An easy Sudoku on this site prints 36 clues. The medium setting prints 30, and the hard setting cuts down to 26 and stops when the loop runs out of cells. None of them go anywhere near the number this piece is about, and the gap is not laziness: 17 is the floor for a puzzle with exactly one solution, and the search that ruled out everything below it ran for roughly 800 processor-years.
The counting side is the easy half. Choosing 16 of the 81 cells in one completed grid gives C(81,16) = 33,594,090,947,249,085 candidate clue patterns, about 3.4 x 10^16 of them, and that is a single grid out of the pile. The number of legal finished 9 x 9 grids is 6,670,903,752,021,072,936,960. Divide out relabelling the digits, swapping rows, columns and bands, transposing and reflecting, and 5,472,730,538 grids are left that are genuinely different from each other.
The hard half is that having one solution is a property of the clue set as a whole, and no single cell carries it. A generator that only checks each placement locally — this digit does not clash with its row, its column or its box — will hand over a grid that two people can finish two different ways.
From checker in 2005 to the answer in 2012
Gary McGuire wrote the first version of a program called checker in August 2005, working with Gordon Royle, who had spent years collecting 17-clue puzzles at the University of Western Australia while hunting for a 16-clue one. The collection reached 49,151 puzzles, no two of them equivalent under the grid symmetries. Each is a 17-clue puzzle with exactly one solution, which makes the list a mountain of evidence and not a proof.
The proof arrived in a preprint by McGuire, Bastian Tugemann and Gilles Civario posted on 1 January 2012, later published in Experimental Mathematics. They searched the 5,472,730,538 essentially different grids for a 16-clue puzzle, found none, and closed the minimum at 17. The ratio shows the shape of the problem: roughly one catalogued 17-clue puzzle exists for every 111,000 equivalence classes.
| Quantity | Value | Where it comes from |
|---|---|---|
| Completed 9 x 9 grids | 6,670,903,752,021,072,936,960 | Felgenhauer and Jarvis, 2005 |
| Essentially different grids | 5,472,730,538 | Russell and Jarvis |
| 16-cell patterns inside one grid | 33,594,090,947,249,085 | C(81,16), my arithmetic |
| Catalogued 17-clue puzzles | 49,151 | Royle's list |
The second row is the one the search actually ran over. A puzzle and its reflected, relabelled twin have the same clue count, so proving the result for one representative of each symmetry class proves it for all 6.67 x 10^21 finished grids at once. Five and a half billion grids is still a great many to visit, and the visit happens once per grid rather than once per puzzle inside it.
What the search cost, in seconds per grid
Visiting one grid is cheap, and everything else multiplies out of that one figure. The last revision of checker needed about 3.6 seconds per grid on a single hyperthreaded core.
5,472,730,538 grids at 3.6 seconds each comes to 5.47 million core hours before any overhead is counted. The published total for the run is about 7.1 million core hours spread over six revisions of the program, which is 810 years of one core. The work ran on a 320-node cluster at ICHEC plus time from a PRACE award on JUGENE at Jülich, in jobs of 24 to 84 hours apiece.
The original 2006 checker explains why this could not simply have been started earlier. That version needed around 30 minutes for a single grid, and a 17-clue search the 2011 code completed in under a week would have taken months. One later addition, a vector marking a clue dead once it can no longer appear in any puzzle, was worth enough on its own to turn a month into a day.
Unavoidable sets are what made 3.4 x 10^16 patterns searchable
Nobody enumerated those patterns. The search enumerated hitting sets instead, and the trick rests on a small piece of grid theory.
An unavoidable set is a group of cells whose digits, in a finished grid, can be rearranged to produce a different finished grid. Leave every cell of an unavoidable set blank in a puzzle and the player has at least two valid ways to complete it, so the puzzle is not unique. Every legal clue set therefore has to contain at least one cell from every unavoidable set. It has to hit all of them.
That constraint is what makes the search finish at all. A grid starts with up to 384 minimal unavoidable sets, and once seven clues are down only the smallest 128 still need tracking. The enumeration is arranged so each hitting set is produced exactly once, and therefore each 16-clue puzzle is tested exactly once. The hitting set problem is itself NP-complete, one of Karp's twenty-one, and a plain backtracking version of it was never going to see the end of this.
How the generator on this site cuts a puzzle and keeps it unique
The generator behind the Sudoku game runs the same check in the opposite direction, and the loop is short. It fills a random finished grid, shuffles the 81 cell positions, then tries to empty them one at a time in that shuffled order.
Each removal gets tested. The candidate board goes to a counter that gives up the moment it finds a second solution, and the removal is kept only if the count came back at one. When a second solution turns up, the digit goes straight back and the loop moves to the next position. That one comparison is the entire difference between a puzzle and a grid with more than one answer.
The shuffle is doing real work. Two puzzles cut from one finished grid in two different orders end up with different clue patterns and different solving paths, even though they share a solution. The generator also runs the cut up to three times and keeps the sparsest result, because some finished grids cannot be taken down to the target before uniqueness breaks; on those the loop simply runs out of positions and keeps the harder puzzle it reached.
Nothing in that loop approaches 17, and that is deliberate. A puzzle at the floor has 64 blanks, which leaves very little for a solving technique to bite on, and the reason clue count and difficulty do not track each other is that difficulty depends on which deductions remain available rather than on how many digits are showing. The puzzles come out of a seeded random number generator instead of Math.random, so a bad grid can be handed back as a single number and reproduced exactly — the same determinism that makes a page worth pointing a fake browser at.
Where the same trap catches Minesweeper generators
Uniqueness is the property that makes a puzzle a puzzle, and it is not exclusive to digits in a grid. A Minesweeper board generated by placing mines at random and reading off the numbers is unique only by accident, and the accident fails often enough that a guess is sometimes the only move left. The reasoning is the same in both cases: the clue set has to determine the answer, and the only way to know that it does is to count the answers. That failure mode gets its own piece in the notes on Minesweeper's 50/50 problem.
Pros and cons
Pros
- A counter limited to two solutions returns almost immediately in the common case, so a uniqueness check costs far less than a full solve.
- Enforcing uniqueness during the removal loop removes the need for a separate validation pass, because nothing else can produce a shipped puzzle.
- A seeded generator turns a bad grid into a one-line bug report instead of a screenshot and a guess.
Cons
- The removal loop is a greedy pass, so it stops at the first locally minimal clue set rather than at the best puzzle it could have built.
- A solver call on a sparse grid is exponential in the worst case, and the three-attempt retry multiplies that unbounded cost.
- Hitting a target clue count is a blunt instrument, since the number of printed digits says little about how the puzzle solves.
Sources
- There is no 16-Clue Sudoku (arXiv:1201.0749) — McGuire, Tugemann and Civario on the hitting set method, the 3.6 seconds per grid, the six revisions of checker and the 7.1 million core hours.
- Sudoku puzzles with few clues — David Eppstein's note on what the January 2012 search established and why the result counts as computer-assisted.
- Wolfram MathWorld: Sudoku — the count of finished grids and the 5,472,730,538 essentially different ones, credited to Felgenhauer and Jarvis and to Russell and Jarvis.