Algorithm Guidecomplexity: O(9^(empty cells))

Sudoku Solver

The puzzle of filling a 9×9 grid so 1–9 appears exactly once in each row, column, and 3×3 box. It's backtracking: try a possible number in an empty cell, and on a contradiction reset it to 0 and try another.

01Sudoku Solver

Explore How It Works

4×4 mini Sudoku. Each row, column, and 2×2 box must hold 1–4 exactly once. Fill the two empty cells.

Try 1 in cell (3,2) → the same column already has a 1, so it clashes.

Try 2 → it clashes with the same row (which already has a 2).

Try 3 → the same column has a 3, so it clashes again.

Try 4 → it overlaps with no row, column, or box. Lock 4 into (3,2).

Last cell (3,3) · the remaining number 3 satisfies every rule. Lock it in.

Complete! On a clash, try the next number; when every option is blocked, reset to 0 and retry the previous cell — that's backtracking.

Live Python

1def solve(board):

2 cell = find_empty(board)

3 if not cell:

4 return True # all filled

5 r, c = cell

6 for num in range(1, 5): # 4×4, so 1–4

7 if is_valid(board, r, c, num):

8 board[r][c] = num

9 if solve(board):

10 return True

11 board[r][c] = 0 # backtrack

12 return False

1 / 7

02 Understand It Simply

For Everyone

🔑How It Works

Writes one candidate into a blank cell and moves on, retracting that value the moment it breaks a rule and trying the next candidate.

💡In Plain Words

Try a possible number in each blank; if it breaks a row, column, or box rule, erase it and try the next.

If all fail, back up to the previous cell.

📍Where It's Used

–Constraint-satisfaction puzzles
–timetabling
–placement problems

03 Python Implementation

A clean, readable reference implementation of the core logic of Sudoku Solver.

core_implementation.py

def solve_sudoku(board):
    empty = find_empty(board)
    if not empty:
        return True
    r, c = empty
    for num in range(1, 10):
        if is_valid(board, r, c, num):
            board[r][c] = num
            if solve_sudoku(board):
                return True
            board[r][c] = 0      # backtrack
    return False

04 Frequently Asked Questions

FAQ

What is Sudoku Solver?+

What is the time complexity of Sudoku Solver?+

The time complexity of Sudoku Solver is O(9^(empty cells)). Follow the step-by-step visualization to see exactly why.

Where is Sudoku Solver used?+

Constraint-satisfaction puzzles, timetabling, placement problems.

What's a simple analogy for Sudoku Solver?+

Writes one candidate into a blank cell and moves on, retracting that value the moment it breaks a rule and trying the next candidate.

→ Backtracking — see allRelated