• board.length == 9 and board[i].length == 9
• board[i][j] is a digit character '1'–'9' or the character '.'
• The given board is valid — no conflicts exist among the pre-filled digits
• Exactly one solution is guaranteed to exist
• The board must be modified in place rather than returned

This is the hardest problem in the section, and it introduces one structural idea the earlier problems never needed: the search stops at the first complete answer rather than collecting all of them. That changes the shape of the recursion, so it is worth handling deliberately.

A puzzle with 50 empty cells and 9 candidates each has 9⁵⁰ possible fillings — a number with 48 digits. Enumerating them and checking each is not slow, it is impossible.

for assignment in all_9_to_the_50_fillings:
    if valid(assignment):
        return assignment

Yet real solvers finish instantly, and the reason is entirely pruning. Almost every partial filling is already illegal after a handful of placements, and detecting that immediately eliminates the entire subtree below it.

Concretely: place a 5 somewhere and then another 5 in the same row. That board is dead, and every one of the 9⁴⁸ completions beneath it is dead with it. Checking after each placement rather than at the end is what collapses an impossible search into a fast one. The bound stays 9^m; the actual work does not resemble it.

Every cell sits at the intersection of three regions, and a digit placed there is claimed in all three at once.

Its row — nine cells sharing the same first index. Its column — nine cells sharing the second. Its box — the 3 × 3 block containing it.

Identifying the box from the coordinates is the one piece of arithmetic worth deriving rather than memorising. Integer-dividing a coordinate by 3 collapses 0, 1, 2 to 0; 3, 4, 5 to 1; and 6, 7, 8 to 2 — so row // 3 and col // 3 give the box's grid position. Flattening those two into a single index 0–8 is (row // 3) * 3 + col // 3.

Check it: cell (4,7) gives 4//3 = 1 and 7//3 = 2, so box 1×3 + 2 = 5, the middle-right block. Correct.

Every earlier problem in this section collected all answers, so the recursion returned nothing — it appended to a shared result list and unwound.

Here only one solution exists and it is wanted as soon as it is found. So the recursion returns true or false, meaning "did this branch lead to a complete board?" A caller that receives true stops immediately and propagates it; a caller that receives false undoes its placement and tries the next digit.

That is what turns backtracking into a search for something rather than an enumeration of everything, and it is the reusable idea here.

def solve_sudoku(board):
    def box_index(r, c):
        return (r // 3) * 3 + c // 3

    def is_valid(r, c, ch):
        for i in range(9):
            if board[r][i] == ch:                     # row conflict
                return False
            if board[i][c] == ch:                     # column conflict
                return False
            br, bc = 3 * (r // 3) + i // 3, 3 * (c // 3) + i % 3
            if board[br][bc] == ch:                   # box conflict
                return False
        return True

    def solve():
        for r in range(9):
            for c in range(9):
                if board[r][c] != '.':
                    continue                          # already filled

                for ch in "123456789":
                    if not is_valid(r, c, ch):
                        continue                      # PRUNE before recursing

                    board[r][c] = ch                  # CHOOSE
                    if solve():                       # EXPLORE
                        return True                   # solved — stop everything
                    board[r][c] = '.'                 # UN-CHOOSE

                return False        # no digit worked here: this branch is dead
        return True                 # no empty cell found: the board is complete

    solve()

is_valid scans 27 cells per call, and it is called up to nine times per cell at every level. It can be reduced to three lookups by maintaining occupancy sets and updating them alongside the board.

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

for r in range(9):                                    # seed from the given digits
    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)

# then, in the digit loop:
b = (r // 3) * 3 + c // 3
if ch in rows[r] or ch in cols[c] or ch in boxes[b]:
    continue                                          # three lookups, no scanning

The sets must be updated on every choose and reverted on every un-choose, exactly like the board itself. It does not change the asymptotic bound — that is dominated by the branching — but it removes a factor of 27 from the constant, which is very noticeable on hard puzzles.

A stronger optimisation worth naming even if not implemented: instead of filling cells in scan order, always pick the empty cell with the fewest legal candidates. Choosing the most constrained cell first means branching 1 or 2 ways instead of 9, which prunes far harder near the root. That heuristic is called minimum remaining values and it is what makes industrial constraint solvers fast.

Take a board whose first empty cell is (0,2), with row 0 reading 5 3 . . 7 . . . .

The two directions of propagation are the whole mechanism: false travels up and triggers undo; true travels up and freezes everything.

Sudoku and N-Queens are both constraint satisfaction problems, and they share the structure: assign values to variables such that a set of rules holds, with the search pruned by checking rules at each assignment. The differences are instructive. N-Queens folded the row and column constraints into its representation and had to check only diagonals; Sudoku cannot do that, since its three constraints are genuinely independent, so all three are checked explicitly.

The recursion shape is the transferable piece. Compare the two termination styles used across this section:

Recognition signals: fill a grid subject to rules, assign values without conflicts, schedule with exclusions, colour a map, solve a puzzle. If the question wants one solution, return a boolean. If it wants all of them, collect and keep going.

Train the reflex: in a search where most states are illegal, the constraint check is the algorithm. Test it at the earliest possible moment, make the test cheap, and let a failure high in the tree delete everything beneath it.