Fill a 9×9 grid so every row, column and 3×3 box holds the digits 1 to 9 once each. A computer can do it by backtracking: write a digit, move on, and erase when stuck. The order it picks cells in can change the amount of work by a factor of thousands.
The solver walks the empty cells in reading order and tries 1 through 9 in each, keeping the first digit that clashes with nothing. When a cell has no legal digit, the mistake was made earlier, so it erases its last placement and tries the next digit there. Cells are named row and column from the top left, so r1c1 is the corner.
Try this: Pick Hard and press Step repeatedly; watch the red erase-and-retry loop.
Each placement is a guess that the rest of the board can still be completed. The search abandons a guess as soon as some later cell has no legal digit, and only then. It never skips an option, so if a solution exists it finds it, and if the root runs out of digits there is none.
It is the same search as 000 · N-Queens: place, check, recurse, undo. Sudoku has 81 cells instead of 8 rows, and the rule check covers a row, a column and a box.
Small digits in each empty cell are its candidates: the digits its row, column and box still allow. Reading order ignores them. The fewest candidates rule branches on the cell with the fewest options, so a wrong guess shows up sooner. Filling naked singles goes further: any cell left with one candidate gets that digit at once, with no guess. The table runs all four combinations on the chosen puzzle in the background.
Try this: Switch to Reading order and Singles off, then compare the Guesses count in the table.
| Order | Singles | Guesses | Forced | Backtr. |
|---|
With E empty cells there are 9^E ways to fill them blindly. For a 21-given puzzle that is a 58-digit number. The givens cut it down before any search starts, and backtracking visits a tiny fraction of what's left. Each bar is a power of ten, so one bar half as long as another is the square root of it. Move the slider to remove givens from the puzzle or reveal more of its solution.
How to read this: Longer bar means more; each step of length is ×10. Green bars count possible fillings, amber bars count actual search work, gold counts solutions.
Try this: Pick 17 givens and drag Givens to 16.
Remove enough givens and a puzzle stops having one answer. In 2012 Gary McGuire, Bastian Tugemann and Gilles Civario finished an exhaustive computer search showing that no 9×9 puzzle with 16 givens has a unique solution. So 17 is the minimum.
Try it on the 17-givens preset: drop the slider to 16 and the counter finds a second solution. On the other presets, watch the solution count and the search work as givens disappear.