N-Queens named this page as a natural next step, and the shape carries over almost unchanged: build a candidate incrementally, reject a choice the instant it can't work, and undo the moment nothing further is left to explore. Where N-Queens places one queen per column, Sudoku fills one empty cell at a time with a digit 1–9, and a placement is legal only if that digit doesn't already appear in the same row, column, or 3×3 box. Nine candidate rows become nine candidate digits; two constraints (row, diagonal) become three (row, column, box) — everything else about the search is the same discipline applied to a bigger board.
The solver picks an empty cell, then tries digits 1 upward. A digit is rejected the instant it collides with the same row, column, or box — the demo shows exactly which cell it collided with and why. A digit that survives all three checks gets placed, and the search moves to the next empty cell. Once every digit 1–9 has been tried in a cell with none surviving, the search backtracks: clear that cell and resume trying the next digit in whichever cell was filled just before it. Bold digits are the puzzle's own givens and never change; the search only ever fills and clears the plain digits. This particular puzzle — 48 givens, 33 blanks — was built by taking a real solved grid, removing 33 cells, and checking by independent exhaustive search that exactly one completion exists, not assumed.
The cell order selector below switches which empty cell gets picked at each step. Reading order always picks the first empty cell, top-left to bottom-right, no matter how many digits would still survive there. MRV (minimum remaining values) instead checks every empty cell's candidate count first and picks whichever has the fewest legal digits — the most constrained cell, tried first because it's the one most likely to fail fast or have only one way to go. Same board, same conflict rule, same reference algorithm underneath; only the order cells are visited changes. Switching the selector reruns the search from scratch and reloads the step list.
Checking a candidate digit against every filled cell in its row, column, and box is
O(1) per check (each of the three groups always has exactly 9 cells), so testing all nine
digits at one empty cell costs at most O(9) — cheap, and cheap early, which is the whole
point: a conflict is caught the moment it's introduced rather than after the rest of the board has been
filled in around it. That's what makes backtracking correct here for the same reason it's correct for
N-Queens: every rejected digit is a proof that no completion of the board can use it in that cell, so
skipping straight past it costs nothing. The default puzzle above needs 273 digit
attempts and 12 backtracks to reach its one solution — far short of the
933 ways to fill 33 blanks with no constraint checking at all, because almost
every one of those attempts gets cut off within a row, column, or box of where it started.
function solveSudoku(board) { // board is 9x9, 0 marks an empty cell
function findEmpty() {
for (let r = 0; r < 9; r++)
for (let c = 0; c < 9; c++)
if (board[r][c] === 0) return [r, c];
return null; // no empty cells left — the board is complete
}
function conflicts(row, col, val) {
for (let i = 0; i < 9; i++) {
if (board[row][i] === val) return true; // same row
if (board[i][col] === val) return true; // same column
}
const br = row - row % 3, bc = col - col % 3;
for (let r = br; r < br + 3; r++)
for (let c = bc; c < bc + 3; c++)
if (board[r][c] === val) return true; // same 3x3 box
return false;
}
function solve() {
const empty = findEmpty();
if (!empty) return true; // every cell filled — solved
const [row, col] = empty;
for (let val = 1; val <= 9; val++) {
if (conflicts(row, col, val)) continue;
board[row][col] = val;
if (solve()) return true; // propagate success all the way up
board[row][col] = 0; // backtrack: undo, try the next digit
}
return false; // no digit works here — this branch is a dead end
}
return solve() ? board : null;
}Stopping at the first solution isn't the same as checking there's only one. The
reference implementation above returns the instant solve() finds a complete board — it
never looks for a second one. A well-formed Sudoku puzzle is supposed to have exactly one solution, but
this solver has no way to tell a proper puzzle from a sloppy one that happens to have several; it just
reports whichever completion it reaches first. Verifying uniqueness needs a different check entirely —
keep searching after the first solution and confirm nothing else turns up (which is exactly how the
default puzzle above was validated before shipping it, with a separate exhaustive search
capped at two solutions — it's not something the solver itself does at solve time).
Cell order isn't neutral — it can change the attempt count by orders of magnitude. Reading order always picks the first empty cell, with no regard for how constrained that cell already is. The order selector above makes this a real, checked comparison rather than a claim: on this page's own default puzzle, reading order needs 273 attempts and 12 backtracks to reach the solution, while MRV — picking the emptiest-of-choices cell first at every step — reaches the identical unique solution in just 165 attempts and 0 backtracks. Both numbers come from running the exact shipped generator above, not estimated; MRV's own tie-break (when two or more empty cells are tied for fewest candidates, the one that comes first in reading order wins) is itself arbitrary, the same kind of caveat this site's DP pages raise about their own tie-breaks. Feeding the plain reading-order code two other real, published, verified-unique puzzles instead of the default one shows the gap grows with difficulty: a widely-used "easy" puzzle (Project Euler's problem 96, 31 givens) takes 37,652 attempts and 4,157 backtracks, and Arto Inkala's 2012 puzzle — reported in the press at the time as the world's hardest — takes 445,778 attempts and 49,498 backtracks. Neither puzzle is shown as a clickable demo here, the same way N-Queens named its 8×8 numbers in prose without offering an 8×8 board to step through — thousands of steps stop being something a person can usefully watch one at a time, even though the algorithm handles them fine unattended. MRV's own numbers on those two harder boards aren't re-measured here (would need re-running the harder puzzles' exact grids through the MRV variant too) — a natural follow-up if this page ever gets its own worked comparison table.
Undoing the placement is still load-bearing. Same lesson N-Queens landed on with
queens.pop(), unchanged by the bigger board: board[row][col] = 0 after a
failed recursive call isn't cleanup, it's what makes the next digit's conflicts check see
an accurate board. Skip it and a stale digit keeps blocking (or silently permitting) placements that
should have been evaluated against an empty cell.
Time: exponential in the worst case — up to 9 choices at each of the board's empty
cells with no guaranteed cutoff, though in practice the row/column/box checks prune the vast majority of
branches immediately, which is the entire gap between 273 attempts and 933
above. Space: O(1) beyond the 9×9 board itself — the recursion depth is
bounded by the number of empty cells (at most 81), and no larger structure is ever built alongside it.
The same "fill the next open slot, reject a conflict immediately, undo on the way back out" shape underlies graph coloring and generating constrained permutations generally, not just chess boards and grids — N-Queens and this page are two instances of one general technique, not two unrelated puzzles. See Choosing a Backtracking Strategy for how this page's own reading-order-vs-MRV numbers compare to the other nine entries' order sensitivity.