vault

Sudoku Solver

17 min read

Sudoku Solver

LeetCode 37 — fill a partially-filled 9×9 grid such that every row, every column, and every 3×3 sub-box contains the digits 1–9 exactly once. The classical solution is backtracking with constraint propagation: find an empty cell, try each digit 1-9, recurse if the placement is consistent with rows / columns / boxes seen so far. Maintaining nine row-sets, nine column-sets, and nine box-sets (or three 9-bit bitmasks each) makes the consistency check O(1) per attempt — without it, every check would scan up to 27 cells, making the solver tens of times slower in practice. The MRV (Minimum Remaining Values) heuristic — always pick the empty cell with the fewest legal choices — collapses the search tree on most “newspaper-difficulty” puzzles to a few hundred nodes. Knuth’s Dancing Links (Algorithm X) reformulates Sudoku as exact-cover and solves the hardest 9×9 instances in microseconds; it generalises to arbitrary exact-cover problems including N-Queens, polyomino tilings, and pentominoes. The interview-grade implementation is plain backtracking with bitmask constraints — fast enough that Norvig’s famous 2007 “Solving Every Sudoku Puzzle” essay solves all 49,151 17-clue puzzles in under a second per puzzle in pure Python.

1. Intuition — Try, Check, Backtrack

The brute-force-est approach (“try every assignment of digits to empty cells”) visits up to 9^k configurations for k empty cells — for a typical 50-empty-cell puzzle, 9^50 ≈ 5 × 10^47. Infeasible.

The fix is twofold:

  1. Place digits one cell at a time, not all at once. Pick an empty cell; try each digit; if the digit is consistent with what’s already on the board (no other 1 in the row, column, or 3×3 box), commit and recurse. If consistent placements at this cell all fail later, backtrack and undo.
  2. Make consistency check O(1), not O(n). Instead of scanning row, column, and box on every attempted placement, maintain three arrays of sets (or bitmasks): row_used[r], col_used[c], box_used[b]. To check “can I put digit d here?”, check three set memberships. To commit, add to three sets. To undo, remove from three sets.

The third lever is ordering: 3. Pick the most constrained empty cell first — the one with the fewest legal digits. This is the MRV (Minimum Remaining Values) heuristic, formalised in CSP literature (Russell & Norvig Ch. 6.2). MRV reduces the branching factor at the top of the recursion tree, where pruning matters most.

For a typical Sudoku puzzle, the unpruned tree (without (2) and (3)) has 9^50 nodes; the pruned tree with bitmask constraints alone has perhaps 10⁵ nodes; with MRV ordering on top, it shrinks to ~10²-10³ nodes. The whole puzzle solves in milliseconds.

2. Tiny Worked Example

For brevity, take a 4×4 mini-Sudoku (1-4 instead of 1-9, with 2×2 boxes):

. 2 | . .
. . | . 4
----+----
. 1 | . .
4 . | 2 .

Convention: cells are board[r][c], boxes are indexed b = (r // 2) * 2 + (c // 2) (so b ∈ {0, 1, 2, 3}).

Initial constraint sets (after reading the givens):

  • row_used = [{2}, {4}, {1}, {4, 2}]
  • col_used = [{4}, {2, 1}, {2}, {4}]
  • box_used = [{2}, {4}, {1, 4}, {2}]

Find empty cells. Try each. Apply MRV:

  • (0, 0): legal digits = {1,2,3,4} − row[0] − col[0] − box[0] = {1,2,3,4} − {2} − {4} − {2} = {1, 3}. Two choices.
  • (0, 2): {1,2,3,4} − {2} − {2} − {4} = {1, 3}. Two choices.
  • (0, 3): {1,2,3,4} − {2} − {4} − {4} = {1, 2, 3}. Three.
  • (1, 0): {1,2,3,4} − {4} − {4} − {2} = {1, 3}. Two.
  • … (etc.)

The MRV pick is any cell with two choices. Take (0, 0).

Try digit 1 at (0, 0):

  • row_used[0] = {2, 1}, col_used[0] = {4, 1}, box_used[0] = {2, 1}. Recurse.

In the recursion, find next empty (apply MRV again). Suppose we pick (0, 2):

  • legal = {1,2,3,4} − {2,1} − {2} − {4} = {3}. One choice. Forced.

Place 3:

  • row_used[0] = {2,1,3}, col_used[2] = {2,3}, box_used[1] = {4,3}. Recurse.

Continue cell-by-cell. Most cells become forced after the first two choices because constraint propagation cascades. The whole 4×4 puzzle solves in ~10 backtracking steps.

If at some level, the legal-digits set is empty, backtrack: undo the most recent placement (remove from row_used / col_used / box_used) and try the next digit at the prior cell.

3. Pseudocode

3.1 Plain Backtracking with Set Constraints

solve_sudoku(board):
    rows := array of 9 empty sets
    cols := array of 9 empty sets
    boxes := array of 9 empty sets

    # Initialise from existing board
    for r := 0..8, c := 0..8:
        if board[r][c] != '.':
            d := board[r][c]
            rows[r].add(d); cols[c].add(d); boxes[box(r, c)].add(d)

    backtrack(board, 0, 0)

backtrack(board, r, c):
    if r == 9:
        return True                                  # solved
    nr, nc := next_cell(r, c)                        # row-major next
    if board[r][c] != '.':
        return backtrack(board, nr, nc)              # skip filled cells

    for d := 1 to 9:
        b := box(r, c)
        if d in rows[r] or d in cols[c] or d in boxes[b]:
            continue                                  # prune
        # apply
        board[r][c] := d
        rows[r].add(d); cols[c].add(d); boxes[b].add(d)
        # recurse
        if backtrack(board, nr, nc):
            return True                               # propagate solution up
        # undo (mirror)
        board[r][c] := '.'
        rows[r].remove(d); cols[c].remove(d); boxes[b].remove(d)

    return False                                      # all 9 digits failed at this cell

box(r, c) := (r // 3) * 3 + (c // 3)

The five Backtracking Framework primitives map as:

PrimitiveThis problem
is_solution(state)All cells filled (r == 9)
choices(state)Digits 1-9
valid(choice)d not in row, col, box constraint sets
apply(choice)Set board[r][c], add d to three sets
undo(choice)Reset cell, remove d from three sets

3.2 With MRV Heuristic (Most-Constrained Variable First)

backtrack_MRV(board):
    if no empty cell:
        return True

    # Find the empty cell with the fewest legal digits
    best_cell := None; best_options := None
    for r := 0..8, c := 0..8:
        if board[r][c] == '.':
            options := {d for d in 1..9 if d not in rows[r], cols[c], boxes[box(r,c)]}
            if best_cell == None or |options| < |best_options|:
                best_cell := (r, c); best_options := options
                if |options| == 0:
                    return False                       # dead-end early
                if |options| == 1:
                    break                              # forced; can't beat this

    (r, c) := best_cell
    for d in best_options:
        apply
        if backtrack_MRV(board): return True
        undo
    return False

The MRV heuristic adds O(81) overhead per recursion level (scan all empties to find the best) but reduces the tree size by orders of magnitude. Net win for non-trivial puzzles.

4. Python Implementation

4.1 Plain Backtracking

from typing import List
 
 
def solve_sudoku(board: List[List[str]]) -> None:
    """
    LeetCode 37. Modify board in place to fill empty ('.') cells with digits 1-9
    such that every row, column, and 3x3 box contains 1-9 exactly once.
    """
    rows = [set() for _ in range(9)]
    cols = [set() for _ in range(9)]
    boxes = [set() for _ in range(9)]
 
    # Initialize constraint sets from given clues.
    for r in range(9):
        for c in range(9):
            if board[r][c] != '.':
                d = board[r][c]
                rows[r].add(d); cols[c].add(d); boxes[(r // 3) * 3 + c // 3].add(d)
 
    def backtrack(idx: int) -> bool:
        if idx == 81:
            return True
 
        r, c = divmod(idx, 9)
 
        if board[r][c] != '.':
            return backtrack(idx + 1)                 # skip pre-filled cells
 
        b = (r // 3) * 3 + c // 3
 
        for d in '123456789':
            if d in rows[r] or d in cols[c] or d in boxes[b]:
                continue
            # apply
            board[r][c] = d
            rows[r].add(d); cols[c].add(d); boxes[b].add(d)
            # recurse
            if backtrack(idx + 1):
                return True
            # undo
            board[r][c] = '.'
            rows[r].remove(d); cols[c].remove(d); boxes[b].remove(d)
        return False
 
    backtrack(0)

4.2 With Bitmask Constraints (Faster)

Replace each set with a 9-bit integer. Bit i = digit i+1 is used. Membership check is one AND; addition is OR; removal is XOR.

def solve_sudoku_bitmask(board: List[List[str]]) -> None:
    rows = [0] * 9
    cols = [0] * 9
    boxes = [0] * 9
    empties: list[tuple[int, int]] = []
 
    for r in range(9):
        for c in range(9):
            if board[r][c] != '.':
                bit = 1 << (int(board[r][c]) - 1)
                rows[r] |= bit; cols[c] |= bit; boxes[(r // 3) * 3 + c // 3] |= bit
            else:
                empties.append((r, c))
 
    def backtrack(i: int) -> bool:
        if i == len(empties):
            return True
        r, c = empties[i]
        b = (r // 3) * 3 + c // 3
        used = rows[r] | cols[c] | boxes[b]            # 9-bit mask of forbidden digits
        free = (~used) & 0x1FF                         # 9-bit mask of allowed digits
        while free:
            bit = free & -free                          # lowest set bit
            free ^= bit
            d = bit.bit_length()                        # digit = 1..9
            board[r][c] = str(d)
            rows[r] ^= bit; cols[c] ^= bit; boxes[b] ^= bit
            if backtrack(i + 1):
                return True
            rows[r] ^= bit; cols[c] ^= bit; boxes[b] ^= bit
            board[r][c] = '.'
        return False
 
    backtrack(0)

The bitmask version is typically 2-3× faster than the set version for the worst-case 17-clue puzzles (the most constrained valid Sudoku has exactly 17 clues, McGuire, Tugemann & Civario 2014).

4.3 With MRV Heuristic

def solve_sudoku_mrv(board: List[List[str]]) -> None:
    rows = [0] * 9; cols = [0] * 9; boxes = [0] * 9
 
    for r in range(9):
        for c in range(9):
            if board[r][c] != '.':
                bit = 1 << (int(board[r][c]) - 1)
                rows[r] |= bit; cols[c] |= bit; boxes[(r // 3) * 3 + c // 3] |= bit
 
    def backtrack() -> bool:
        # Find the empty cell with the fewest legal options (MRV).
        best_r, best_c, best_free = -1, -1, 0
        best_count = 10  # max possible is 9
        for r in range(9):
            for c in range(9):
                if board[r][c] != '.':
                    continue
                used = rows[r] | cols[c] | boxes[(r // 3) * 3 + c // 3]
                free = (~used) & 0x1FF
                count = bin(free).count('1')
                if count == 0:
                    return False                       # this cell has no option; dead-end
                if count < best_count:
                    best_r, best_c, best_free = r, c, free
                    best_count = count
                    if count == 1:
                        break                          # forced — can't do better
            if best_count == 1:
                break
 
        if best_r == -1:
            return True                                # no empty cells
 
        r, c = best_r, best_c
        b = (r // 3) * 3 + c // 3
        free = best_free
        while free:
            bit = free & -free
            free ^= bit
            d = bit.bit_length()
            board[r][c] = str(d)
            rows[r] ^= bit; cols[c] ^= bit; boxes[b] ^= bit
            if backtrack():
                return True
            rows[r] ^= bit; cols[c] ^= bit; boxes[b] ^= bit
            board[r][c] = '.'
        return False
 
    backtrack()

This is the implementation Norvig’s blog post effectively builds (via constraint propagation + MRV). It solves any reasonable Sudoku in <10 ms in pure Python.

5. Complexity

5.1 Worst Case

Without constraints, brute-force is O(9^k) where k is the number of empty cells (up to 81). For a near-empty board, that’s 9^81 ≈ 10⁷⁷ — astronomically infeasible.

With row / column / box constraints alone, the bound becomes harder to state precisely. Knuth (TAOCP 4A §7.2.2) discusses Sudoku as a canonical example where worst-case bounds are easy to write down (O(9^k)) but tight bounds are open. Empirically, real puzzles (uniquely-solvable, 17-30 clues) solve in O(10²-10⁴) backtracking nodes.

Sudoku is NP-complete in the generalised case

The general “n²×n² Sudoku” decision problem (does a partially filled n²×n² grid admit a completion?) is NP-complete (Yato & Seta 2003). So no polynomial-time algorithm can be expected for arbitrary n. For fixed n = 9, every instance is solvable in O(1) time (since the input size is bounded), but the constant is large enough that algorithm choice matters.

5.2 Empirical Performance

For the 49,151 known 17-clue Sudoku puzzles (McGuire, Tugemann & Civario 2014):

  • Plain backtracking (set version): ~10-100 ms per puzzle in Python
  • Bitmask backtracking: ~3-30 ms per puzzle
  • Bitmask + MRV: ~1-5 ms per puzzle
  • Knuth’s Dancing Links (Algorithm X): ~10-100 µs per puzzle

The Sudoku Solver benchmark on LeetCode 37 accepts plain backtracking; MRV is unnecessary for the LC test cases but is essential for the worst-case competitive-programming inputs.

5.3 Space

Recursion depth ≤ 81. Constraint sets / bitmasks: O(1) (constant 27 sets / 27 ints). Total auxiliary: O(1).

6. Constraint Encoding — Sets vs Bitmasks

The choice of data structure for constraint tracking is the dominant performance lever after the algorithm itself. Comparison:

EncodingMembership checkAdd/removeMemoryPythonic?
set[str]O(1) (hash)O(1) (hash)~100 bytes/setYes
set[int]O(1) (hash)O(1) (hash)~100 bytes/setYes
list[bool] of size 10O(1) (index)O(1) (index)~80 bytes/listOK
9-bit intO(1) (bitwise AND)O(1) (bitwise XOR)28 bytes (small int)Most Pythonic

The bitmask version wins in cache locality and avoids hash overhead. For interview purposes, the set version is acceptable and often clearer.

The bitmask encoding has additional benefits:

  • popcount(free) (number of set bits in the free mask) gives the option count for MRV in O(1) (Python: bin(free).count('1') or, for performance, int.bit_count() in Python 3.10+).
  • Iterating set bits via bit = free & -free; free ^= bit is faster than for d in 1..9 if d not in used.
  • Storage is one int per row / col / box, not a hash set.

7. Knuth’s Dancing Links / Algorithm X

For the curious / advanced reader: Knuth’s Algorithm X (“Dancing Links” or DLX, from his 2000 paper) reformulates Sudoku as an exact cover problem and uses a doubly-linked-list “remove and re-insert” trick to make backtracking nearly free of allocation overhead.

Reformulation. Each cell-and-digit assignment (r, c, d) is a “row” in an exact-cover matrix. The “columns” are the constraints:

  • 81 cells (each cell must contain exactly one digit)
  • 81 row-digit constraints (each row must contain each digit exactly once: 9 rows × 9 digits)
  • 81 column-digit constraints
  • 81 box-digit constraints
  • Total: 324 constraint columns; 729 candidate-row entries.

A valid Sudoku is exactly a partial cover of all 324 columns by 81 of the 729 rows. Knuth’s algorithm efficiently searches this combinatorial space by maintaining the doubly-linked list of “uncovered columns” and “remaining candidate rows”, removing them upon commit and re-inserting upon undo (the “dancing” of the links — they’re never deallocated, just unlinked).

The big win: O(1) constraint-removal and O(1) candidate-row enumeration with extreme cache locality. DLX solves the hardest 9×9 Sudoku in microseconds and generalises to N-Queens, polyomino-tiling, and pentomino packing problems.

For interview purposes, the plain backtracking solver above is sufficient and fits in 30 lines; DLX is worth knowing about but rarely required.

8. Diagram — The Constraint Propagation Picture

flowchart TD
    BOARD["9x9 board with empty cells"]
    BOARD --> CELL["Pick empty cell (r, c)"]
    CELL --> CHK{"For each digit d in 1..9:<br/>d in row[r]?<br/>d in col[c]?<br/>d in box[(r//3)*3+c//3]?"}
    CHK -->|"any → yes"| SKIP["Skip d (prune)"]
    CHK -->|"all → no"| PLACE["Place d:<br/>add d to row[r], col[c], box[b]"]
    PLACE --> RECURSE["Recurse on next empty cell"]
    RECURSE -->|"sub-tree fails"| UNDO["Undo:<br/>remove d from row[r], col[c], box[b]<br/>try next d"]
    RECURSE -->|"sub-tree succeeds"| DONE["Solved — propagate True up"]
    SKIP --> CHK

    style PLACE fill:#cfc
    style UNDO fill:#fcc
    style DONE fill:#ccf

What this diagram shows. The lifecycle of a single cell-decision in the Sudoku backtracker. We pick an empty cell, then for each digit d from 1 to 9, perform three constraint-set membership tests (row, column, box). If any test rejects, we skip and try the next digit. If all pass, we apply — write d into the board and add it to the three constraint sets — and recurse to the next empty cell. If the recursive subtree fails (no completion exists from this state), we undo exactly the same three additions and try the next d. If 1-9 all fail at this cell, the parent recursion backtracks. The colour coding emphasises the apply / undo symmetry and the success / failure outcomes. With MRV ordering on top of this, the “pick empty cell” step always picks the most-constrained one, dramatically shrinking the tree.

9. Pitfalls

  1. Forgetting to undo all three constraint sets. As with N-Queens, forgetting to remove d from any one of rows[r], cols[c], boxes[b] corrupts later branches and produces wrong answers (or no answer found). Test with a known unique-solution puzzle.
  2. Wrong box index formula. (r // 3) * 3 + (c // 3) is the standard 9-box layout: row 0-2 of the column → boxes 0-2, row 3-5 → 3-5, etc. Easy to write r // 3 + c // 3 (not multiplied by 3) which collapses 9 boxes into 5 indices and silently lets digits collide.
  3. Mutating board in place but checking board[r][c] == '.' against the wrong sentinel. LeetCode 37 uses '.' (string). Some implementations use 0 (int). Mixing them silently fails. Be consistent.
  4. Returning False and not propagating up. The recursion needs to return True on success and short-circuit. Forgetting if backtrack(...): return True makes the algorithm find every cell-assignment and report only the last (often wrong) one.
  5. Iterating for d in '123456789' but using int(d) - 1 as the bit index. Either iterate over range(9) and use d + 1 for the digit character, or iterate over '123456789' and convert. Mixing produces off-by-one bugs in the bitmask.
  6. MRV breaks ties pessimally. When multiple cells have the same minimum option count, the choice doesn’t matter for correctness but can swing performance by 10×. Some implementations break ties by “most constraining variable” (the cell that appears in the most constraints), but for 9×9 Sudoku, MRV alone is enough.
  7. MRV scans all 81 cells per call. That’s O(81) overhead per recursion level. For deep trees, this dominates. Optimisation: maintain a priority structure (heap or simple sorted list) of empty cells keyed by current option count. Only updates needed when a constraint changes — but the bookkeeping is fiddly.
  8. Trying to “speed up” with Python multiprocessing. Sudoku backtracking is sequential by nature (each level depends on the parent). Multiprocessing rarely helps unless you’re solving a batch of independent puzzles.
  9. Using a dict instead of a list/array for constraint sets. Hash overhead for 9-element lookups dominates. Use list[set] or list[int], indexed directly.
  10. Forgetting that LeetCode 37 promises a unique solution. The algorithm above returns the first solution found, which is correct for unique-solution inputs. For count all solutions (the harder variant), return only after exhausting all branches and accumulate results.
  11. Recursion depth in pathological puzzles. Maximum depth is 81 — safely within Python’s default limit. Not a real concern.
  12. Naive if board[r][c] != '.': skip inside a loop instead of a precomputed list of empties. Each level does an O(81) scan to find the next empty. Precomputing the list of empty cells once at the start drops to O(1) per level. The bitmask version above does this.

10. Common Interview Problems

ProblemLeetCodeDifficultyNotes
Sudoku Solver37HardThis note’s main subject
Valid Sudoku36MediumJust check the partial board for current consistency. No solving.
Sudoku Generator—HardGenerate a valid puzzle with unique solution. Inverse of solving.
KenKen / Killer Sudoku—VariantAdd cage / sum constraints; same backtracking schema with additional checks
N-Queens51HardSibling backtracking. See N-Queens
Word Search79MediumSibling backtracking. See Word Search
Constraint Propagation in CSPAI / theoryRussell-Norvig Ch. 6The general framework; Sudoku is the canonical example
Exact Cover (NP-complete)—TheoreticalAlgorithm X / DLX; Sudoku reduces to it

11. Open Questions

  • Can the MRV heuristic be improved by combining it with least-constraining-value (LCV) for digit ordering? Empirically marginal for 9×9 Sudoku; the wins are dominated by MRV alone.
  • How does arc consistency (AC-3) layer on top of MRV? AC-3 propagates constraints transitively (if cell (r, c) can only be 5, all peers’ “5”-option is removed, which may force their values, etc.). Norvig’s solver uses this; gains a 5-10× speedup on hard puzzles. Adds bookkeeping complexity.
  • What is the minimum number of clues for a uniquely-solvable Sudoku? Proven to be 17 by McGuire, Tugemann & Civario 2014 using exhaustive search via Algorithm X — they checked all ~10^11 16-clue puzzles and found none with a unique solution.
  • Are there harder variants for which Sudoku-style backtracking fails practically? Yes — 25×25 “killer Sudoku” or “samurai Sudoku” can require deeper constraint propagation; pure backtracking can blow up.
  • Is there a polynomial-time algorithm specific to uniquely-solvable 9×9 Sudoku (a sub-class)? Open question; conjectured no.

12. See Also

Graph View

Backlinks