Sudoku and the Pace of Mathematics
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 least one cell from each known unavoidable set. Finding those particular sets of starting clues is a specific instance of a more general problem, known to mathematicians as the “hitting set problem.” The really clever part of McGuire’s work is the development of algorithms for solving the hitting set problem in a reasonable amount of time. Solving the minimum-clue problem for Sudoku was just an application of this new algorithm.
Of course, caution is required until researchers have had time to check carefully the details of McGuire’s proof. It is one of the cruelties of mathematics that subtle errors can elude even the most careful of practitioners. We can certainly say, though, that the techniques being employed here are very plausible and interesting. They might also be useful for polishing off other “minimal clue” problems in Sudoku. For example, if we require that the starting clues be placed symmetrically, then eighteen clues is the smallest that is known (as shown below left; puzzle taken from Taking Sudoku Seriously). On the other hand, in Sudoku X, in which the two main diagonals join the rows, columns and blocks as valid Sudoku regions, the current minimum is twelve (see below right; puzzle adapted from one in Ruud’s online collection of 12-clue Sudoku X puzzles).
McGuire’s paper illustrates two of the realities of contemporary mathematics. The first is the prominent role of the computer. Nowadays it is increasingly difficult to determine which puzzles should be viewed as math problems, and which are really problems for computer scientists.
But the second is the pace of mathematical discovery. We learned of McGuire’s work as we were traveling to a mathematics conference at which we were organizing a session on Sudoku puzzles. One of us had a talk prepared in which this problem was described as unsolved. It was very exciting to be able to use the conference to report on this development. Our book on the mathematics of Sudoku has only been out for a few weeks, but it might already be outdated, at least with regard to this one problem.
Jason Rosenhouse is Associate Professor of Mathematics at James Madison University. He is the author of Taking Sudoku Seriously: The Math Behind the World’s Most Popular Pencil Puzzle and the forthcoming Among the Creationists: Dispatches from the Anti-Evolutionist Front.