#37 Sudoku Solver
the problem
In plain words
Fill a 9 × 9 Sudoku board in place. Empty cells hold '.'. When you finish, every row, every column and every 3 × 3 box must contain each digit 1–9 exactly once. The puzzle is guaranteed to have exactly one solution.
in board = ["53..7....","6..195...",".98....6.","8...6...3","4..8.3..1","7...2...6",".6....28.","...419..5","....8..79"]
out ["534678912","672195348","198342567","859761423","426853791","713924856","961537284","287419635","345286179"]
Each row is written as one string to save space. In Java the board is a char[9][9].
- board.length == 9 and board[i].length == 9
- board[i][j] is a digit '1'–'9' or '.'
- The puzzle has exactly one solution
your turn
Try it before you peek
Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.
Solve it in the browser
LeetCode-style: complete the class. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.
Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.
Marking the problem solved, or opening every hint, also shows it.
the aha
Key insight
patternBacktracking with constraint pruningBitmask as a set
It's N-Queens with digits: fill one empty cell, try only digits its row, column and box allow, undo on a dead end. Two upgrades make it instant: O(1) "used" tables (bitmasks), and always filling the cell with the fewest options first.
solutions
From brute force to optimal
Find the first '.', try '1'–'9', check each by reading its row, column and box (27 cells), recurse, undo.
- Scan for the first empty cell; none left → true.
- For each digit: if no clash in row, column or box, place it.
- If the recursive call succeeds, return true; else put '.' back.
- All 9 failed → return false.
m = empty cells, up to 9 tries each in the worst case. Every try also pays 27 reads to check and up to 81 to find the next empty cell.
One stack frame per filled cell.
class Solution { public void solveSudoku(char[][] board) { solve(board); } private boolean solve(char[][] board) { for (int r = 0; r < 9; r++) { for (int c = 0; c < 9; c++) { if (board[r][c] != '.') continue; // first empty cell for (char d = '1'; d <= '9'; d++) { if (!canPlace(board, r, c, d)) continue; board[r][c] = d; // choose if (solve(board)) return true; // explore: stop at the first full board board[r][c] = '.'; // un-choose } return false; // no digit fits here → backtrack } } return true; // no empty cell left: solved } /** Reads the row, the column and the 3×3 box: 27 cells per check. */ private boolean canPlace(char[][] board, int r, int c, char d) { int br = r / 3 * 3, bc = c / 3 * 3; for (int i = 0; i < 9; i++) { if (board[r][i] == d || board[i][c] == d) return false; if (board[br + i / 3][bc + i % 3] == d) return false; } return true; }}Keep row[r][d], col[c][d], box[b][d] booleans and a list of empty cells. A check becomes three lookups.
- Fill the tables from the givens; collect the empty cells.
- solve(k): k == number of empties → true.
- Try digits not used in row, column or box; mark, recurse(k + 1), unmark.
Same worst-case tree, but each try costs O(1) instead of a 27-cell scan.
The list of empty cells and the recursion; the tables are a fixed 3 × 9 × 10.
class Solution { private final boolean[][] row = new boolean[9][10], col = new boolean[9][10], box = new boolean[9][10]; private final List<int[]> empty = new ArrayList<>(); public void solveSudoku(char[][] board) { for (int r = 0; r < 9; r++) { for (int c = 0; c < 9; c++) { if (board[r][c] == '.') { empty.add(new int[] {r, c}); } else { int d = board[r][c] - '0'; row[r][d] = col[c][d] = box[r / 3 * 3 + c / 3][d] = true; } } } solve(board, 0); } private boolean solve(char[][] board, int k) { if (k == empty.size()) return true; // every empty cell filled int r = empty.get(k)[0], c = empty.get(k)[1], b = r / 3 * 3 + c / 3; for (int d = 1; d <= 9; d++) { if (row[r][d] || col[c][d] || box[b][d]) continue; // O(1) instead of 27 reads board[r][c] = (char) ('0' + d); row[r][d] = col[c][d] = box[b][d] = true; if (solve(board, k + 1)) return true; row[r][d] = col[c][d] = box[b][d] = false; } board[r][c] = '.'; return false; }}Bit d of rows[r], cols[c], boxes[b] = digit d is used. Each step, fill the empty cell with the fewest free digits (Integer.bitCount).
- For every empty cell: free = ~(rows[r] | cols[c] | boxes[b]) & 0b11_1111_1110.
- Pick the cell with the smallest bitCount(free). None → solved.
- For each set bit d of free: place d, toggle the three masks, recurse; on failure toggle back.
- 0 options → the loop does nothing → return false at once.
Still exponential in theory, but forced cells (one option) go first and dead cells (zero options) fail at once: 56–96 calls on the judge's 26-clue puzzles, against 1,549–6,121 for the scan version.
Recursion depth ≤ m; three int[9] tables.
class Solution { private final int[] rows = new int[9], cols = new int[9], boxes = new int[9]; // bit d on = digit d used public void solveSudoku(char[][] board) { for (int r = 0; r < 9; r++) for (int c = 0; c < 9; c++) if (board[r][c] != '.') toggle(r, c, board[r][c] - '0'); solve(board); } private boolean solve(char[][] board) { int bestR = -1, bestC = -1, bestFree = 0, fewest = 10; for (int r = 0; r < 9; r++) { // pick the empty cell with the FEWEST options for (int c = 0; c < 9; c++) { if (board[r][c] != '.') continue; int free = ~(rows[r] | cols[c] | boxes[r / 3 * 3 + c / 3]) & 0b11_1111_1110; // digits 1..9 int options = Integer.bitCount(free); if (options < fewest) { fewest = options; bestR = r; bestC = c; bestFree = free; } } } if (bestR == -1) return true; // no empty cell: solved for (int free = bestFree; free != 0; free &= free - 1) { // 0 options → loop skipped → backtrack int d = Integer.numberOfTrailingZeros(free); // lowest candidate digit board[bestR][bestC] = (char) ('0' + d); toggle(bestR, bestC, d); if (solve(board)) return true; toggle(bestR, bestC, d); // XOR again = undo } board[bestR][bestC] = '.'; return false; } private void toggle(int r, int c, int d) { rows[r] ^= 1 << d; cols[c] ^= 1 << d; boxes[r / 3 * 3 + c / 3] ^= 1 << d; }}in the room
How to say it in the interview
talk track
- "Backtracking: pick an empty cell, try the digits its row, column and box allow, undo on a dead end, stop at the first full board."
- "I return a boolean, so the search stops the moment the board is full — otherwise the undo would wipe the answer."
- Upgrade 1: three tables make each check O(1). The box index is
r / 3 * 3 + c / 3. - Upgrade 2: fill the most constrained cell first. Zero options → fail now; one option → forced, no guessing.
traps
- A
voidrecursion: after the board is solved, the undo lines erase it again. Returnbooleanand stop ontrue. - Wrong box index: it's
r / 3 * 3 + c / 3, notr / 3 + c / 3. - Forgetting to put '.' back when every digit fails.
what they ask next
Follow-ups
Valid Sudoku (LC 36): only check a partly filled board?
One pass with the same three tables. A digit already in its row, column or box table means the board is invalid. No search needed.
How do serious solvers go even faster?
Constraint propagation (keep filling forced cells before any guess), or model Sudoku as an exact-cover problem and use Knuth's Algorithm X with dancing links.
before you submit
Edge cases to test
- Only one empty cell: a single forced digit.
- A whole row empty: every cell is fixed by its column.
- Hard puzzles with about 25 givens: a wrong guess deep down must be undone.
practise next
Similar problems
- #36Valid SudokuMediumin Hashing
- #51N-QueensHardin Backtracking
- #79Word SearchMediumin Backtracking