Sudoku Solver: Backtracking with Constraint Propagation

Sudoku Solver (LeetCode 37) is the canonical backtracking problem that tests constraint propagation, pruning, and disciplined state management. It appears at Google, Facebook, and Microsoft as a medium-to-hard coding problem and is the template for all constraint satisfaction backtracking problems.

Problem

Fill in a 9×9 Sudoku board so that every row, column, and 3×3 box contains the digits 1-9 exactly once. Empty cells are marked with ‘.’.

Backtracking Solution

def solve_sudoku(board: list[list[str]]) -> None:
    """
    Modifies board in place. Backtracking with constraint checking.
    Time: O(9^m) where m is number of empty cells. Space: O(m) recursion stack.
    """
    rows = [set() for _ in range(9)]
    cols = [set() for _ in range(9)]
    boxes = [set() for _ in range(9)]
    empty = []

    # Initialize constraint sets from pre-filled cells
    for r in range(9):
        for c in range(9):
            val = board[r][c]
            if val == '.':
                empty.append((r, c))
            else:
                n = int(val)
                rows[r].add(n)
                cols[c].add(n)
                boxes[(r // 3) * 3 + c // 3].add(n)

    def backtrack(idx):
        if idx == len(empty):
            return True  # All empty cells filled — solution found

        r, c = empty[idx]
        box_id = (r // 3) * 3 + c // 3

        for num in range(1, 10):
            if num in rows[r] or num in cols[c] or num in boxes[box_id]:
                continue  # num already used in this row/col/box

            # Place num
            board[r][c] = str(num)
            rows[r].add(num)
            cols[c].add(num)
            boxes[box_id].add(num)

            if backtrack(idx + 1):
                return True

            # Undo placement (backtrack)
            board[r][c] = '.'
            rows[r].remove(num)
            cols[c].remove(num)
            boxes[box_id].remove(num)

        return False  # No valid number found — backtrack further

    backtrack(0)

Why Constraint Sets Speed Things Up

The naive approach checks all cells in the row/column/box on each candidate test — O(9) per check. Pre-building sets makes each check O(1). For 9^m total possibilities this constant factor matters enormously.

Most Constrained Variable Heuristic (MRV)

Always fill the cell with the fewest valid candidates first. This prunes the search tree aggressively:

def solve_sudoku_mrv(board: list[list[str]]) -> None:
    """
    Solve with Minimum Remaining Values (MRV) heuristic.
    Choose the empty cell with the fewest valid options first.
    In practice this solves hard puzzles orders of magnitude faster.
    """
    rows = [set() for _ in range(9)]
    cols = [set() for _ in range(9)]
    boxes = [set() for _ in range(9)]
    empty = set()

    for r in range(9):
        for c in range(9):
            val = board[r][c]
            if val == '.':
                empty.add((r, c))
            else:
                n = int(val)
                rows[r].add(n)
                cols[c].add(n)
                boxes[(r // 3) * 3 + c // 3].add(n)

    def get_candidates(r, c):
        box_id = (r // 3) * 3 + c // 3
        return set(range(1, 10)) - rows[r] - cols[c] - boxes[box_id]

    def backtrack():
        if not empty:
            return True

        # MRV: pick cell with fewest valid candidates
        r, c = min(empty, key=lambda pos: len(get_candidates(*pos)))
        candidates = get_candidates(r, c)

        if not candidates:
            return False  # Dead end — no valid number for this cell

        box_id = (r // 3) * 3 + c // 3
        empty.remove((r, c))

        for num in candidates:
            board[r][c] = str(num)
            rows[r].add(num)
            cols[c].add(num)
            boxes[box_id].add(num)

            if backtrack():
                return True

            board[r][c] = '.'
            rows[r].remove(num)
            cols[c].remove(num)
            boxes[box_id].remove(num)

        empty.add((r, c))
        return False

    backtrack()

Constraint Propagation (Arc Consistency)

Before backtracking, propagate constraints: if a cell has only one valid candidate, fill it immediately and propagate the constraint to neighboring cells. This alone solves most “easy” and “medium” Sudoku puzzles without any backtracking:

def constraint_propagation(board: list[list[str]]) -> bool:
    """
    Fill in cells with only one valid candidate. Returns False if contradiction found.
    Run before backtracking to reduce search space.
    """
    changed = True
    while changed:
        changed = False
        for r in range(9):
            for c in range(9):
                if board[r][c] != '.':
                    continue

                # Collect numbers used in same row, col, box
                used = set()
                for i in range(9):
                    if board[r][i] != '.': used.add(int(board[r][i]))
                    if board[i][c] != '.': used.add(int(board[i][c]))

                br, bc = (r // 3) * 3, (c // 3) * 3
                for dr in range(3):
                    for dc in range(3):
                        v = board[br + dr][bc + dc]
                        if v != '.': used.add(int(v))

                candidates = set(range(1, 10)) - used
                if len(candidates) == 0:
                    return False  # Contradiction
                if len(candidates) == 1:
                    board[r][c] = str(candidates.pop())
                    changed = True

    return True

The Full Solver

def solve_complete(board):
    """Constraint propagation first, then MRV backtracking."""
    if not constraint_propagation(board):
        return False
    solve_sudoku_mrv(board)
    return True

Complexity Analysis

Worst case: O(9^m) where m = number of empty cells (up to 81). For a completely empty board: 9^81 ≈ 10^77 — impossible without heuristics.
With MRV + constraint propagation: In practice, most valid puzzles solve in microseconds. The branching factor drops dramatically because most cells have only 1-3 candidates at each step.

The Backtracking Template

Sudoku demonstrates the complete production backtracking pattern:

State representation: Board + constraint sets (rows/cols/boxes)
Constraint checking: O(1) with pre-built sets
Variable ordering: MRV picks the most constrained cell first
Value ordering: Try candidates in order (could also try least-constraining value first)
Pruning: Constraint propagation eliminates dead ends before entering recursion

The same five-component structure solves N-Queens, graph coloring, exam scheduling, and register allocation in compilers.

Practice Problems

LeetCode 37: Sudoku Solver
LeetCode 36: Valid Sudoku (just validation, no solving)
LeetCode 51-52: N-Queens (same backtracking template)
LeetCode 79: Word Search (backtracking on a grid)