Sudoku Solver Using Backtracking
The Puzzle
A Sudoku grid is 9 × 9, split into nine 3 × 3 boxes. Fill every empty cell with a digit 1–9 so that each row, each column, and each box contains every digit exactly once.
The puzzle used on this page (52 empty cells, one solution): . 7 4 | . . 3 | 9 . . 6 . . | . . . | 7 . 8 . . . | . . 4 | . . 6 ------+-------+------ . 8 . | . 3 . | . . . . . 9 | 1 . 7 | . 5 4 . . . | 8 . 5 | . 9 3 ------+-------+------ . 2 . | . 5 . | 3 1 . . . . | . . . | . 6 5 . 4 6 | . 9 . | . . .
Sudoku is the textbook constraint satisfaction problem: a set of variables (empty cells), a domain for each (digits 1–9), and rules that link them. Backtracking with good bookkeeping solves typical puzzles in milliseconds.
Mapping Sudoku to the Backtracking Template
LEVEL: one empty cell OPTIONS: digits 1..9 VALID IF: digit not already in the cell's row, column, or box CHOOSE: write the digit, record it in the three trackers UN-CHOOSE: erase the digit, remove it from the three trackers COMPLETE: no empty cells remain → stop the whole search (one answer)
Because only one answer is needed, the function returns true as soon as the grid is full, and every caller passes that true straight up without undoing anything.
Fast Constraint Checks
Box Index
box = (r / 3) * 3 + (c / 3) (integer division)
c: 0 1 2 3 4 5 6 7 8
r 0-2: box 0 box 1 box 2
r 3-5: box 3 box 4 box 5
r 6-8: box 6 box 7 box 8
Bitmask Trackers
Keep one integer per row, per column, and per box. Bit d is set ⇔ digit d is already present there.
rows[r], cols[c], boxes[b] (bits 1..9 used, bit 0 ignored)
used = rows[r] | cols[c] | boxes[b]
free = ~used & 0b1111111110 ← digits still legal for (r, c)
place d: rows[r] |= 1<<d; cols[c] |= 1<<d; boxes[b] |= 1<<d
remove d: rows[r] &= ~(1<<d); cols[c] &= ~(1<<d); boxes[b] &= ~(1<<d)
Example: row 0 of the puzzle has 7, 4, 3, 9
rows[0] = bits {3,4,7,9} = 0b1010011000
Every check, place, and remove is a handful of integer operations.
Which Cell to Fill Next?
The digit loop is fixed (1 to 9), but the order of cells is your choice, and it matters enormously.
STRATEGY 1 — READING ORDER
Always fill the first empty cell (left to right, top to bottom).
Simple. But it may branch on a cell with 5 candidates while another
cell elsewhere has only 1 — and only discover a contradiction much later.
STRATEGY 2 — FEWEST CANDIDATES FIRST
Scan all empty cells, pick the one with the fewest legal digits.
0 candidates → this partial grid is impossible: return false NOW
1 candidate → forced move, no branching at all
2+ → branch, but on the narrowest choice available
Costs an O(81) scan per call, but shrinks the tree dramatically.
The program below solves the same puzzle both ways and counts recursive calls.
public class SudokuSolver {
static final String[] PUZZLE = {
".74..39..",
"6.....7.8",
".....4..6",
".8..3....",
"..91.7.54",
"...8.5.93",
".2..5.31.",
".......65",
".46.9....",
};
int[][] grid = new int[9][9];
int[] rows = new int[9], cols = new int[9], boxes = new int[9]; // bit d → digit d present
int[][] empties = new int[81][];
int emptyCount = 0;
long calls = 0;
SudokuSolver(String[] puzzle) {
for (int r = 0; r < 9; r++)
for (int c = 0; c < 9; c++) {
char ch = puzzle[r].charAt(c);
if (ch == '.') empties[emptyCount++] = new int[]{r, c};
else mark(r, c, ch - '0');
}
}
static int box(int r, int c) { return (r / 3) * 3 + c / 3; }
void mark(int r, int c, int d) {
int bit = 1 << d;
rows[r] |= bit; cols[c] |= bit; boxes[box(r, c)] |= bit;
grid[r][c] = d;
}
void unmark(int r, int c, int d) {
int bit = 1 << d;
rows[r] &= ~bit; cols[c] &= ~bit; boxes[box(r, c)] &= ~bit;
grid[r][c] = 0;
}
int candidates(int r, int c) {
int used = rows[r] | cols[c] | boxes[box(r, c)];
return ~used & 0b1111111110; // bits 1..9 that are still free
}
// Strategy 1 — fill empty cells in reading order
boolean solveInOrder(int k) {
calls++;
if (k == emptyCount) return true;
int r = empties[k][0], c = empties[k][1];
int free = candidates(r, c);
for (int d = 1; d <= 9; d++) {
if ((free & (1 << d)) == 0) continue;
mark(r, c, d); // choose
if (solveInOrder(k + 1)) return true; // explore
unmark(r, c, d); // un-choose
}
return false;
}
// Strategy 2 — always fill the empty cell with the FEWEST candidates
boolean solveFewestFirst() {
calls++;
int bestR = -1, bestC = -1, bestFree = 0, bestCount = 10;
for (int k = 0; k < emptyCount; k++) {
int r = empties[k][0], c = empties[k][1];
if (grid[r][c] != 0) continue;
int free = candidates(r, c);
int n = Integer.bitCount(free);
if (n < bestCount) {
bestR = r; bestC = c; bestFree = free; bestCount = n;
if (n <= 1) break; // cannot do better than this
}
}
if (bestR == -1) return true; // no empty cell left
if (bestCount == 0) return false; // dead end — prune now
for (int d = 1; d <= 9; d++) {
if ((bestFree & (1 << d)) == 0) continue;
mark(bestR, bestC, d);
if (solveFewestFirst()) return true;
unmark(bestR, bestC, d);
}
return false;
}
static void show(int[][] g) {
for (int r = 0; r < 9; r++) {
if (r == 3 || r == 6) System.out.println("------+-------+------");
StringBuilder line = new StringBuilder();
for (int c = 0; c < 9; c++) {
if (c == 3 || c == 6) line.append("| ");
line.append(g[r][c]).append(' ');
}
System.out.println(line.toString().trim());
}
}
public static void main(String[] args) {
SudokuSolver a = new SudokuSolver(PUZZLE);
System.out.println("empty cells: " + a.emptyCount);
a.solveInOrder(0);
show(a.grid);
SudokuSolver b = new SudokuSolver(PUZZLE);
b.solveFewestFirst();
String same = java.util.Arrays.deepEquals(a.grid, b.grid) ? "True" : "False";
System.out.println("same answer both ways: " + same);
System.out.println("calls, reading order: " + a.calls);
System.out.println("calls, fewest first: " + b.calls);
}
}Output:
empty cells: 52
8 7 4 | 5 6 3 | 9 2 1
6 5 3 | 9 1 2 | 7 4 8
1 9 2 | 7 8 4 | 5 3 6
------+-------+------
4 8 5 | 6 3 9 | 1 7 2
3 6 9 | 1 2 7 | 8 5 4
2 1 7 | 8 4 5 | 6 9 3
------+-------+------
7 2 8 | 4 5 6 | 3 1 9
9 3 1 | 2 7 8 | 4 6 5
5 4 6 | 3 9 1 | 2 8 7
same answer both ways: True
calls, reading order: 3356
calls, fewest first: 53
Reading the Result
Reading order: 3,356 calls — many wrong guesses, discovered late Fewest first: 53 calls — 52 empty cells + 1 final call 53 calls means the fewest-first solver NEVER guessed wrong on this puzzle: at every step some cell had exactly one legal digit, so it was a chain of forced moves. Harder puzzles do need real branching, but the rule still keeps the tree small — it always branches on the narrowest choice.
Complexity
Let e = number of empty cells.
TIME (worst case): O(9^e) — each empty cell can try up to 9 digits.
That bound is never close in practice: row/column/box
checks cut most branches, and fewest-first ordering
turns many levels into forced moves.
PER NODE: reading order: O(1) for the check (bitmasks)
fewest first: O(e) scan to pick the next cell
SPACE: O(e) recursion depth + O(1) for 27 integer trackers
(the grid itself is 81 cells, fixed size)
A fixed 9 × 9 board means every Sudoku is technically O(1) — but the 9ᵉ bound is the honest way to describe how the work grows with the number of blanks.
Going Further
CONSTRAINT PROPAGATION After placing a digit, immediately fill every cell that now has exactly one candidate (and undo them all together on backtrack). Fewest-first does this implicitly, one call at a time. HIDDEN SINGLES If digit d can go in only one cell of a row/column/box, place it — even if that cell has other candidates. CHECK UNIQUENESS Don't stop at the first solution: count solutions up to 2. 1 → well-formed puzzle, 2 → ambiguous, 0 → invalid. OTHER SIZES 16 × 16 (4 × 4 boxes, digits 1-16): same code with size parameters and 17-bit masks.
Common Mistakes
Wrong box formula. r / 3 + c / 3 collides boxes (e.g. box (0,1) and box (1,0) both give 1). Use (r / 3) * 3 + c / 3.
Undoing after success. Once the recursive call returns true, return immediately. Undoing then would erase the solved grid.
Forgetting to update the trackers on undo. Clearing only grid[r][c] leaves the digit marked in the row, column, and box, which wrongly blocks it elsewhere.
Not marking the given digits at the start. The trackers must reflect the clues before searching, or the solver will happily place a duplicate next to a clue.
Validating the full board at the end. That is brute force — with 52 blanks, 9⁵² boards. Validate every digit as it is placed.
Interview Questions
Q: Walk through how you check whether a digit can be placed at (r, c).
Keep a bitmask for each row, column, and box. OR the three masks for the cell to get every digit already used in its neighbourhood. The digit d is allowed if bit d is clear. Placing or removing a digit sets or clears that bit in the same three masks, so every operation is O(1).
Q: Why does choosing the cell with the fewest candidates speed things up so much?
It minimises branching at each level and detects failure early. A cell with zero candidates proves the current partial grid is impossible immediately, instead of after many more placements elsewhere. A cell with one candidate costs no branching at all. Branching on the most constrained cell keeps the search tree narrow near the root, where a wrong choice is most expensive.
Q: How would you check that a Sudoku puzzle has exactly one solution?
Run the solver but, instead of returning on the first full grid, increment a counter and keep searching. Stop as soon as the counter reaches 2. A final count of 1 means the puzzle is uniquely solvable.
Summary
- ›Sudoku = one level per empty cell, digits 1–9 as options, row/column/box as constraints.
- ›Box index: (r / 3) * 3 + c / 3.
- ›Track used digits with 27 bitmasks for O(1) checks, places, and removals.
- ›Return true up the stack on the first full grid — never undo after success.
- ›Fewest candidates first cut this page's puzzle from 3,356 calls to 53.
Next, Word Search moves backtracking onto a grid where the path itself must stay connected — and where marking and unmarking visited cells is the undo step.
Which 3×3 box (numbered 0–8 left-to-right, top-to-bottom) contains the cell at row 5, column 7?