Sudoku Solver

Two different jobs get called solving

The first is finding an answer: hand the program a grid, get a filled grid back. The second is proving that answer is the only one. Almost every published solver does the first and quietly implies the second, and the gap between them is where puzzles go wrong. A grid with two valid completions will still produce a confident answer, and if your own answer happens to be the other one, the solver will tell you that a perfectly correct grid is wrong. Any solver used to check a puzzle rather than to finish it has to be able to count.

Propagate first, search second

The naive approach – try 1 in the first empty cell, then 2, and back out when it fails – works and is unusably slow. What every practical solver does instead is compute, for each empty cell, the set of digits still legal there given its row, its column and its box. Any cell with exactly one candidate is filled immediately, which shrinks the candidate sets of its peers, which usually produces another cell with one candidate. That cascade alone finishes a gentle puzzle without a single guess. Only when the cascade stalls does the program have to choose a cell and try its candidates in turn, and it repeats the whole procedure inside each branch.

Branch on the tightest cell, not the first one

When a guess is unavoidable, which cell you guess in decides everything. Picking the first empty cell in reading order might mean choosing between six candidates, so five out of six branches are wasted work carried a long way before it collapses. Picking the cell with the fewest candidates left – two, if such a cell exists – halves the work at that node and pushes the contradiction closer to the surface. The solver used here scans for the smallest candidate set and abandons the scan the moment it finds a cell with one candidate, because there is nothing better to find. It also gives up on the branch immediately if any empty cell has no candidates at all, rather than discovering that fact several levels deeper.

Counting to two is the whole trick

To prove a puzzle has one solution you do not need to know how many it has – you need to know whether it has more than one. So the counter runs the same search but does not stop at the first completion; it records it and keeps going, and the moment a second turns up it stops dead. That cap is what makes the check cheap enough to run inside a generator that is removing digits one at a time and testing after every removal. Without the cap, an ambiguous grid can have millions of completions and the count would run until the tab was closed.

A hint is a solver with a conscience

The tempting shortcut is to solve the puzzle once, keep the answer, and have the hint copy one cell out of it. It is a few lines of code and it teaches nothing, because the cell it reveals may be one no human could yet deduce. The boards here work the other way: a hint runs the human technique list over the position actually in front of you, fills the first cell that reasoning reaches, and names the sort of deduction it used. When the position cannot be advanced by any technique on the list, the board says there is no hint available rather than pretending.

When a printed puzzle refuses to come out

Nine times in ten it is a transcription error, not a bad puzzle. Before blaming the grid, check the givens for a straightforward repeat – the same digit twice in one row, column or box – because that is the usual result of reading a 6 as an 8 or of slipping a column while copying. A solver given a contradictory grid returns nothing at all, which is a useful answer in itself: it means the puzzle as typed has no solution, and the fault is above the solver rather than inside it. If you want to see the technique list applied to a live grid instead, the hard board will name each deduction as it makes it.