A Sudoku grid with a single valid solution cannot start with 16 clues, however those clues are arranged. Gary McGuire’s team at University College Dublin proved it in a paper that went public in 2011, and Nature covered the result on 6 January 2012. Seventeen clues, not sixteen, is the true floor.
more
Getting there meant checking a number too large to search by hand. McGuire’s team, working with Bastian Tugemann and Gilles Civario, searched within that space for any 16-clue puzzle that could stand on its own.
How do you search a number that large?
The team’s method turned on a shortcut called a hitting set. Inside any completed grid sit clusters of cells, called unavoidable sets, where wiping every clue out of the cluster leaves more than one way to fill the puzzle back in. A puzzle keeps its single solution only if its clues plant at least one entry inside every unavoidable set the grid contains. Miss one, and a second valid grid opens up.
Rather than build 16-clue puzzles from nothing, the team took each completed grid in turn and asked whether any 16-clue arrangement could hit every unavoidable set inside it at once. None could. Enumerating hitting sets efficiently is itself hard: it belongs to Karp’s list of 21 classically difficult problems, and an ordinary trial-and-error search would not finish in reasonable time even on today’s fastest machines. The team built a purpose-made algorithm instead.
Why a year of computing, not an afternoon
The team’s search software, named checker, had already existed since 2006, but its first version was slow. By the team’s own estimate, that original version would have needed more than 300,000 processor-years to check every grid. The new hitting-set algorithm cut that to roughly 800 processor-years, run in parallel over about a year at the Irish Centre for High-End Computing. Nature’s own report of the total was wrong at first. It said 700 million hours of CPU time, then corrected that to about 7 million. Seven million hours comes out to almost exactly 800 years on one processor, so the two figures, reached by different routes, agree.
The result found no 16-clue puzzle anywhere in that search. Had one existed, the team wrote, the search would have found it. It joins a long line of computer-assisted proofs. Precedents include the four-colour theorem, proved by Appel and Haken, the Kepler conjecture on sphere-packing, proved by Thomas Hales, and the weak Goldbach conjecture.
Why nobody had found a 16-clue puzzle by hand
The question had stood open for years before the computers settled it. Sudoku’s craze traces back to a puzzle style called Nanpure, which Japanese magazines had run since the 1980s. The name adapted “Number Place,” a puzzle Dell Magazines had published in the United States since the 1970s. Once Sudoku spread worldwide in the early 2000s, a Japanese enthusiast, Sinpei Araki, found a 17-clue grid with a unique solution by hand in 2006. Nobody who tried could get below that, which left an open question: was 16 simply undiscovered, or genuinely impossible?
What the proof settles, and what it leaves alone
Any published puzzle that claims a unique solution on 16 clues or fewer is now known to be either a misprint or wrong. The proof says nothing, though, about how hard a puzzle feels to solve. A 17-clue grid can fall to ordinary logic when its clues open the board quickly. A puzzle built from far more givens can still demand deeper technique before it yields. Clue count and difficulty are different properties of a puzzle. Neither measures the other.
Gordon Royle’s catalogue lists more than 49,000 distinct 17-clue puzzles, a lower bound on a catalogue believed to be very nearly complete. And a proof that needs no computer at all is still some way off. A 7-clue puzzle can never have one solution, because its two missing digits always swap to make a second valid grid. Proving the same thing for an 8-clue puzzle, by pen and paper alone, is a step nobody has yet managed.
