Sudoku Solver

The phrase “try digits and backtrack” is the easy part. The interview-grade solution keeps four representations synchronized: the board, row constraints, column constraints, and 3×3 box constraints.

The reliable plan is:

1. Record every fixed digit in its row, column, and box.
2. Store the empty-cell coordinates.
3. Fill one empty cell with a legal digit.
4. Recurse.
5. Undo the board change and all three constraint updates when the branch fails.

That is a constraint satisfaction backtracking solution. The search is ordinary; the state discipline is the real problem.

Read the Sudoku Contract

The canonical problem provides a fixed 9×9 board:

• A digit from "1" through "9" is already placed.
• "." marks an empty cell.
• Existing digits cannot be changed.
• Every completed row, column, and 3×3 sub-box must contain digits 1 through 9 exactly once.
• The board has one solution.
• The supplied board is filled in place.

The unique-solution guarantee changes the stopping rule. We do not need to count solutions or enumerate alternatives. The first complete assignment is enough.

The solver therefore needs to answer one question repeatedly:

Can digit d be placed at (r, c) without violating its row, column, or box?

A naive implementation could scan the relevant row, column, and box every time. That works conceptually, but it repeats the same membership work throughout the search. Since the digit domain is fixed at nine values, we can maintain the answers incrementally.

Recognize the Search Shape

Sudoku has the standard signals for constraint satisfaction backtracking:

• There is a partial assignment.
• Each empty cell is a variable.
• Digits 1 through 9 are candidate values.
• A candidate can be rejected using local constraints.
• A locally legal choice may make a later cell impossible.
• Failed choices must be removed before trying another choice.

The brute-force baseline is to assign digits to empty cells and validate the board after completing an assignment. With E empty cells, that explores a search space shaped like 9^E, while repeatedly doing full-board validation.

The better version rejects illegal branches immediately. A digit that already appears in the current row, column, or box never enters the recursive search.

This is the same broad backtracking move used in other problems—choose, recurse, undo—but the pruning state is different. Sudoku has three interacting constraint families. The solver must update all three on every placement.

Turn the Rules into State

Use three Boolean membership tables:

row_used[r][d]  = digit d is already in row r
col_used[c][d]  = digit d is already in column c
box_used[b][d]  = digit d is already in box b

Here d can be an integer from 0 through 8, representing the board digit d + 1.

The box containing (r, c) is:

box_id = (r // 3) * 3 + (c // 3)

This maps the nine 3×3 boxes to IDs from 0 through 8:

0 1 2
3 4 5
6 7 8

For example, (r=4, c=7) belongs to:

(4 // 3) * 3 + (7 // 3)
= 1 * 3 + 2
= 5

The preprocessing pass records every given digit in all three structures. After that, a candidate is legal exactly when:

not row_used[r][d]
and not col_used[c][d]
and not box_used[b][d]

The central invariant is worth stating precisely:

At every recursive call, the board and all three tracking tables describe the same set of placed digits.

That invariant is the foundation of the Sudoku Solver solution. If one representation disagrees with the others, candidate pruning becomes fiction.

Boolean tables are the clearest implementation for an interview. Bitmasks can represent the same information more compactly, but they add bit operations to the explanation without changing the search idea. Start with the representation that makes state transitions auditable.

Derive Placement and Undo

Collect the coordinates of all empty cells before searching:

empty = [(r0, c0), (r1, c1), ...]

The recursive helper receives an index i into that fixed list.

Base case

If:

i == len(empty)

then every empty cell has been filled. Because the invariant says every placement respected row, column, and box membership, the board is a valid completion.

Recursive transition

For the current empty cell (r, c):

1. Compute its box ID.
2. Try digits 1 through 9.
3. Skip a digit already used by the row, column, or box.
4. Mark the digit in all three tables.
5. Write it to the board.
6. Recurse on the next empty cell.
7. If the recursive call succeeds, propagate True.
8. Otherwise erase the board cell and unmark the digit everywhere.

Placement and undo must be exact opposites:

State	On placement	On failure
Board	write digit	write "."
Row table	mark digit	unmark digit
Column table	mark digit	unmark digit
Box table	mark digit	unmark digit

The common broken implementation clears the board cell but forgets one index. That stale bit or Boolean becomes a ghost constraint: a digit appears unavailable even though it is no longer on the board.

Undo is not cleanup around the algorithm. Undo is one half of the algorithm. Every mutation made before recursion must be reversed before the next sibling branch is explored.

Choose Search Order Deliberately

A fixed order through empty is the best baseline:

• The recursion state is only an integer index.
• Progress is obvious.
• The correctness proof is short.
• The code has fewer moving parts.

For the fixed 9×9 problem, this is usually the version I would write first in an interview. Search order affects branching, not correctness. State consistency is the higher-risk problem.

A common optimization is minimum remaining values, or MRV:

1. Inspect every unfilled cell.
2. Compute its legal candidates.
3. Choose the cell with the smallest candidate set.
4. Branch on that cell.

MRV can expose contradictions earlier. A cell with zero candidates immediately proves the current branch is impossible; a cell with one candidate is a forced transition.

The tradeoff is additional work and proof surface. Each recursive call must rescan unfilled cells, compute candidate sets, and select a position. That is worthwhile when search branching is the bottleneck, not when the implementation is still leaking stale state.

My decision rule is simple:

Implement fixed order first. Add MRV only after the placement and restoration invariant is correct and search branching is the measured problem.

Do not confuse this algorithmic heuristic with human Sudoku techniques such as pairs, X-Wings, or other deduction systems. Those are different solving strategies. This article is about systematic constraint tracking plus search.

Prove the Invariant

A compact proof has five parts.

Initialization

For every prefilled digit, preprocessing marks:

• its row membership,
• its column membership,
• its box membership.

Therefore the board and tracking tables agree before recursion starts.

Legal placement

A candidate is placed only if it is absent from all three relevant constraint tables. Therefore the new partial board contains no duplicate digit in the affected row, column, or box.

All unaffected structures remain unchanged, so the invariant is preserved.

Restoration

If the recursive suffix fails, the solver:

• removes the digit from the board,
• clears its row membership,
• clears its column membership,
• clears its box membership.

The state returns exactly to its condition before the candidate was tried. The next candidate therefore starts from a clean sibling branch.

Termination

Each successful recursive transition fills one previously empty cell. With E empty cells, a branch performs at most E placements before reaching the base case.

Soundness and completeness

At the base case, every empty cell is filled. The invariant guarantees that all row, column, and box obligations hold, so the returned board is valid.

For completeness, every digit that is legal in the current state is considered. The solver may reject a branch only after a later contradiction proves that branch cannot lead to a completion. Since the input is guaranteed to have a solution, the search can reach it.

The important distinction is this:

A candidate can be locally legal without being globally viable.

That is precisely why backtracking exists.

Trace a Candidate and a Dead End

Use the familiar starting board:

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

Take the first empty cell, (0, 2).

Its row already contains:

5, 3, 7

Its column contains:

8

Its top-left box contains:

5, 3, 6, 9, 8

The legal candidates are therefore:

{1, 2, 4}

The full set difference is the useful mental model:

{1, 2, 3, 4, 5, 6, 7, 8, 9}
- row digits
- column digits
- box digits
= {1, 2, 4}

Suppose the search tries 4.

The mutation is:

board[0][2] = "4"
row_used[0][3] = True
col_used[2][3] = True
box_used[0][3] = True

The digit 4 is indexed by 3 because the code uses zero-based digit indexes.

The search advances. At a later cell, suppose every digit is already blocked by its row, column, or box. That cell has no candidates. This is a contradiction in the current branch—not evidence that the original puzzle has no solution.

The solver then reverses the exact previous mutation:

board[0][2] = "."
row_used[0][3] = False
col_used[2][3] = False
box_used[0][3] = False

Only now can it try 1 or 2 at (0, 2).

That is the mechanical heart of backtracking: make a reversible commitment, let its consequences propagate, and restore the previous state when the commitment fails.

Implement the Python Solver

The following Python implementation uses:

• row_used, col_used, and box_used as Boolean tables,
• zero-based digit indexes internally,
• a fixed list of empty cells,
• a Boolean recursive result to propagate success.

from typing import List


def solveSudoku(board: List[List[str]]) -> None:
    row_used = [[False] * 9 for _ in range(9)]
    col_used = [[False] * 9 for _ in range(9)]
    box_used = [[False] * 9 for _ in range(9)]
    empty_cells = []

    def box_id(row: int, col: int) -> int:
        return (row // 3) * 3 + (col // 3)

    # Build the constraint indexes and collect variables.
    for row in range(9):
        for col in range(9):
            value = board[row][col]

            if value == ".":
                empty_cells.append((row, col))
                continue

            digit = ord(value) - ord("1")
            box = box_id(row, col)

            row_used[row][digit] = True
            col_used[col][digit] = True
            box_used[box][digit] = True

    def search(index: int) -> bool:
        if index == len(empty_cells):
            return True

        row, col = empty_cells[index]
        box = box_id(row, col)

        for digit in range(9):
            if (
                row_used[row][digit]
                or col_used[col][digit]
                or box_used[box][digit]
            ):
                continue

            # Place the candidate.
            board[row][col] = chr(ord("1") + digit)
            row_used[row][digit] = True
            col_used[col][digit] = True
            box_used[box][digit] = True

            if search(index + 1):
                return True

            # Undo every mutation before trying the next candidate.
            board[row][col] = "."
            row_used[row][digit] = False
            col_used[col][digit] = False
            box_used[box][digit] = False

        return False

    search(0)

The helper returns True when the suffix beginning at index can be solved. That return value matters. When a complete solution is found, every earlier call must stop exploring and propagate success.

A subtle point: the function mutates board in place and returns None. That matches the problem contract. The solved board is the output.

The digit conversion is also deliberate:

digit = ord(value) - ord("1")

This maps:

"1" -> 0
"2" -> 1
...
"9" -> 8

The board retains character values because that is its supplied representation. The tracking tables use integer indexes because fixed-size arrays are simple and predictable.

Complexity and Edge-Case Checks

Let E be the number of empty cells.

Time

At each recursive level, the solver may try up to nine digits. The worst-case search has the shape:

O(9^E)

This is an upper-bound description, not a prediction of typical runtime. Constraint pruning usually removes many branches before they become deep.

Each candidate check, placement, and undo touches a constant number of Boolean entries, so each costs O(1) under the fixed nine-digit domain. Preprocessing the 81 cells and collecting empty positions costs O(81).

MRV changes the per-level work because it repeatedly scans empty cells and computes their candidate sets. It can reduce the explored search tree while increasing selection overhead. The right comparison is therefore not “MRV is always faster,” but:

MRV spends more work choosing a branch in exchange for potentially exploring fewer branches.

Space

The recursion depth is at most E. The empty-cell list also stores E coordinate pairs.

The row, column, and box tables have fixed size:

9 × 9 + 9 × 9 + 9 × 9

So the auxiliary space is O(E) plus fixed-size storage.

Edge cases and failure modes

Test cases should target state transitions, not only successful output:

• Already completed valid board: empty_cells is empty, so the base case returns immediately.
• One empty cell: the solver should place the only legal digit and stop.
• A branch that requires undo: verify that failed candidates do not contaminate later candidates.
• A late contradiction: verify that the solver backtracks rather than declaring the original board unsolvable.
• Wrong box formula: test cells in every box, especially positions crossing row or column group boundaries.
• Mixed digit indexes: do not mark with digit + 1 in one place and digit in another.
• Stale indexes: clearing only board[row][col] is insufficient.
• Incorrect success propagation: after a recursive success, return immediately. Continuing can undo the solved placement.
• Treating "." as a digit: skip it during preprocessing and only write actual digits during search.

The canonical contract guarantees a 9×9 board with a solution. Malformed input, contradictory fixed digits, or unsolvable boards are outside that contract unless you explicitly choose to validate and handle them.

Reuse the Backtracking Move

The transferable recognition rule is:

When a problem builds a partial assignment under cheap local constraints, identify the variables, candidate values, validity predicate, and reversible state.

For Sudoku:

• Variables: empty cells.
• Values: digits 1 through 9.
• Validity predicate: absent from the row, column, and box.
• State: board contents plus three constraint indexes.
• Transition: place one legal digit.
• Failure response: undo every mutation and try the next candidate.

Every state structure should answer a named obligation. The row, column, and box tables are not arbitrary optimization furniture; they are executable forms of the Sudoku rules.

In an interview, explain that contract before writing code:

“I will maintain synchronized row, column, and box membership. For each empty cell, I will try every legal digit, recurse, and undo all four mutations if the suffix fails.”

That sentence gives the code somewhere to go.

The durable pattern is:

Choose. Mutate. Prune by invariant. Recurse. Undo symmetrically.

When you see a partial assignment, local validity checks, and a later contradiction that can invalidate an earlier choice, stop thinking about cleverness. Name the constraints, make the state visible, and build the undo path before you build the search.