Sudoku Solver: Backtracking with Constraint Checking

Write a program to solve a Sudoku puzzle by filling the empty cells. A Sudoku solution must satisfy all of the following rules: each of the digits 1 through 9 must occur exactly once in each row, each column, and each of the nine 3x3 sub-boxes of the grid. The input board contains '.' for empty cells.

This is LeetCode 37: Sudoku Solver, and it is the definitive constraint-based backtracking problem. If N-Queens teaches you to combine backtracking with constraint sets, Sudoku Solver takes that same idea and adds a third constraint dimension. Instead of checking columns and two diagonals, you check rows, columns, and 3x3 boxes. The mechanics are identical, but the constraint logic is richer.

Why this problem matters

Sudoku Solver is one of the purest examples of constraint satisfaction via backtracking. Every empty cell is a decision point with up to 9 choices. Most of those choices are invalid, and the whole job of the algorithm is to reject them as early as possible. That pruning skill transfers directly to scheduling problems, graph coloring, configuration search, and any interview question where you must "find a valid assignment under constraints."

The problem also tests whether you can maintain and restore state cleanly. Each placement adds a digit to three constraint sets (row, column, box). Each backtrack step removes it from all three. If you forget to undo even one, the solver produces wrong answers or gets stuck. That discipline of symmetric choose/unchoose is the core of backtracking.

The key insight

Scan the board left to right, top to bottom. When you hit an empty cell, try digits 1 through 9. For each digit, check three constraints:

1. Row: does this digit already appear in the same row?
2. Column: does this digit already appear in the same column?
3. Box: does this digit already appear in the same 3x3 sub-box?

If any constraint is violated, skip that digit. If all three pass, place the digit and recurse to the next empty cell. If the recursion hits a dead end (no digit works for some future cell), backtrack: remove the digit you placed and try the next one.

The box index for a cell at (r, c) is (r // 3) * 3 + c // 3. This maps all nine cells of a 3x3 sub-box to the same index (0 through 8). That formula is the only tricky part. Everything else is the standard backtracking template.

The backtracking solution

def solve_sudoku(board: list[list[str]]) -> None:
    rows = [set() for _ in range(9)]
    cols = [set() for _ in range(9)]
    boxes = [set() for _ in range(9)]

    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(r, c):
        if r == 9:
            return True
        next_r, next_c = (r, c + 1) if c < 8 else (r + 1, 0)

        if board[r][c] != ".":
            return backtrack(next_r, next_c)

        box_id = (r // 3) * 3 + c // 3
        for d in "123456789":
            if d in rows[r] or d in cols[c] or d in boxes[box_id]:
                continue

            board[r][c] = d
            rows[r].add(d)
            cols[c].add(d)
            boxes[box_id].add(d)

            if backtrack(next_r, next_c):
                return True

            board[r][c] = "."
            rows[r].remove(d)
            cols[c].remove(d)
            boxes[box_id].remove(d)

        return False

    backtrack(0, 0)

Let's break this down.

The setup phase scans the board once and populates three arrays of sets: rows[r] holds the digits already present in row r, cols[c] for column c, and boxes[box_id] for the 3x3 box containing the cell. This pre-population turns each constraint check into an O(1) set membership test.

The backtrack function processes cells left to right, top to bottom. When r == 9, every cell has been filled, so return True. If the current cell is already filled (a given digit), skip to the next cell.

For empty cells, the for d in "123456789" loop tries every possible digit. The if guard checks all three constraints. If any constraint is violated, continue to the next digit. This is the pruning that keeps the algorithm fast. Without it, you would explore every possible arrangement of 81 cells.

When all three constraints pass, the choose step places the digit on the board and adds it to the three constraint sets. Then we recurse. If the recursive call returns True, the puzzle is solved and we propagate True upward. If it returns False, the unchoose step removes the digit from the board and all three sets, restoring the state exactly as it was before the attempt.

If no digit 1 through 9 works for this cell, we return False. That False travels up the call stack to the caller, which then undoes its own placement and tries its next digit. This is backtracking in action.

Visual walkthrough

Let's trace the algorithm on a simplified 4x4 mini-Sudoku (digits 1 through 4, 2x2 boxes) to see backtracking happen. The logic is identical to the 9x9 version, just smaller.

The critical moment is Step 5. After placing 2 at (1,0), the solver eventually reaches (3,0) and finds that every digit 1 through 4 conflicts with either the row or the column. No valid digit exists, so it returns False. That False bubbles up, undoing all placements that depended on the choice of 2 at (1,0). The solver then tries 4 at (1,0) instead, and the rest of the board fills without conflict.

This is exactly how the 9x9 solver works, just with more cells and more branching. The three-set constraint check catches conflicts early. The backtracking framework handles dead ends automatically by unwinding to the last decision point and trying the next option.

How the box index works

This formula deserves its own section because it is the part people forget or get wrong.

For a cell at row r, column c, the 3x3 box index is:

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

Here is the box index for every cell in a 9x9 grid:

0 0 0 | 1 1 1 | 2 2 2
0 0 0 | 1 1 1 | 2 2 2
0 0 0 | 1 1 1 | 2 2 2
------+-------+------
3 3 3 | 4 4 4 | 5 5 5
3 3 3 | 4 4 4 | 5 5 5
3 3 3 | 4 4 4 | 5 5 5
------+-------+------
6 6 6 | 7 7 7 | 8 8 8
6 6 6 | 7 7 7 | 8 8 8
6 6 6 | 7 7 7 | 8 8 8

r // 3 gives the box row (0, 1, or 2). Multiplying by 3 and adding c // 3 (the box column) maps each 3x3 region to a unique index 0 through 8. Cell (4, 7) has box index (4 // 3) * 3 + 7 // 3 = 1 * 3 + 2 = 5. Check the grid: row 4, column 7 is indeed in box 5.

Complexity analysis

Time is bounded by O(9^E), where E is the number of empty cells. At each empty cell, you try up to 9 digits. In the worst case (a nearly empty board), E can be close to 81, giving a massive search space. In practice, the constraint checks prune the vast majority of branches, and most well-formed Sudoku puzzles solve in milliseconds. But the theoretical worst case is exponential.

Space is O(E) for the recursion stack, since the DFS goes at most E levels deep. The three arrays of sets use O(81) = O(1) space (fixed board size). If you treat the board size as constant (9x9 is the only size that matters for this problem), both time and space are technically O(1), but that hides the exponential nature of the search.

Edge cases

Before submitting, consider these:

• Already solved board: every cell is filled. The solver should return immediately without modifying anything. The backtrack function handles this because it skips non-empty cells and hits r == 9 without placing any digits.
• Minimal clues: a valid Sudoku puzzle needs at least 17 given digits. With fewer clues, the puzzle might have multiple solutions. The solver finds one valid solution and stops. LeetCode guarantees a unique solution, but your code should not assume that.
• No solution: if the input board has conflicting given digits (like two 5s in the same row), no valid completion exists. The solver returns False from backtrack(0, 0) after exhausting all branches. The board remains in its original state because every placement gets undone during backtracking.

The building blocks

This problem is built on two reusable pieces that CodeBricks drills independently.

1. Constraint-based backtracking

The pattern of checking multiple constraints before committing to a choice:

for candidate in choices:
    if violates_row(candidate):
        continue
    if violates_col(candidate):
        continue
    if violates_box(candidate):
        continue

    apply(candidate)
    if explore():
        return True
    undo(candidate)

return False

In Sudoku, the constraints are three set lookups. In N-Queens, the constraints check column and two diagonals. In graph coloring, the constraint checks neighboring node colors. The shape is always the same: a sequence of guard clauses at the top of the loop that reject invalid candidates before you commit to them. The key difference from unconstrained backtracking (like Subsets) is that most candidates are rejected, and that rejection is what makes the algorithm fast enough to be practical.

2. Validity checking with pre-built lookup sets

Instead of scanning the entire row, column, and box on every placement (O(n) per check), you maintain sets that track which digits are already used:

rows = [set() for _ in range(9)]
cols = [set() for _ in range(9)]
boxes = [set() for _ in range(9)]

Adding a digit to a cell means adding it to three sets. Removing a digit means removing it from three sets. Checking a digit means three O(1) lookups. This optimization is what separates a clean solution from a slow one. The same idea appears in any problem where you need to validate membership repeatedly: maintain a set rather than scanning a list.

Common mistakes

1. Forgetting the box constraint. If you only check rows and columns, your solver will place digits that violate the 3x3 box rule. The output will look partially correct but fail validation.

2. Getting the box index formula wrong. (r // 3) * 3 + c // 3 is the correct formula. A common error is writing r // 3 + c // 3, which maps multiple boxes to the same index. Double-check by computing the index for a cell in each of the nine boxes.

3. Not undoing all three sets on backtrack. The choose step modifies board[r][c], rows[r], cols[c], and boxes[box_id]. The unchoose step must undo all four. Missing any one corrupts the state for sibling branches.

4. Scanning for empty cells inside the loop. Some solutions search for the next empty cell by scanning the entire board at each recursive call. That works but is slower than the approach above, which simply advances (r, c) to (r, c+1) or (r+1, 0). The scan approach adds O(81) overhead per recursive call.

5. Returning the wrong type. LeetCode 37 asks you to modify the board in-place and return nothing. If your backtrack function returns True but you forget to stop recursing, the board may get overwritten during later backtrack steps. Make sure you propagate the True result immediately.

When to use this pattern

Look for these signals:

• The problem asks you to fill in values subject to multiple overlapping constraints
• Each position has a fixed set of candidates, and you need to find which one works
• The constraints involve rows, columns, regions, or other groupings
• The problem guarantees a unique solution or asks for any valid solution

Problems that use the same constrained backtracking pattern:

• N-Queens (LeetCode 51): constrained backtracking with column and diagonal sets
• Valid Sudoku (LeetCode 36): the validation-only version, tests your box index formula
• Word Search (LeetCode 79): grid backtracking with a different constraint (visited cells)
• Combination Sum (LeetCode 39): backtracking where the constraint is a running sum

From understanding to recall

You understand how the three constraint sets work. You see how the box index formula maps cells to boxes, and how the choose-explore-unchoose skeleton drives the search. But can you write the constraint checking and backtracking logic from scratch in an interview?

That is the hard part. The Sudoku Solver has specific details that are easy to mix up under pressure: the box index formula, remembering to undo all three sets, advancing from (r, 8) to (r+1, 0), returning True immediately when the recursion succeeds. These are not conceptual issues. They are recall problems.

Spaced repetition fixes recall. You practice writing the constraint validation and the backtracking framework from memory at increasing intervals. After a few rounds, the pattern is automatic. You see "fill in a grid with constraints" and the code flows out without hesitation.

The constraint-validation and choose-explore-unchoose patterns are two of roughly 60 reusable building blocks that cover hundreds of LeetCode problems. Learning them individually and drilling them with spaced repetition is far more effective than grinding random problems and hoping the patterns stick.

Related posts

• N-Queens - The closest relative. Same constrained backtracking template, but with column and diagonal sets instead of row/column/box sets. If you can solve one, you can solve the other.
• Word Search - Grid backtracking with choose-explore-unchoose. Sudoku Solver adds constraint sets on top of the same skeleton.

CodeBricks breaks Sudoku Solver into its constraint-validation and choose-explore-unchoose building blocks, then drills them independently with spaced repetition. You type the constraint checking and backtracking logic from scratch until the pattern is automatic. When a constraint satisfaction problem shows up in your interview, you do not think about it. You just write it.