Sudoku Solver
Sudoku Solver is LeetCode 37 (Hard). You get a 9 × 9 board of characters: the digits '1' to '9' for given cells and '.' for empty ones. Fill every empty cell so the whole board becomes a valid Sudoku.
- Every row must hold each digit
1–9exactly once. - Every column must hold each digit exactly once.
- Every one of the nine 3 × 3 boxes must hold each digit exactly once.
- Change
boardin place; the function returns nothing.
The sudoku solver LeetCode version guarantees the input has exactly one solution. The board size is fixed, but dozens of cells can be empty, each with up to 9 candidate digits, so blind guessing is hopeless: the solver has to reject a digit the moment it breaks a rule.
Constraints
- board.length == 9
- board[i].length == 9
- board[i][j] is a digit or '.'.
- It is guaranteed that the input board has only one solution.
02
Intuition
A sudoku solver is a search: some empty cell needs a digit, and the rules only say which digits are not allowed. So guess, and undo the guess when it leads nowhere. That is backtracking, and it is how a step by step sudoku solver works: fill cells one at a time, and when a later cell has no legal digit, an earlier guess was wrong.
Two details make it fast enough. A set of used digits for each row, column and box makes every legality check O(1) instead of a 27-cell scan. And the rules prune hard: most digits are rejected immediately, so a real puzzle never comes close to the worst case.
How to spot this pattern
Fill a grid or a sequence under constraints, where a choice can only be judged by what it allows later: backtracking with constraint sets. N-Queens (51) is the same shape with columns and diagonals.
03
Approach
Try it first
Before reading on, decide what three pieces of state let you check a digit at (r, c) without scanning, and how to compute the box number from r and c.
1
Record the given digits
Make rows[9], cols[9], boxes[9] sets. For every filled cell add its digit to all three, and collect every empty cell into a list. The box of (r, c) is (r // 3) * 3 + c // 3.
In the sudoku solver Python code the sets hold the characters '1' to '9' straight from the board. The C++ and Java versions convert with ch - '0' and use boolean arrays indexed by digit instead.
2
Solve the k-th empty cell
k == len(empty)– every cell is filled: returnTrue.- Otherwise take
(r, c) = empty[k]and loopdover'1'to'9', skipping anydfound inrows[r],cols[c]orboxes[b].
3
Place, recurse, undo
- Place: write
don the board and add it to the three sets. - Recurse: if
solve(k + 1)returnsTrue, returnTrueimmediately, leaving the digit in place. - Undo: otherwise erase
dfrom the board and the three sets, and try the next digit.
4
Report a dead end
If the loop ends without success, no digit works in this cell given the earlier guesses. Return False, and the previous cell undoes its guess. Because the puzzle has a solution, the first call eventually returns True.
04
Sudoku Solver solution in Python | C++ | Java
▶1class Solution:
▶2 def solveSudoku(self, board: List[List[str]]) -> None:
▶3 rows = [set() for _ in range(9)]
▶4 cols = [set() for _ in range(9)]
▶5 boxes = [set() for _ in range(9)]
▶6 empty = []
▶7 for r in range(9):
▶8 for c in range(9):
▶9 d = board[r][c]
▶10 if d == ".":
▶11 empty.append((r, c))
▶12 else:
▶13 rows[r].add(d)
▶14 cols[c].add(d)
▶15 boxes[r // 3 * 3 + c // 3].add(d)
▶16
▶17 def solve(k: int) -> bool:
▶18 if k == len(empty):
▶19 return True
▶20 r, c = empty[k]
▶21 b = r // 3 * 3 + c // 3
▶22 for d in "123456789":
▶23 if d in rows[r] or d in cols[c] or d in boxes[b]:
▶24 continue
▶25 board[r][c] = d
▶26 rows[r].add(d)
▶27 cols[c].add(d)
▶28 boxes[b].add(d)
▶29 if solve(k + 1):
▶30 return True
▶31 board[r][c] = "."
▶32 rows[r].remove(d)
▶33 cols[c].remove(d)
▶34 boxes[b].remove(d)
▶35 return False
▶36
▶37 solve(0)
▶1class Solution {
▶2 bool rows[9][10] = {}, cols[9][10] = {}, boxes[9][10] = {};
▶3 vector<pair<int, int>> empty;
▶4
▶5 bool solve(vector<vector<char>>& board, int k) {
▶6 if (k == (int)empty.size()) return true;
▶7 auto [r, c] = empty[k];
▶8 int b = r / 3 * 3 + c / 3;
▶9 for (int d = 1; d <= 9; d++) {
▶10 if (rows[r][d] || cols[c][d] || boxes[b][d]) continue;
▶11 board[r][c] = '0' + d;
▶12 rows[r][d] = cols[c][d] = boxes[b][d] = true;
▶13 if (solve(board, k + 1)) return true;
▶14 board[r][c] = '.';
▶15 rows[r][d] = cols[c][d] = boxes[b][d] = false;
▶16 }
▶17 return false;
▶18 }
▶19
▶20public:
▶21 void solveSudoku(vector<vector<char>>& board) {
▶22 for (int r = 0; r < 9; r++) {
▶23 for (int c = 0; c < 9; c++) {
▶24 if (board[r][c] == '.') {
▶25 empty.push_back({r, c});
▶26 } else {
▶27 int d = board[r][c] - '0';
▶28 rows[r][d] = cols[c][d] = boxes[r / 3 * 3 + c / 3][d] = true;
▶29 }
▶30 }
▶31 }
▶32 solve(board, 0);
▶33 }
▶34};
▶1class Solution {
▶2 private final boolean[][] rows = new boolean[9][10];
▶3 private final boolean[][] cols = new boolean[9][10];
▶4 private final boolean[][] boxes = new boolean[9][10];
▶5 private final List<int[]> empty = new ArrayList<>();
▶6
▶7 public void solveSudoku(char[][] board) {
▶8 for (int r = 0; r < 9; r++) {
▶9 for (int c = 0; c < 9; c++) {
▶10 if (board[r][c] == '.') {
▶11 empty.add(new int[] {r, c});
▶12 } else {
▶13 int d = board[r][c] - '0';
▶14 rows[r][d] = cols[c][d] = boxes[r / 3 * 3 + c / 3][d] = true;
▶15 }
▶16 }
▶17 }
▶18 solve(board, 0);
▶19 }
▶20
▶21 private boolean solve(char[][] board, int k) {
▶22 if (k == empty.size()) return true;
▶23 int r = empty.get(k)[0], c = empty.get(k)[1];
▶24 int b = r / 3 * 3 + c / 3;
▶25 for (int d = 1; d <= 9; d++) {
▶26 if (rows[r][d] || cols[c][d] || boxes[b][d]) continue;
▶27 board[r][c] = (char) ('0' + d);
▶28 rows[r][d] = cols[c][d] = boxes[b][d] = true;
▶29 if (solve(board, k + 1)) return true;
▶30 board[r][c] = '.';
▶31 rows[r][d] = cols[c][d] = boxes[b][d] = false;
▶32 }
▶33 return false;
▶34 }
▶35}
empty cells9
rule1 to 4 once per row, column and box
Backtracking. Visit the empty cells in order. At each one, try the digits that do not already appear in its row, column or box. If a later cell runs out of digits, the guess was wrong: undo it and try the next digit. Keeping a set per row, column and box makes each check O(1).
cell(0, 0)empty cell 1 of 9
digit1smallest that fits
Place 1 and record it in the row, column and box sets. It is only a guess: it stays only if every later cell can still be filled.
cell(0, 1)empty cell 2 of 9
digit2smallest that fits
Digits below 2 are ruled out by the highlighted row, column and box. Place 2 and record it in the row, column and box sets. It is only a guess: it stays only if every later cell can still be filled.
cell(0, 2)empty cell 3 of 9
digit3smallest that fits
Digits below 3 are ruled out by the highlighted row, column and box. Place 3 and record it in the row, column and box sets. It is only a guess: it stays only if every later cell can still be filled.
cell(0, 3)empty cell 4 of 9
digit4smallest that fits
Digits below 4 are ruled out by the highlighted row, column and box. Place 4 and record it in the row, column and box sets. It is only a guess: it stays only if every later cell can still be filled.
cell(2, 1)empty cell 5 of 9
digit1smallest that fits
Place 1 and record it in the row, column and box sets. It is only a guess: it stays only if every later cell can still be filled.
cell(2, 2)empty cell 6 of 9
digit4smallest that fits
Digits below 4 are ruled out by the highlighted row, column and box. Place 4 and record it in the row, column and box sets. It is only a guess: it stays only if every later cell can still be filled.
cell(2, 3)
digits left0return False
Dead end. No digit is left for (2, 3): the red cells already hold every digit in the same row, column or box. The board cannot be finished from here, so return
False and let the previous cell change its guess.cell(2, 2)
removed4row, column and box sets too
Backtrack. With 4 at (2, 2) some later cell had no digit left, so 4 cannot be right here. Erase it from the board and from the three sets, then continue the loop with the next digit.
cell(2, 2)
digits left0return False
Dead end. No digit is left for (2, 2): the red cells already hold the others in the same row, column or box, and 4 already failed further down. The board cannot be finished from here, so return
False and let the previous cell change its guess.cell(2, 1)
removed1row, column and box sets too
Backtrack. With 1 at (2, 1) some later cell had no digit left, so 1 cannot be right here. Erase it from the board and from the three sets, then continue the loop with the next digit.
cell(2, 1)empty cell 5 of 9
digit3next option after a dead end
Second try at this cell. 1 failed further down, so the loop moves on. Place 3 and record it in the row, column and box sets. It is only a guess: it stays only if every later cell can still be filled.
cell(2, 2)empty cell 6 of 9
digit4smallest that fits
Digits below 4 are ruled out by the highlighted row, column and box. Place 4 and record it in the row, column and box sets. It is only a guess: it stays only if every later cell can still be filled.
cell(2, 3)empty cell 7 of 9
digit1smallest that fits
Place 1 and record it in the row, column and box sets. It is only a guess: it stays only if every later cell can still be filled.
cell(3, 1)empty cell 8 of 9
digit1smallest that fits
Place 1 and record it in the row, column and box sets. It is only a guess: it stays only if every later cell can still be filled.
cell(3, 2)empty cell 9 of 9
digit2smallest that fits
Digits below 2 are ruled out by the highlighted row, column and box. Place 2 and record it in the row, column and box sets. It is only a guess: it stays only if every later cell can still be filled.
filled9 / 9
resultboard solved in place
Solved. The last empty cell got a digit, so
solve returns True all the way up and no guess is undone. Every row, column and box now holds 1 to 4 exactly once. The board was edited in place, which is what LeetCode checks.empty cells8
rule1 to 4 once per row, column and box
Backtracking. Visit the empty cells in order. At each one, try the digits that do not already appear in its row, column or box. If a later cell runs out of digits, the guess was wrong: undo it and try the next digit. Keeping a set per row, column and box makes each check O(1).
cell(0, 2)empty cell 1 of 8
digit3smallest that fits
Digits below 3 are ruled out by the highlighted row, column and box. Place 3 and record it in the row, column and box sets. It is only a guess: it stays only if every later cell can still be filled.
cell(0, 3)empty cell 2 of 8
digit4smallest that fits
Digits below 4 are ruled out by the highlighted row, column and box. Place 4 and record it in the row, column and box sets. It is only a guess: it stays only if every later cell can still be filled.
cell(1, 0)empty cell 3 of 8
digit3smallest that fits
Digits below 3 are ruled out by the highlighted row, column and box. Place 3 and record it in the row, column and box sets. It is only a guess: it stays only if every later cell can still be filled.
cell(1, 1)empty cell 4 of 8
digit4smallest that fits
Digits below 4 are ruled out by the highlighted row, column and box. Place 4 and record it in the row, column and box sets. It is only a guess: it stays only if every later cell can still be filled.
cell(2, 2)empty cell 5 of 8
digit4smallest that fits
Digits below 4 are ruled out by the highlighted row, column and box. Place 4 and record it in the row, column and box sets. It is only a guess: it stays only if every later cell can still be filled.
cell(2, 3)empty cell 6 of 8
digit3smallest that fits
Digits below 3 are ruled out by the highlighted row, column and box. Place 3 and record it in the row, column and box sets. It is only a guess: it stays only if every later cell can still be filled.
cell(3, 0)empty cell 7 of 8
digit4smallest that fits
Digits below 4 are ruled out by the highlighted row, column and box. Place 4 and record it in the row, column and box sets. It is only a guess: it stays only if every later cell can still be filled.
cell(3, 1)empty cell 8 of 8
digit3smallest that fits
Digits below 3 are ruled out by the highlighted row, column and box. Place 3 and record it in the row, column and box sets. It is only a guess: it stays only if every later cell can still be filled.
filled8 / 8
resultboard solved in place
Solved. The last empty cell got a digit, so
solve returns True all the way up and no guess is undone. Every row, column and box now holds 1 to 4 exactly once. The board was edited in place, which is what LeetCode checks.05
Common pitfalls
Undoing the board but not the sets
✗ Wrong
board[r][c] = "."
✓ Right
board[r][c] = "." rows[r].remove(d) cols[c].remove(d) boxes[b].remove(d)
The sets would still say d is used, so later cells in that row, column and box wrongly reject it. The solver then reports no solution for a valid puzzle.
Not stopping when the board is solved
✗ Wrong
solve(k + 1) board[r][c] = "."
✓ Right
if solve(k + 1):
return True
board[r][c] = "."Without checking the result, every placement is undone on the way back up, and the board ends exactly as it started. The success has to propagate up and skip every undo.
Wrong box index
✗ Wrong
b = r // 3 + c // 3
✓ Right
b = r // 3 * 3 + c // 3
r // 3 + c // 3 gives only 5 distinct values (0 to 4), merging different boxes. Boxes are numbered row-major: box row times 3, plus box column.
06
Complexity
Time
O(9ᵐ) worst case
Space
O(m)
m is the number of empty cells (at most 81). Each can take up to 9 digits, so the bound is exponential, but row, column and box pruning cuts it to a tiny fraction: on a typical puzzle the sudoku solver steps number a few hundred to a few thousand placements. Space is the recursion depth plus the fixed 27 sets.
07
Sudoku Solver FAQ
What is the difference between Valid Sudoku and Sudoku Solver?
Valid Sudoku (LeetCode 36) only checks that the filled cells break no rule: a single pass with the same row, column and box sets. Sudoku Solver (37) must fill the empty cells, which needs the search and backtracking on top of those checks.
How can a sudoku solver be made faster?
- Most constrained cell first: instead of reading order, fill the empty cell with the fewest legal digits. A cell with one option is forced, and dead ends show up much earlier.
- Bitmasks: one 9-bit integer per row, column and box replaces the sets; the legal digits for a cell are one OR and one NOT away.
- Exact cover: Dancing Links (Algorithm X) treats Sudoku as 324 constraints and handles the hardest puzzles, at the cost of much more code.
None of these is needed for LeetCode 37; plain backtracking passes comfortably.