Sudoku solver
hardThe solver has no clever insight. All the improvement comes from filling the most-constrained cell first, which often leaves exactly one option and nothing to guess.
O(9^empty cells)Space O(1) on a fixed 9×9 gridSaved in this browser - no sign-up, nothing sent anywhere.
How sudoku solver works
Fill every empty cell with 1 to 9 so that no digit repeats in its row, column, or 3×3 box. The solver is the choose-explore-undo skeleton and nothing more: find an empty cell, try each legal value, recurse, and erase the value if the recursion fails. When a cell has zero legal values the branch is already dead, and the solver backs up without trying anything.
All the improvement comes from ordering, not cleverness. Scanning left to right, top to bottom, the engine solves the classic 30-clue puzzle in 4,209 recursive calls. Turn on most-constrained-cell ordering and the same puzzle takes 52 calls - one per empty cell plus the final check, meaning not a single placement had to be undone. Filling the hardest cell first often leaves exactly one option, and one option is not a guess.
That gap is the general lesson of constraint-satisfaction search: failing fast beats searching fast. A wrong value placed in a loosely constrained cell can survive for thousands of calls before the contradiction surfaces; the same wrong value in a tight cell dies immediately. Reach for this pattern whenever choices are heavily constrained and a cheap legality test can veto them early.
Step by step
- The classic puzzle starts with 30 clues and 51 empty cells. Scanning row by row, the first empty cell is (0, 2).
- Its row, column, and box already contain 3, 5, 6, 7, 8, and 9, so (0, 2) accepts only 1, 2, and 4.
- The solver places 1, the smallest candidate, and recurses to the next empty cell, (0, 3), which now accepts just 2 and 6.
- Placement continues until some cell has no legal value. That branch is dead - the solver erases the most recent value and tries the next candidate.
- Wrong early guesses can survive a long time: the left-to-right run needs 4,209 recursive calls before every contradiction is resolved and the grid fills.
- Rerun with most-constrained-cell ordering on: cells with exactly one option are filled first, forced moves cascade, and the puzzle solves in 52 calls with zero backtracks.
Complexity
| Worst case time | O(9^empty cells) |
|---|---|
| Space | O(1) on a fixed 9×9 grid |
Constraint propagation cuts the practical branching factor enormously.
Reference implementation
Python
def solve(grid):
for r in range(9):
for c in range(9):
if grid[r][c]:
continue
for v in range(1, 10):
if legal(grid, r, c, v):
grid[r][c] = v # choose
if solve(grid): # explore
return True
grid[r][c] = 0 # undo
return False # nothing fits: dead end
return True # no empty cell left
def legal(grid, r, c, v):
box_r, box_c = 3 * (r // 3), 3 * (c // 3)
return (
all(grid[r][x] != v for x in range(9)) and
all(grid[x][c] != v for x in range(9)) and
all(grid[box_r + i][box_c + j] != v
for i in range(3) for j in range(3))
)JavaScript
function solve(grid) {
for (let r = 0; r < 9; r++) {
for (let c = 0; c < 9; c++) {
if (grid[r][c]) continue;
for (let v = 1; v <= 9; v++) {
if (legal(grid, r, c, v)) {
grid[r][c] = v;
if (solve(grid)) return true;
grid[r][c] = 0;
}
}
return false;
}
}
return true;
}
function legal(g, r, c, v) {
const br = 3 * Math.floor(r / 3), bc = 3 * Math.floor(c / 3);
for (let i = 0; i < 9; i++) {
if (g[r][i] === v || g[i][c] === v) return false;
if (g[br + ((i / 3) | 0)][bc + (i % 3)] === v) return false;
}
return true;
}Worth noticing
Try, recurse, undo - Sudoku is the purest example
There is no clever insight in the solver itself. Every improvement comes from ordering: which cell to fill next and which values to try first.
Most-constrained-variable is the big win
Turn the toggle on. Instead of scanning left-to-right, it fills whichever empty cell has the fewest legal values - often only one, where there is nothing to guess. On a hard puzzle this can cut the node count by an order of magnitude.
Failing fast beats searching fast
A cell with zero legal values means the branch is already dead. Detecting that immediately - rather than after nine failed attempts several levels deeper - is where the saving comes from.
Common pitfalls
- Forgetting grid[r][c] = 0 after a failed recursion. The stale digit over-constrains every later legality check, and a solvable puzzle comes back reported as unsolvable.
- Dropping the result of the recursive call. It must be if solve(): return True - calling solve() without returning its answer keeps searching after the puzzle is already solved.
- Misplacing the return False. It belongs right after the value loop of the first empty cell; move it outside the scan and the solver skips unfillable cells and declares a grid with holes solved.
- Getting the box origin wrong. A cell's box starts at 3 times (r // 3) down and 3 times (c // 3) across - using r % 3 instead checks the wrong nine cells.
- Overwriting given clues. The recursion must skip cells that are non-zero in the original puzzle; erasing a clue during backtracking corrupts the board permanently.
Where it is used
- Constraint-satisfaction solvers - most-constrained-variable and fail-fast ordering shown here are the same heuristics production CSP engines use.
- Puzzle apps and generators - creating a sudoku means removing clues while a solver keeps confirming the solution is still unique.
- Timetabling and rostering, where slots take one value each under no-repeat constraints structurally identical to rows, columns, and boxes.
- A standard interview hard - LeetCode 37 asks for exactly this solver, and cell ordering is the natural follow-up discussion.
Frequently asked questions
What is the time and space complexity of a backtracking sudoku solver?
Worst-case time is O(9^empty cells) - up to nine candidates for each empty cell, and the default puzzle has 51 of them. Space is O(1) on a fixed 9×9 grid: the board is constant size and recursion depth never exceeds 81. In practice the legality check collapses the branching - 4,209 calls on the default run, nowhere near 9^51.
What is the most-constrained-variable heuristic?
Instead of filling empty cells in reading order, pick the one with the fewest legal candidates. A cell with one candidate is a free move; a cell with zero proves the branch dead before descending. On the default puzzle it cuts 4,209 recursive calls to 52 - not one placement is ever undone.
Can backtracking solve any sudoku?
Yes. The search is exhaustive, so it finds a solution whenever one exists and proves unsolvability otherwise - the only cost is time, which the O(9^empty cells) worst case reflects. Hard puzzles are mostly hard for the scan-order solver; good cell ordering flattens much of the difficulty.
How many clues does a sudoku need for a unique solution?
17. A computer search published in 2012 checked that no 16-clue puzzle has a unique solution, and tens of thousands of valid 17-clue puzzles are known. The puzzle here has 30 clues, which is typical for a moderately rated grid.