Why 17 clues?
A sudoku needs at least 17 clues to have one solution. How a 2012 computer search of every grid proved there is no 16-clue sudoku, in plain words, with three real 17-clue puzzles to play.
A sudoku is only fair if it has exactly one solution. The fewest clues that can manage that is 17.
Tens of thousands of 17-clue sudokus are known, but for years nobody could say whether a 16-clue one existed. In 2012 a computer search settled it: there is none.
The proof in short
- Gary McGuire, Bastian Tugemann and Gilles Civario set out to check every possible solution grid for a 16-clue puzzle.
- Many grids are really the same grid: relabel the digits, rotate or reflect it, or shuffle rows within a band, and nothing about its puzzles changes. That leaves 5,472,730,538 essentially different grids to check.
- For each grid, the program first listed its unavoidable sets, like the four-cell rectangle in the walkthrough.
- Then it looked for 16 cells that touch every one of those sets at once, what mathematicians call a hitting set. Any 16-clue puzzle would have to be such a set, so finding none for a grid rules it out.
- It found none for any grid. The search took about 7 million CPU hours on a supercomputer.
Read more
- There is no 16-Clue Sudoku — McGuire, Tugemann and Civario’s paper (PDF)
- Minimum sudoku — Gordon Royle’s 17-clue collection (archived copy)