Sudoku Solver — Constraint Propagation Plus Backtracking

Problem Statement#

LC 37 — Sudoku Solver. Write a program to solve a Sudoku puzzle by filling the empty cells. The board is a 9 x 9 2D array where empty cells are represented by . and digits 1 through 9 represent fixed clues. The completed board must satisfy three rules: every row contains digits 1-9 exactly once, every column contains digits 1-9 exactly once, and each of the nine 3 x 3 boxes contains digits 1-9 exactly once. The solution is guaranteed to exist and to be unique.

Constraints: board.length == 9, board[i].length == 9, characters are digits or ., the input is a valid Sudoku puzzle.

Example:

Input:
[["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"]]
 
Output: a fully filled 9x9 board satisfying all three constraints.

Why This Problem Matters#

Sudoku is the canonical Constraint Satisfaction Problem (CSP) every algorithms textbook reaches for. Inside Google, Meta, Microsoft, and Amazon onsite loops it tests four orthogonal skills: clean recursive structure, efficient state representation, constraint propagation, and (at senior levels) heuristic ordering. The data structures that make Sudoku fast — three bitsets per dimension — are the same ones that power register allocators, exam timetabling engines, and SAT solvers.

The puzzle is also a perfect interview problem because it is small enough to fit on a whiteboard but large enough that a naive solution times out. A candidate who jumps to "scan board and try each digit" without precomputing constraint sets shows weak fluency. A candidate who proposes bitsets, MRV (minimum remaining values) ordering, and forward propagation is signaling staff-level CSP intuition.

The Core Insight#

The decision tree iterates over EMPTY CELLS in order. At each empty cell, branches correspond to digits 1 through 9. A branch is legal exactly when the digit does not appear yet in the cell's row, its column, or its 3x3 box. After placing, recurse to the next empty cell. On dead-end, undo the placement and try the next digit.

To avoid scanning the row, column, and box on every check, precompute three bitsets at start:

• row[r]: bit d set if digit d is already in row r.
• col[c]: bit d set if digit d is already in column c.
• box[(r // 3) * 3 + c // 3]: bit d set if digit d is already in that 3x3 box.

Legality of placing digit d at (r, c) is then a single OR-and-AND test, and updating state on choose / unchoose is a single XOR. This turns each cell decision into a constant-time operation.

The MRV heuristic supercharges this: instead of always picking the next empty cell in scan order, pick the empty cell with the FEWEST legal candidates. Cells with one legal candidate force the value (zero branching), and cells with zero legal candidates fail fast (instant prune). This single change makes Sudoku solving roughly 100x faster on hard puzzles and is the trick used by Norvig's famous solver.

A practical 9x9 board has 81 cells with at most 9 branches per empty cell, so the worst-case search tree has up to 9^81 nodes, but with bitsets and MRV the actual exploration on standard puzzles is well under 10000 nodes.

Visual Dry Run#

Consider a partial board where the empty cell (0, 2) has constraints excluding 5, 3, 7 (row), 9, 8, 4 (column), and 5, 3, 6 (box). The legal digits are {1, 2}.

solve()
  next = (0,2)
  legal = {1, 2}
  try 1:
    set (0,2)=1, mark row[0], col[2], box[0]
    solve()
      next = (0,5)
      legal = {2, 4, 8} ...
        ... eventually dead-end
    unmark, restore (0,2)='.'
  try 2:
    set (0,2)=2, mark row[0], col[2], box[0]
    solve()
      ... succeeds, propagates to leaf -> RECORD
    return True

With MRV the next chosen cell may not be (0, 2) but instead any empty cell with the smallest legal-candidate count — typically a cell with one or two options that forces decisive progress.

Solution (Optimal)#

Python — bitset-based with MRV-friendly structure#

def solveSudoku(board: list[list[str]]) -> None:
    rows = [0] * 9
    cols = [0] * 9
    boxes = [0] * 9
    empties: list[tuple[int, int]] = []
 
    # Precompute initial bitsets and the list of empty cells
    for r in range(9):
        for c in range(9):
            ch = board[r][c]
            if ch == '.':
                empties.append((r, c))
            else:
                d = int(ch)
                bit = 1 << d
                rows[r] |= bit
                cols[c] |= bit
                boxes[(r // 3) * 3 + c // 3] |= bit
 
    def bt(idx: int) -> bool:
        # Base case: all empty cells filled -> solution found
        if idx == len(empties):
            return True
 
        r, c = empties[idx]
        b = (r // 3) * 3 + c // 3
        used = rows[r] | cols[c] | boxes[b]
 
        # Try each digit 1..9 not yet used
        for d in range(1, 10):
            bit = 1 << d
            if used & bit:
                continue                # constraint violated
            # Choose
            board[r][c] = str(d)
            rows[r] |= bit; cols[c] |= bit; boxes[b] |= bit
            # Explore
            if bt(idx + 1):
                return True             # propagate success
            # Unchoose
            rows[r] ^= bit; cols[c] ^= bit; boxes[b] ^= bit
            board[r][c] = '.'
 
        return False
 
    bt(0)

JavaScript#

function solveSudoku(board) {
    const rows = new Array(9).fill(0);
    const cols = new Array(9).fill(0);
    const boxes = new Array(9).fill(0);
    const empties = [];
 
    for (let r = 0; r < 9; r++) {
        for (let c = 0; c < 9; c++) {
            const ch = board[r][c];
            if (ch === '.') {
                empties.push([r, c]);
            } else {
                const d = parseInt(ch, 10);
                const bit = 1 << d;
                rows[r] |= bit;
                cols[c] |= bit;
                boxes[Math.floor(r / 3) * 3 + Math.floor(c / 3)] |= bit;
            }
        }
    }
 
    function bt(idx) {
        if (idx === empties.length) return true;
        const [r, c] = empties[idx];
        const b = Math.floor(r / 3) * 3 + Math.floor(c / 3);
        const used = rows[r] | cols[c] | boxes[b];
 
        for (let d = 1; d <= 9; d++) {
            const bit = 1 << d;
            if (used & bit) continue;
            board[r][c] = String(d);
            rows[r] |= bit; cols[c] |= bit; boxes[b] |= bit;
            if (bt(idx + 1)) return true;
            rows[r] ^= bit; cols[c] ^= bit; boxes[b] ^= bit;
            board[r][c] = '.';
        }
        return false;
    }
    bt(0);
}

Complexity#

M is typically 40 to 60 for normal puzzles. Bitsets reduce per-cell work to O(1).

Common Mistakes#

1. Scanning row, column, and box on each digit attempt. This makes each placement O(27) instead of O(1) — a real performance hit for hard puzzles. Always precompute the three bitsets.
2. Off-by-one in box index. The formula is (r // 3) * 3 + (c // 3), NOT r // 3 + c // 3. The latter collides three different boxes onto one index.
3. Returning a copy instead of mutating in place. LC 37 expects in-place mutation; returning a new board fails the judge.
4. Forgetting to propagate the success boolean. Backtracking with a single solution must short-circuit on the first success — propagate True up the stack and stop. Without this, you keep searching after finding the answer.
5. Iterating cell positions inside the recursive loop. The cell iteration belongs to the OUTER scan; inside the loop you only iterate digits. Mixing them produces wrong results.
6. Using int(d) to update bit mistakenly with bit = d instead of bit = 1 less-than-less-than d. A digit's bit position must be 1 less-than-less-than d, otherwise constraint masks become meaningless.

Interview Tips#

• State the CSP framing up front. "Three constraint sets — rows, columns, boxes — give O(1) legality checks." Interviewer immediately knows you have done CSPs before.
• Bring up MRV when asked to optimize. "Min remaining values picks the most constrained cell first; combined with bitsets it solves the world's hardest puzzles in milliseconds."
• Mention forward checking and arc consistency as natural extensions. These are textbook CSP techniques and demonstrate breadth.
• Walk through one cell. Pick any empty cell, compute used = rows | cols | boxes, and explain why (used and bit) == 0 is the legality test.
• Return type matters. The Python signature returns None (mutates board); the JS signature mutates the array in place. Don't return a new structure.

Follow-up Questions#

• Validate a Sudoku board (LC 36). Use the same three bitsets and one pass; if any bit is already set when seen again, it's invalid.
• N x N generalized Sudoku. Replace 9 with n and 3 with sqrt(n). The bitset approach generalizes if n less-than-or-equal 64 (fits in a long).
• Sudoku with some unique-solution constraint. Continue searching after first hit; if a second solution is found, return ambiguous.
• Killer Sudoku / Diagonal Sudoku. Add new constraint sets (cage sums, the two main diagonals) — same pattern, more bitsets.
• Difficulty rating. Count nodes explored during solve; correlate with human difficulty.

Key Takeaways#

• Sudoku is the textbook Constraint Satisfaction Problem and uses a row, column, and 3x3 box state representation tracked as three bitsets.
• Precomputing constraints turns each placement into an O(1) check and a single XOR on the way back up — orders of magnitude faster than re-scanning.
• The empty-cell list with index pointer is cleaner than re-scanning for the next dot inside recursion and supports MRV cleanly.
• MRV (minimum remaining values) heuristic combined with bitsets reduces explored nodes by 100x or more on hard puzzles.
• Always propagate the success boolean to short-circuit once a unique solution is found — Sudoku is single-solution by problem statement.
• The bitset plus backtracking template carries directly to N-Queens, graph coloring, exam scheduling, and miniature SAT solvers in interview follow-ups.