Sudoku Solver
Fill a 9×9 sudoku in place by backtracking: try the digits each empty cell allows, recurse, and erase the digit when the recursion hits a dead end.
Problem Understanding
Sudoku Solver (LeetCode 37): fill the empty cells (.) of a 9×9 board so that every row, every column and every 3×3 box contains the digits 1 to 9 exactly once. Change the board in place. The input is guaranteed to have exactly one solution.
The Intuition: Guess, Check, Undo
You cannot know the right digit for most cells up front, so guess, and take the guess back when it leads nowhere.
- Record what is used. One set per row, column and box holds the digits already there. A digit fits a cell when none of its three sets has it.
- Fill the empty cells in order. At each one, place the smallest digit that fits and move to the next cell.
- Back up on a dead end. If no digit fits a cell, an earlier guess was wrong. Return false; the caller erases its digit and tries its next one.
It is the same choose, explore, unchoose loop as N-Queens, and the three sets are the ones Valid Sudoku uses to check a board.
Interactive Walkthrough
BLUE = PLACED
RECORD USED DIGITS
Cell
:
Filled
0/10
Erased
0
Record the digits each row, column and box already uses. 10 empty cells to fill, in reading order
Next
1, 2, 3, 4, 5, 6 and 7 are already used. 8 fits at row 0, column 5: place it and move on
Board
The default board has ten empty cells, and the top row forces the solver to back up seven times before it finds the right digits. Blue digits are the solver's guesses; red is a dead end. LeetCode example runs the full puzzle: 12,524 steps, so drag the slider.
Dry Run Table
Input: the default board, ten empty cells. Row 0 is 5 3 4 6 7 . . . ..
| Steps | What happens |
|---|---|
| 1 | Record the used digits; 10 empty cells |
| 2 to 4 | (0,5) = 8, (0,6) = 1, (0,7) = 2 |
| 5 | (0,8): every digit is used. Dead end |
| 6 to 7 | Erase the 2 at (0,7); 9 fits there instead |
| 8 to 11 | (0,8) = 2, (2,0) = 1, (3,7) = 2, (4,1) = 2 |
| 12 to 23 | (4,7) has no digit. The solver backs up cell by cell, all the way to (0,6) |
| 24 | (0,6) = 9 instead of 1 |
| 25 to 32 | Every remaining cell takes the first digit that fits |
| 33 | Solved: row 0 is 5 3 4 6 7 8 9 1 2 |
The Solution Template
Used-digit sets (or boolean tables) for rows, columns and boxes, a list of empty cells, and a recursive backtrack that returns true once the last cell is filled.
Sudoku Solver Code
1var solveSudoku = function(board) {2 const rows = Array.from({ length: 9 }, () => new Set());3 const cols = Array.from({ length: 9 }, () => new Set());4 const boxes = Array.from({ length: 9 }, () => new Set());5 const empties = [];6 for (let r = 0; r < 9; r++) {7 for (let c = 0; c < 9; c++) {8 const d = board[r][c];9 if (d === '.') {10 empties.push([r, c]);11 } else {12 rows[r].add(d);13 cols[c].add(d);14 boxes[Math.floor(r / 3) * 3 + Math.floor(c / 3)].add(d);15 }16 }17 }1819 const backtrack = (i) => {20 if (i === empties.length) {21 return true;22 }23 const [r, c] = empties[i];24 const b = Math.floor(r / 3) * 3 + Math.floor(c / 3);25 for (const d of '123456789') {26 if (rows[r].has(d) || cols[c].has(d) || boxes[b].has(d)) {27 continue;28 }29 board[r][c] = d;30 rows[r].add(d); cols[c].add(d); boxes[b].add(d);31 if (backtrack(i + 1)) {32 return true;33 }34 board[r][c] = '.';35 rows[r].delete(d); cols[c].delete(d); boxes[b].delete(d);36 }37 return false;38 };3940 backtrack(0);41};
Edge Cases & Common Mistakes
- Forgetting to undo the sets: erasing the digit from the board but not from its row, column and box sets makes later checks wrong.
- Not stopping at the solution: without the true return, every caller erases its digit on the way out and the board ends up empty again.
- Box index: the box of (r, c) is (r / 3) * 3 + c / 3 with integer division.
- Rescanning to find the next empty cell: list the empty cells once; scanning the board on every call adds up to 81 checks per step.
- Static state in C or Java: reset the used-digit tables and the empty list on every call, because LeetCode runs several boards in one process.
Summary
Record the digits each row, column and box uses, then fill the empty cells in order: place the smallest digit that fits, recurse, and erase it if the recursion fails. Stop at the first full board. O(9^m) time in the worst case for m empty cells, O(m) recursion depth.
More practice: DSA interview questions with answers · patterns cheat sheet