Sudoku Solver

Sudoku Solver is the classic backtracking interview problem. You fill a grid by guessing, and when a guess paints you into a corner, you erase it and try the next one. It is depth-first search with an undo step — the move that powers N-Queens, word search, and combination puzzles too.

3 . | . 1
. 1 | . .
----+----
. . | 1 .
2 . | . 3

The slow way first

You could try every possible assignment of digits to all the blanks and check, at the very end, whether the whole board is legal. That is astronomically wasteful — the number of full assignments explodes, and almost all of them are obviously illegal long before the last cell.

The question to ask: can I reject a bad path early instead of at the end? Yes — the moment a digit conflicts with its row, column, or box, that whole branch is dead. Pruning early is what makes the search tractable.

The idea: guess, recurse, undo

Walk to the first empty cell. Try each digit d from 1 to 4 (1 to 9 in real Sudoku). If d is valid there — not already in its row, column, or box — place it and recurse to fill the rest. If the recursion eventually succeeds, you are done. If it fails, erase d (backtrack) and try the next digit. If no digit works, return failure so the caller backtracks one level up.

The base case is the win condition: when there is no empty cell left, the board is fully and legally filled, so we return success and the recursion unwinds.

Walk through it

Step through the animation. We place 2 then 4 across row 0, then 4 at (1,0). At (1,2) we guess 3 — it looks fine locally, but recursion deeper hits a cell where no digit fits, so the call returns False. We erase the 3 and try the next candidate, 2, which leads to a clean finish. That erase-and-retry is the backtrack.

Pseudocode

solve(board):
    empty = first blank cell, scanning row by row
    if there is no blank:
        return True                 # solved
    for each digit d in 1..4:
        if d is valid in this row, column, and box:
            place d in the cell
            if solve(board):        # recurse
                return True
            erase the cell          # backtrack: undo the guess
    return False                    # no digit worked → caller backtracks

The Python solution

def solve(board):
    empty = find_empty(board)
    if empty is None:
        return True            # no blanks left → solved
    r, c = empty
    for d in range(1, 5):      # digits 1..4
        if valid(board, r, c, d):
            board[r][c] = d
            if solve(board):
                return True
            board[r][c] = 0    # backtrack: undo the guess
    return False               # no digit worked here

• find_empty scans the board and returns the (r, c) of the first blank, or None.
• When empty is None there are no blanks left, so the board is complete — return True.
• for d in range(1, 5) tries each candidate digit (use range(1, 10) for a 9x9 board).
• valid(board, r, c, d) checks the row, the column, and the box — this is the pruning that kills bad branches early.
• We place d, then recurse. If the deeper call returns True, the answer is fixed and we propagate True up.
• Line 11 is the backtrack: when the recursion fails we erase the cell and let the loop try the next digit.

Complexity

Because the board has a fixed size (9x9), the worst case is technically a constant — but a big one. The validity pruning is what keeps real puzzles fast: most digit choices are rejected immediately, so the search tree stays shallow.

When this pattern shows up

Practice