Algorithm

Sudoku Solver

Backtracking Pattern

Sudoku Solver

Fill every empty cell of a 9 × 9 Sudoku grid so the completed board is valid.

A board is valid when each digit 1 through 9 appears exactly once in every row, exactly once in every column, and exactly once in each of the nine 3 × 3 boxes.

Empty cells are given as the character '.'. The board is modified in place — the function returns nothing, and the caller reads the solution out of the grid it passed in. The input is guaranteed to have exactly one solution.

CONSTRAINTS
  • board.length == 9 and board[i].length == 9
  • board[i][j] is a digit character '1'–'9' or the character '.'
  • The given board is valid — no conflicts exist among the pre-filled digits
  • Exactly one solution is guaranteed to exist
  • The board must be modified in place rather than returned
EXAMPLE 1
Input: A row reading 5 3 . . 7 . . . . with the first empty cell at (0,2)
Output: That cell becomes 4
Its row already contains 5, 3 and 7; its column and its 3×3 box eliminate the rest. Only 4 survives all three constraints. Cells with a single surviving candidate are where the search makes progress without guessing.
EXAMPLE 2
Input: An empty cell whose row, column and box between them contain all of 1–9
Output: No digit can be placed — the search backtracks
Every candidate conflicts, so the loop over digits completes without a single placement and the function returns failure. That failure propagates upward, causing an earlier guess to be undone.
EXAMPLE 3
Input: A grid with only one empty cell remaining
Output: The single missing digit is placed and the puzzle is complete
Eight digits are already present in the cell's row, leaving exactly one possibility. The recursion places it, finds no further empty cells, and reports success back up the entire call chain.
EXAMPLE 4
Input: A completely filled valid board
Output: Unchanged — the function returns immediately
With no empty cells the scan finds nothing to fill and reports success at once. Worth checking that the base case handles this rather than looping or failing.
Is the solution guaranteed to be unique?
Yes, which simplifies things considerably: the moment a complete board is reached it is the answer, so the search can stop rather than continuing to look for alternatives. Without that guarantee you would need to decide whether to return the first solution or all of them.
Should the board be modified in place or returned?
Modified in place. The function typically returns nothing to the caller, so returning a new grid instead means the caller sees no change at all — the bug produces no error, just an unsolved board.
Are the cells digits or characters?
Characters, '1' through '9' and '.' for empty. Comparing against integers matches nothing and silently treats every cell as available, so the board fills with conflicting digits.
Could the input already be unsolvable or contain a conflict?
Not here — the given board is valid and solvable. If that were removed, the same algorithm still works and simply reports failure from the top-level call, which is a reasonable thing to note.

Fill every empty cell so each digit 1–9 appears once per row, once per column, and once per 3×3 box. Only one solution exists, so we want the first complete board: the recursion returns True/False and stops the instant it wins. And because the finished board is the answer, we do not undo on success.

The backtracking template

Every problem in this section is the same loop — three beats: choose, explore, un-choose.

python
def backtrack(state):
    if done(state):
        save(state)              # record the finished answer
        return
    for choice in choices(state):    # what can I pick right now?
        if not ok(choice):
            continue                 # prune: skip bad picks early
        apply(choice)                # CHOOSE
        backtrack(next_state)        # EXPLORE
        undo(choice)                 # UN-CHOOSE: put it back

Only four slots change between problems: done, choices, ok (pruning), and how you finish (save every answer, or return True at the first one). Fill those and the problem is solved.

What changes here
- A choice = write a digit 1–9 into the first empty cell.
- Choices = the digits 1–9.
- Done = no empty cell left → return True.
- Prune = skip a digit already in this cell's row, column, or box.
python
def solve_sudoku(board):
    def ok(r, c, ch):
        for i in range(9):
            if board[r][i] == ch or board[i][c] == ch:
                return False
            if board[3*(r//3) + i//3][3*(c//3) + i%3] == ch:   # 3x3 box
                return False
        return True

    def backtrack():
        for r in range(9):
            for c in range(9):
                if board[r][c] != '.':
                    continue
                for ch in "123456789":
                    if not ok(r, c, ch):
                        continue          # PRUNE
                    board[r][c] = ch      # CHOOSE
                    if backtrack():       # EXPLORE
                        return True        # solved — do NOT undo
                    board[r][c] = '.'     # UN-CHOOSE (only on failure)
                return False              # no digit fit: dead end, back up
        return True                       # no empty cell: done

    backtrack()

Two rules unique to "find one answer": return True straight up the chain and don't undo (undoing would erase the solution); and return False after the digit loop, which tells the caller "back up and try something else." A cell's box is (r//3, c//3).

Trace: at the first empty cell, digits 1/2/3 clash with the row/column/box, 4 is clean → place 4, recurse; a later dead-end returns False, undoes, and tries the next digit until the board fills.

Interactive Strategy Visualization

Sudoku Solver Intuition

Search: Recursive Backtracking
5
3
.
.
7
.
.
.
.
6
.
.
1
9
5
.
.
.
.
9
8
.
.
.
.
6
.
8
.
.
.
6
.
.
.
3
4
.
.
8
.
3
.
.
1
7
.
.
.
2
.
.
.
6
.
6
.
.
.
.
2
8
.
.
.
.
4
1
9
.
.
5
.
.
.
.
8
.
.
7
9
Sudoku is a Constraint Satisfaction problem. We must fill every '.' without violating Row, Column, or Box rules.
MINDSET

Sudoku is about **Constraint Satisfaction**. We don't just guess; we systematically fill gaps and immediately abandon any path that violates the row, column, or 3x3 box rules.

PRUNING

Backtracking works because it prunes trillions of branches. If a '5' is invalid at [0,0], we never even look at the $9^80$ possible boards that start with '5' at that position.

O(9^m) Fill Everything Then Validate
→
O(9^m) Pruned By Per-Placement Checks
→
O(9^m) With Constant-Time Constraint Sets