Sudoku Solver (LeetCode 37)
Fill in every empty cell of a 9x9 Sudoku board so the finished board is a valid solution.
A board is valid when, in every row, in every column, and in each of the nine 3x3 sub-boxes, the digits 1 through 9 each appear exactly once.
Empty cells are marked with the '.' character.
Worked Examples
board = [["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"]][["5","3","4","6","7","8","9","1","2"],["6","7","2","1","9","5","3","4","8"],["1","9","8","3","4","2","5","6","7"],["8","5","9","7","6","1","4","2","3"],["4","2","6","8","5","3","7","9","1"],["7","1","3","9","2","4","8","5","6"],["9","6","1","5","3","7","2","8","4"],["2","8","7","4","1","9","6","3","5"],["3","4","5","2","8","6","1","7","9"]]⚖️Formal Constraints & Bounds
board.length == 9board[i].length == 9board[i][j]is a digit or'.'It is guaranteed that the input board has only one solution
Core Insight
Scanning for the next empty cell and validating a candidate digit against its row, column, and 3x3 box in O(1)-per-check (bounded by 27 cells) lets simple depth-first backtracking prune almost the entire search space before it ever needs to be explored.
Real-World Scenario & Production Applications
Constraint-satisfaction puzzle solvers, automated exam/room scheduling with row/column/group exclusivity rules, and register allocation where conflicting resources cannot share a slot.
Subproblems & Recurrence Decomposition3 Phases
Scan the 9x9 grid row by row for the first cell still marked . -- that is the next decision point for the backtracking search.
for r in range(9):
for c in range(9):
if board[r][c] == ".":
# this is the next cell to fillStep-by-Step Execution Trace Table
| Step | Empty Cell (r, c) | Candidate Digit d | Row / Col / Box Validity Check | Action Taken | Board Mutation | Backtrack Trigger |
|---|---|---|---|---|---|---|
| 1 | (0, 2) | '1'..'3' | Conflicts with existing row/box | Skip | None | Prune invalid branches |
| 2 | (0, 2) | '4' | Row 0 clear, Col 2 clear, Box (0,0) clear | Place '4' | board[0][2] = '4' | Recurse to next empty cell |
| 3 | (4, 4) | '5' | Row 4 clear, Col 4 clear, Box (3,3) clear | Place '5' | board[4][4] = '5' | Recurse to next empty cell |
| 4 | (8, 8) | '9' | Row 8 clear, Col 8 clear, Box (6,6) clear | Place '9' | board[8][8] = '9' | Recurse |
| 5 | End | — | No empty cells remaining | ✅ Solved | Return True | Fast bubble-up exit |
board = [["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"]][["5","3","4","6","7","8","9","1","2"],["6","7","2","1","9","5","3","4","8"],["1","9","8","3","4","2","5","6","7"],["8","5","9","7","6","1","4","2","3"],["4","2","6","8","5","3","7","9","1"],["7","1","3","9","2","4","8","5","6"],["9","6","1","5","3","7","2","8","4"],["2","8","7","4","1","9","6","3","5"],["3","4","5","2","8","6","1","7","9"]]| Step | Empty Cell (r, c) | Candidate Digit d | Row / Col / Box Validity Check | Action Taken | Board Mutation | Backtrack Trigger |
|---|---|---|---|---|---|---|
| 1 | (0, 2) | '1'..'3' | Conflicts with existing row/box | Skip | None | Prune invalid branches |
| 2 | (0, 2) | '4' | Row 0 clear, Col 2 clear, Box (0,0) clear | Place '4' | board[0][2] = '4' | Recurse to next empty cell |
| 3 | (4, 4) | '5' | Row 4 clear, Col 4 clear, Box (3,3) clear | Place '5' | board[4][4] = '5' | Recurse to next empty cell |
| 4 | (8, 8) | '9' | Row 8 clear, Col 8 clear, Box (6,6) clear | Place '9' | board[8][8] = '9' | Recurse |
| 5 | End | — | No empty cells remaining | ✅ Solved | Return True | Fast bubble-up exit |
| 1 | for each cell (r, c) of the 9 x 9 board: |
| 2 | if board[r][c] == '.': |
| 3 | for d in '123456789': |
| 4 | if is_valid(r, c, d): |
| 5 | board[r][c] = d |
| 6 | if backtrack(): |
| 7 | return True |
| 8 | board[r][c] = '.' |
| 9 | return False |
| 10 | return True |
Conceptual Narrative
The most iconic "Hard" backtracking problem on the platform: fill a partially-completed 9x9 Sudoku board so every row, column, and 3x3 box contains 1-9 exactly once.
🧭 Conceptual Foundation & Pattern Intuition
Sudoku Solver looks intimidating because a naive brute force would try all 9^81 possible digit fills. But almost every one of those fills is instantly invalid -- the row, column, and box rules are extremely restrictive local constraints. Backtracking exploits this: instead of guessing an entire board at once, decide one empty cell at a time, and the moment a digit violates any constraint, abandon that branch immediately rather than continuing to fill the rest of the board pointlessly.
🏟️ The Analogy: The Crossword Puzzle Editor
Imagine editing a crossword puzzle cell by cell. You don't fill in every square blindly and check the whole grid at the end -- you check each letter the instant you write it, against every word it's currently part of. If a letter breaks a word, you erase it right away and try another, rather than filling the rest of the puzzle around a mistake you already know is wrong. Sudoku Solver works the same way: validate each digit the instant it's placed against its row, column, and box, so an invalid branch is abandoned immediately instead of being searched deeper.
🔑 The Key Idea in the Code
The recursion only ever needs to look 27 cells ahead (9 in the row, 9 in the column, 9 in the box) to reject a bad digit -- so almost the entire 9^81 search space collapses before it is ever explored.
Sudoku: checking only row and column, forgetting the 3x3 box. A board can satisfy every row and column constraint while still repeating a digit inside one 3x3 box. All three checks must pass, every time.
Sudoku: partial or missing undo. Forgetting to reset
board[r][c] = "."after a failed downstream recursion silently corrupts the board for every sibling branch that follows — the bug will not surface until a much later, seemingly unrelated cell fails to solve.Sudoku: off-by-one box-corner math.
3 * (r // 3), 3 * (c // 3)computes the top-left corner of the 3x3 box containing(r, c). A subtly wrong formula (e.g.r // 3, c // 3without the multiply) silently checks the wrong box and produces an invalid "solution."Missing early boolean termination: Not checking the return value of
if solve(board): return True. Failing to propagateTrueupward causes the algorithm to overwrite the correct solution and backtrack back to an empty board.
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
9x9 grid + fill empty cells + row/column/3x3-box uniqueness constraints.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
Invariant: at any point during the search, every already-filled cell still satisfies all three uniqueness constraints -- only the next empty cell is undetermined.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
Re-scanning the constraint sets from scratch for every candidate digit instead of maintaining
O(1)row/col/box lookup sets, which is fine for a single board but wasteful at scale.
The 60-Second Interview Pitch
Say this out loud before you type a single line
"I scan for the first empty cell, then try digits '1' through '9'. A digit is valid only if it doesn't already appear in that row, column, or 3x3 box. I place a valid digit and recurse; if every path from there fails, I reset the cell to '.' and try the next digit. If no digit works, I return False to trigger backtracking one level up. Once no empty cells remain, the board is solved."
Complexity & Mathematical Proof
O(9^E) worst case (E = empty cells), near-instant in practice
Look at the recursion tree: in the absolute worst case each of the E empty cells could have up to 9 candidate digits, giving an upper bound of O(9^E). In practice, row/column/box constraints eliminate the overwhelming majority of candidates at each cell almost immediately, so real 9x9 boards (E <= 81) solve in a small fraction of a second.
O(E) Auxiliary (recursion depth)
Look at our memory allocations: the recursive call stack grows to at most E frames (one per empty cell along the deepest successful path): O(E). The row/column/box validity check itself scans at most 27 cells (9 + 9 + 9): O(1) relative to the fixed 9x9 board size. No extra board copies are made -- the same board is mutated and un-mutated in place.
Derivation Progression
Each empty cell independently offers up to 9 digit candidates before constraint checking.
O(1) Constraint CheckRow, column, and 3x3 box each contribute exactly 9 cells to inspect for a conflict.
Constraint propagation collapses almost the entire branching factor at each cell for well-posed (uniquely solvable) puzzles.
Variable Definitions
Number of empty ('.') cells that must be filled
Memory Architecture & Bounds
O(E) Recursion frames bounded by number of empty cells
O(1) No extra board copies -- in-place mutate/undo
O(1) Board is solved in-place; no separate output structure
Boundary Best / Worst Cases
if the board already has zero empty cells.
Near-instant for real, uniquely-solvable puzzles due to aggressive constraint pruning.
theoretical bound for E empty cells (never observed in practice for valid puzzles).
Decision & State-Space Search Tree
Senior SWE Deconstruction & Hardware Caveats
Triggers: "solve 9x9 Sudoku puzzle". Exact constraint satisfaction with early exit: we only need to find ONE valid solution. Returning a boolean flag unwinds the recursion stack immediately without undoing the valid board state!
Board . Fixed problem domain.
Returning boolean: when the board is solved, returning True preserves the solution. Backtracking only occurs if all digits fail.
Sudoku Solver (LeetCode 37)
Fill in every empty cell of a 9x9 Sudoku board so the finished board is a valid solution.
A board is valid when, in every row, in every column, and in each of the nine 3x3 sub-boxes, the digits 1 through 9 each appear exactly once.
Empty cells are marked with the '.' character.
Worked Examples
board = [["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"]][["5","3","4","6","7","8","9","1","2"],["6","7","2","1","9","5","3","4","8"],["1","9","8","3","4","2","5","6","7"],["8","5","9","7","6","1","4","2","3"],["4","2","6","8","5","3","7","9","1"],["7","1","3","9","2","4","8","5","6"],["9","6","1","5","3","7","2","8","4"],["2","8","7","4","1","9","6","3","5"],["3","4","5","2","8","6","1","7","9"]]⚖️Formal Constraints & Bounds
board.length == 9board[i].length == 9board[i][j]is a digit or'.'It is guaranteed that the input board has only one solution
Core Insight
Scanning for the next empty cell and validating a candidate digit against its row, column, and 3x3 box in O(1)-per-check (bounded by 27 cells) lets simple depth-first backtracking prune almost the entire search space before it ever needs to be explored.
Real-World Scenario & Production Applications
Constraint-satisfaction puzzle solvers, automated exam/room scheduling with row/column/group exclusivity rules, and register allocation where conflicting resources cannot share a slot.
Subproblems & Recurrence Decomposition3 Phases
Scan the 9x9 grid row by row for the first cell still marked . -- that is the next decision point for the backtracking search.
for r in range(9):
for c in range(9):
if board[r][c] == ".":
# this is the next cell to fillStep-by-Step Execution Trace Table
| Step | Empty Cell (r, c) | Candidate Digit d | Row / Col / Box Validity Check | Action Taken | Board Mutation | Backtrack Trigger |
|---|---|---|---|---|---|---|
| 1 | (0, 2) | '1'..'3' | Conflicts with existing row/box | Skip | None | Prune invalid branches |
| 2 | (0, 2) | '4' | Row 0 clear, Col 2 clear, Box (0,0) clear | Place '4' | board[0][2] = '4' | Recurse to next empty cell |
| 3 | (4, 4) | '5' | Row 4 clear, Col 4 clear, Box (3,3) clear | Place '5' | board[4][4] = '5' | Recurse to next empty cell |
| 4 | (8, 8) | '9' | Row 8 clear, Col 8 clear, Box (6,6) clear | Place '9' | board[8][8] = '9' | Recurse |
| 5 | End | — | No empty cells remaining | ✅ Solved | Return True | Fast bubble-up exit |
board = [["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"]][["5","3","4","6","7","8","9","1","2"],["6","7","2","1","9","5","3","4","8"],["1","9","8","3","4","2","5","6","7"],["8","5","9","7","6","1","4","2","3"],["4","2","6","8","5","3","7","9","1"],["7","1","3","9","2","4","8","5","6"],["9","6","1","5","3","7","2","8","4"],["2","8","7","4","1","9","6","3","5"],["3","4","5","2","8","6","1","7","9"]]| Step | Empty Cell (r, c) | Candidate Digit d | Row / Col / Box Validity Check | Action Taken | Board Mutation | Backtrack Trigger |
|---|---|---|---|---|---|---|
| 1 | (0, 2) | '1'..'3' | Conflicts with existing row/box | Skip | None | Prune invalid branches |
| 2 | (0, 2) | '4' | Row 0 clear, Col 2 clear, Box (0,0) clear | Place '4' | board[0][2] = '4' | Recurse to next empty cell |
| 3 | (4, 4) | '5' | Row 4 clear, Col 4 clear, Box (3,3) clear | Place '5' | board[4][4] = '5' | Recurse to next empty cell |
| 4 | (8, 8) | '9' | Row 8 clear, Col 8 clear, Box (6,6) clear | Place '9' | board[8][8] = '9' | Recurse |
| 5 | End | — | No empty cells remaining | ✅ Solved | Return True | Fast bubble-up exit |
| 1 | for each cell (r, c) of the 9 x 9 board: |
| 2 | if board[r][c] == '.': |
| 3 | for d in '123456789': |
| 4 | if is_valid(r, c, d): |
| 5 | board[r][c] = d |
| 6 | if backtrack(): |
| 7 | return True |
| 8 | board[r][c] = '.' |
| 9 | return False |
| 10 | return True |
Conceptual Narrative
The most iconic "Hard" backtracking problem on the platform: fill a partially-completed 9x9 Sudoku board so every row, column, and 3x3 box contains 1-9 exactly once.
🧭 Conceptual Foundation & Pattern Intuition
Sudoku Solver looks intimidating because a naive brute force would try all 9^81 possible digit fills. But almost every one of those fills is instantly invalid -- the row, column, and box rules are extremely restrictive local constraints. Backtracking exploits this: instead of guessing an entire board at once, decide one empty cell at a time, and the moment a digit violates any constraint, abandon that branch immediately rather than continuing to fill the rest of the board pointlessly.
🏟️ The Analogy: The Crossword Puzzle Editor
Imagine editing a crossword puzzle cell by cell. You don't fill in every square blindly and check the whole grid at the end -- you check each letter the instant you write it, against every word it's currently part of. If a letter breaks a word, you erase it right away and try another, rather than filling the rest of the puzzle around a mistake you already know is wrong. Sudoku Solver works the same way: validate each digit the instant it's placed against its row, column, and box, so an invalid branch is abandoned immediately instead of being searched deeper.
🔑 The Key Idea in the Code
The recursion only ever needs to look 27 cells ahead (9 in the row, 9 in the column, 9 in the box) to reject a bad digit -- so almost the entire 9^81 search space collapses before it is ever explored.
Sudoku: checking only row and column, forgetting the 3x3 box. A board can satisfy every row and column constraint while still repeating a digit inside one 3x3 box. All three checks must pass, every time.
Sudoku: partial or missing undo. Forgetting to reset
board[r][c] = "."after a failed downstream recursion silently corrupts the board for every sibling branch that follows — the bug will not surface until a much later, seemingly unrelated cell fails to solve.Sudoku: off-by-one box-corner math.
3 * (r // 3), 3 * (c // 3)computes the top-left corner of the 3x3 box containing(r, c). A subtly wrong formula (e.g.r // 3, c // 3without the multiply) silently checks the wrong box and produces an invalid "solution."Missing early boolean termination: Not checking the return value of
if solve(board): return True. Failing to propagateTrueupward causes the algorithm to overwrite the correct solution and backtrack back to an empty board.
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
9x9 grid + fill empty cells + row/column/3x3-box uniqueness constraints.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
Invariant: at any point during the search, every already-filled cell still satisfies all three uniqueness constraints -- only the next empty cell is undetermined.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
Re-scanning the constraint sets from scratch for every candidate digit instead of maintaining
O(1)row/col/box lookup sets, which is fine for a single board but wasteful at scale.
The 60-Second Interview Pitch
Say this out loud before you type a single line
"I scan for the first empty cell, then try digits '1' through '9'. A digit is valid only if it doesn't already appear in that row, column, or 3x3 box. I place a valid digit and recurse; if every path from there fails, I reset the cell to '.' and try the next digit. If no digit works, I return False to trigger backtracking one level up. Once no empty cells remain, the board is solved."
Complexity & Mathematical Proof
O(9^E) worst case (E = empty cells), near-instant in practice
Look at the recursion tree: in the absolute worst case each of the E empty cells could have up to 9 candidate digits, giving an upper bound of O(9^E). In practice, row/column/box constraints eliminate the overwhelming majority of candidates at each cell almost immediately, so real 9x9 boards (E <= 81) solve in a small fraction of a second.
O(E) Auxiliary (recursion depth)
Look at our memory allocations: the recursive call stack grows to at most E frames (one per empty cell along the deepest successful path): O(E). The row/column/box validity check itself scans at most 27 cells (9 + 9 + 9): O(1) relative to the fixed 9x9 board size. No extra board copies are made -- the same board is mutated and un-mutated in place.
Derivation Progression
Each empty cell independently offers up to 9 digit candidates before constraint checking.
O(1) Constraint CheckRow, column, and 3x3 box each contribute exactly 9 cells to inspect for a conflict.
Constraint propagation collapses almost the entire branching factor at each cell for well-posed (uniquely solvable) puzzles.
Variable Definitions
Number of empty ('.') cells that must be filled
Memory Architecture & Bounds
O(E) Recursion frames bounded by number of empty cells
O(1) No extra board copies -- in-place mutate/undo
O(1) Board is solved in-place; no separate output structure
Boundary Best / Worst Cases
if the board already has zero empty cells.
Near-instant for real, uniquely-solvable puzzles due to aggressive constraint pruning.
theoretical bound for E empty cells (never observed in practice for valid puzzles).
Decision & State-Space Search Tree
Senior SWE Deconstruction & Hardware Caveats
Triggers: "solve 9x9 Sudoku puzzle". Exact constraint satisfaction with early exit: we only need to find ONE valid solution. Returning a boolean flag unwinds the recursion stack immediately without undoing the valid board state!
Board . Fixed problem domain.
Returning boolean: when the board is solved, returning True preserves the solution. Backtracking only occurs if all digits fail.