Mathematician claims breakthrough in Sudoku puzzle

An Irish mathematician has used a complex algorithm and millions of hours of supercomputing time to solve an important open problem in the mathematics of Sudoku, the game popularized in Japan that involves filling in a 9x9 grid of squares with the numbers 1-9 according to certain rules.

Gary McGuire of University College Dublin shows in a proof posted online on January 1 that the minimum number of clues--or starting digits--needed to complete a puzzle is 17; puzzles with 16 or fewer clues do not have a unique solution. Most newspaper puzzles have around 25 clues, with the difficulty of the puzzle decreasing as more clues are given.

The emerging consensus among mathematicians at a conference in Boston, Mass., on January 7 was that McGuire's proof is probably valid and an important advance in the growing field of Sudoku mathematics.

"The approach is reasonable and it's plausible. I'd say the attitude is one of cautious optimism," says Jason Rosenhouse, a mathematician at James Madison University in Harrisonburg, Va., and the co-author of a newly released book on the mathematics of Sudoku.

The rules of Sudoku require puzzlers to fill out a 9x9 grid with the numbers 1-9 so that no digit is repeated within the same column, row, or 3x3 sub-grid. The clues are the numbers that are filled in to begin with, and enthusiasts have long observed that although there are some puzzles with 17 clues, no one has been able to come up with a valid 16-clue puzzle. That led to the conjecture that 16-clue puzzles with unique solutions simply do not exist. A potential way to demonstrate that could be to check all possible completed grids for every 16-clue puzzle, but that would take too much computing time. So McGuire simplified the problem by designing a 'hitting-set algorithm'. The idea behind this was to search for what he calls unavoidable sets, or arrangements of numbers within the completed puzzle that are interchangeable and so could result in multiple solutions. To prevent the unavoidable sets from causing multiple solutions, the clues must overlap, or 'hit', the unavoidable sets. Once the unavoidable sets are found, it is a much smaller--although still non-trivial--computing task to show that no 16-clue puzzle can hit them all.

Having spent two years testing the algorithm, McGuire and his team used about 700 million CPU hours at the Irish Centre for High-End Computing in Dublin, searching through possible grids with the hitting-set algorithm. "The only realistic way to do it was the brute force approach," says Gordon Royle, a mathematician at the University of Western Australian in Perth who had been working on the problem of counting 17 clue puzzles using different algorithms. "It's a challenging problem that inspires people to push computing and mathematical techniques to the limit. It's like climbing the highest mountain."

A consequence of the approach taken is that it will take some time for others to get enough computing time to check the proof, says Laura Taalman, a mathematician also at James Madison University, who co-authored the book Taking Sudoku Seriously: The Math Behind the World's Most Popular Pencil Puzzle with Rosenhouse. Taalman notes that the book, which came out last week, is already outdated: it says that the problem remains open and that whoever solves it will be a "rock star."

McGuire says that his approach may pay off in other ways. The hitting-set idea that he developed for the proof has been used in papers on gene-sequencing analysis and cellular networks, and he looks forward to seeing if his algorithm can be usefully adapted by other researchers. "Hopefully this will stimulate more interest," he says. 

But he says that, ironically, as he dedicated more of his time to the mathematics of the conundrum, he spent less time enjoying the puzzle. "I still find it a nice way to relax now and then but to be honest I prefer doing the crossword," he says.