#37
Sudoku Solver
Hard Backtracking on empty cells
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
Fill the empty cells of a 9×9 Sudoku so every row, column and 3×3 box contains 1–9 exactly once. The puzzle has exactly one solution.
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: fill the board so every row, column and box has 1–9.
Why this works: try each allowed digit in an empty cell, recurse, and undo when a later cell has no options.
Example: an empty cell where row, column and box already use 1–8
only 9 is allowed → place 9 and move ona dead end later → remove 9 and try the previous cell's next digit
✦Hints open one at a time
Find an empty cell, try digits 1–9 that don't break a rule, recurse.
If no digit works, undo and return false so the caller tries its next digit.
Keep row, column and box "used" arrays to test a digit in O(1).
↗Approach
Collect the used digits first. solve(pos) walks cells in order; for an empty cell try each allowed digit, mark, recurse; on failure unmark and reset the cell.
</>Solution (Java)
class Solution {
private final boolean[][] row = new boolean[9][10], col = new boolean[9][10], box = new boolean[9][10];
public void solveSudoku(char[][] board) {
for (int r = 0; r < 9; r++)
for (int c = 0; c < 9; c++)
if (board[r][c] != '.') mark(r, c, board[r][c] - '0', true);
solve(board, 0);
}
private boolean solve(char[][] b, int pos) {
if (pos == 81) return true;
int r = pos / 9, c = pos % 9;
if (b[r][c] != '.') return solve(b, pos + 1);
for (int d = 1; d <= 9; d++) {
if (row[r][d] || col[c][d] || box[(r / 3) * 3 + c / 3][d]) continue;
b[r][c] = (char) ('0' + d);
mark(r, c, d, true);
if (solve(b, pos + 1)) return true;
mark(r, c, d, false); // undo
b[r][c] = '.';
}
return false;
}
private void mark(int r, int c, int d, boolean v) {
row[r][d] = col[c][d] = box[(r / 3) * 3 + c / 3][d] = v;
}
}!Common mistake
Not resetting the cell to '.' after a failed try.
Complexity
- Time: Exponential in the worst case, fast in practice with O(1) checks.
- Space: O(81).
Topic: Recursion & Backtracking
🎬 Episodes 29–36: video coming soon