By Jason Rosenhouse
Among mathematicians, it is always a happy moment when a long-standing problem is suddenly solved. The year 2012 started with such a moment, when an Irish mathematician named Gary McGuire announced a solution to the minimal-clue problem for Sudoku puzzles.
You have seen Sudoku puzzles, no doubt, since they are nowadays ubiquitous in newspapers and magazines. They look like this:
Your task is to fill in the vacant cells with the digits from 1-9 in such a way that each row, column and three by three block contains each digit exactly once. In a proper puzzle, the starting clues are such as to guarantee there is only one way of completing the square.
This particular puzzle has just seventeen starting clues. It had long been believed that seventeen was the minimum number for any proper puzzle. Mathematician Gordon Royle maintains an online database which currently contains close to fifty thousand puzzles with seventeen starting clues (in fact, the puzzle above is adapted from one of the puzzles in that list). However, despite extensive computer searching, no example of a puzzle with sixteen or fewer clues had ever been found.
The problem was that an exhaustive computer search seemed impossible. There were simply too many possibilities to consider. Even using the best modern hardware, and employing the most efficient search techniques known, hundreds of thousands of years would have been required.
Pure mathematics likewise provided little assistance. It is easy to see that seven clues must be insufficient. With seven starting clues there would be at least two digits that were not represented at the start of the puzzle. To be concrete, let us say that there were no 1s or 2s in the starting grid. Then, in any completion of the starting grid it would be possible simply to change all the 1s to 2s, and all the 2s to 1s, to produce a second valid solution to the puzzle. After making this observation, however, it is already unclear how to continue. Even a simple argument proving the insufficiency of eight clues has proven elusive.
McGuire’s solution requires a combination of mathematics and computer science. To reduce the time required for an exhaustive search he employed the idea of an “unavoidable set.” Consider the shaded cells in this Sudoku square:
Now imagine a starting puzzle having this square for a solution. Can you see why we would need to have at least one starting clue in one of those shaded cells? The reason is that if we did not, then we would be able to toggle the digits in those cells to produce a second solution to the same puzzle. In fact, this particular Sudoku square has a lot of similar unavoidable sets; in general some squares will have more than others, and of different types. Part of McGuire’s solution involved finding a large collection of certain types of unavoidable sets in every Sudoku square under consideration.
Finding these unavoidable sets permits a dramatic reduction in the size of the space that must be searched. Rather than searching through every sixteen-clue subset of a given Sudoku square, desperately looking for one that is actually a proper puzzle, we need only consider sets of sixteen starting clues containing at l