How hard can Sudoku get? Mathematician has the answer

Posted by Kate Taylor

An Irish mathematician has demonstrated that there's a minimum amount of help necessary for a Sudoku puzzle to be solvable.

If it has any fewer than 17 clues, says Gary McGuire at University College Dublin, the puzzle would have to have more than one correct answer.

McGuire developed an algorithm to come up with his conclusion, which bears out experimental evidence. While Sudoku players have come up with thousands of 17-clue puzzles, nobody's ever been ab le to find a valid 16-clue one.

Most newspaper puzzles offer around 25 clues.

Sudoku involves filling in a 9 by 9 grid with the digits 1 to 9, so that no digit is repeated within the same column, row or 3 by 3 sub-grid.

Checking each possible individual puzzle - of which there are an enormous number - would take far too long. McGuire says that even the original version of his algorithm would have taken over 300,000 years to finish the project on a single computer.

So McGuire devised a new 'hitting-set' algorithm designed specifically for 16-clue puzzles, with the aim of proving that none exists. It detects arrangements of numbers within the completed puzzle that are interchangeable and so could result in multiple solutions.

Even using this technique, the proof took the whole of last year and many thousands of hours of supercomputing time. The work was carried out on the Stokes cluster, owned and run by the Irish Centre for High-End Computing (ICHEC).

The work, says McGuire, has implications beyond Sudoku itself.

"Hitting set problems have applications in many areas of science, such as bioinformatics and software testing," he says.