In search of the world's hardest possible Sudoku puzzle

In less than a decade, Sudoku has gone from obscure logic puzzle to global phenomenon. Scientists have built up an entire sub-field of mathematics around this game, mostly to answer one question: what's the toughest possible puzzle that's actually solvable?

Admittedly, that isn't quite how mathematicians usually describe the question, but the end result is the same. Think of it like this - newspapers tend to provide 25 numbers in the 9x9 Sudoku grid as hints. By adding more numbers, the puzzle becomes easier to solve, while taking them away makes the task harder. The question then is what's the minimum amount of numbers a puzzle can have and still be a real, solvable puzzle.

For Sudoku, solvable means the puzzle only has one unique solution. So far, puzzle constructors have reported that they have been unable to create a solvable puzzle with fewer than 17 clues - with only 16 numbers provided, the puzzles always yield multiple solutions. That obviously suggests the lower limit is 17, but that can't simply be assumed in mathematics. A formal proof would be required, and the only way to do that would be to create a computer algorithm that could somehow check through all the countless possible combinations of Sudoku grids with 16 numbers given.

That's exactly what Gary McGuire of University College Dublin did. Faced with a task that colleague Gordon Royle of the University of Western Australia compared to "climbing the highest mountain", McGuire developed a program that could test just a fraction of 16-clue puzzles and still figure out with near certainty whether all such puzzles are impossible. Writing for Nature, Eugenie Samuel Reich describes this process:

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.

So far, McGuire's work has been largely accepted by mathematicians as clinching proof that 17-clue puzzles are indeed the minimum workable amount, and thus the most difficult possible puzzles. That said, this result can't be confirmed for a little while yet - after all, someone else is going to have to devote two years' worth of a super-computer's processing time just to double-check the result, and that probably won't happen immediately.

Read more at Nature. Image by Eduardo Mueses on Flickr.