Sudoku Solver — Solution

Problem

Given a partially filled 9×9 Sudoku grid, fill in every empty cell (marked as '.') so that each row, each column, and each of the nine 3×3 sub-boxes contains every digit from 1 to 9 exactly once. The puzzle is guaranteed to have a unique solution.

• Input: board = [["5","3",".",".","7",".",".",".","."],["6",".",".","1","9","5",".",".","."],... ]
• Output: The same board mutated in-place with all cells filled.
• Explanation: Every row, column, and 3×3 box now contains the digits 1–9 with no repeats.

Counter-example — placing "1" in board[0][2] is invalid because "1" already appears in column 2 at board[2][2].

Intuition

The problem is a classic constraint-satisfaction puzzle. At each empty cell you have at most nine choices, but most are immediately ruled out by the row, column, and box already containing that digit. Backtracking exploits this: place a digit, recurse deeper, and if you ever reach a dead end simply undo the placement and try the next digit. The three constraint checks prune the search space so aggressively that even a 9×9 grid solves in milliseconds.

Solution — Constraint-Checked Backtracking

Scan the board for the first empty cell and try each digit 1–9. A digit is legal if it doesn't already appear in the same row, column, or 3×3 box. Place it, recurse, and undo if no solution follows. When every cell is filled the recursion unwinds with a success signal.

1. Walk every cell left-to-right, top-to-bottom until an empty cell ('.') is found.
2. If no empty cell exists, the board is complete — return True / true.
3. For each candidate digit '1' through '9':
   • Run three O(9) checks: scan the row, scan the column, and scan the 3×3 box.
   • If all pass, write the digit and recurse.
   • If recursion returns success, propagate it immediately without undoing.
   • Otherwise, restore '.' before moving to the next candidate.
4. If all nine candidates fail for this cell, return False / false to trigger backtracking in the caller.

1def solveSudoku(board: list[list[str]]) -> None:
2    def is_valid(row: int, col: int, digit: str) -> bool:
3        for i in range(9):
4            if board[row][i] == digit:   # same digit already in this row
5                return False
6            if board[i][col] == digit:   # same digit already in this column
7                return False
8            # map linear index i into the 3×3 box that contains (row, col)
9            box_row = 3 * (row // 3) + i // 3
10            box_col = 3 * (col // 3) + i % 3
11            if board[box_row][box_col] == digit:
12                return False
13        return True
14
15    def backtrack() -> bool:
16        for row in range(9):
17            for col in range(9):
18                if board[row][col] != '.':
19                    continue
20                for digit in '123456789':
21                    if is_valid(row, col, digit):
22                        board[row][col] = digit
23                        if backtrack():          # solution found deeper in the tree
24                            return True
25                        board[row][col] = '.'    # undo before trying next digit
26                return False  # no digit worked — signal caller to backtrack
27        return True  # no empty cell found; board is solved
28
29    backtrack()

Time: O(9^m) where m is the number of empty cells. The three constraint checks cut the branching factor far below 9 in practice, so real puzzles finish in milliseconds.

Space: O(m) for the recursion stack depth — at most 81 frames for a fully empty board, effectively O(1).

Complexity Summary

Common Mistakes

• Forgetting the undo step. Without board[row][col] = '.' after a failed recursion, wrong placements persist and poison every subsequent branch. The undo is what makes backtracking correct.
• Wrong 3×3 box indexing. A common mistake is computing the box as row - row % 3 and col - col % 3, which gives the top-left corner but requires adding i // 3 and i % 3 to visit all nine cells. The formula 3 * (row // 3) + i // 3 combines both steps cleanly in one pass.
• Returning False after the outer for digit loop instead of inside the cell block. The return False must appear immediately after the digit loop for the current empty cell — not after the outer row/col loops — otherwise the function exits after the first empty cell no matter what.
• Validating with the entire board instead of early exit. Checking all 81 cells for each placement is O(81) per call. The single-loop trick that checks row i, column i, and box cell i in one pass keeps validation at O(9).
• Mutating the input without realising the function signature requires in-place modification. Some implementations copy the board, then lose the result because the caller reads the original. The board must be mutated directly.

Related Problems

• valid-sudoku — validates a board using the same row/column/box constraints; understanding this first makes the solver much clearer.
• n-queens — identical backtracking structure: place a queen, check conflicts, recurse, undo.
• word-search — backtracking on a 2D grid where each step is validated against the current path.
• combination-sum-ii — backtracking with pruning; same try/recurse/undo pattern.
• permutations — foundational backtracking: enumerate all orderings by choosing, recursing, and unchoosing.