Posted 10 January 2012
There is no 16-clue Sudoku, mathematician shows
As all Sudoku enthusiasts know, a proper Sudoku puzzle must have only one correct answer.
But until now, it has been mere conjecture that the minimum number of clues needed to complete the puzzle, with only one unique solution, is 17, and puzzles with 16 clues or fewer must have multiple solutions.
To test this widely held conjecture, Professor Gary McGuire, a Mathematician from University College Dublin, Ireland, and his collaborators, devised a mathematical algorithm named checker that could be run through a 'supercomputer' to search all possible Sudoku solution grids for a 16-clue puzzle.
Professor Gary McGuire - Photo Credit: Fergal Phillips/Sunday Times
The result: No 16-clue puzzle was found, so all Sudoku puzzles must have at least 17 clues.
Sudoku puzzles need at least 17 clues to be solvable
"A brute force exhaustive search would not have been feasible, so we developed a novel algorithm that made the search possible," says Professor McGuire from the UCD School of Mathematical Sciences, University College Dublin, Ireland.
"Using the original version of the checker algorithm we developed in 2006, it would have taken over 300,000 years on one standard computer to complete the search of all Sudoku solution grids."
"But with our new checker algorithm and access to a 'high-end supercomputer', we were able to complete the search in about 12 months or 7 million CPU hours."
The computation was carried out at the Irish Centre for High-End Computing (ICHEC), a distributed national centre providing support for research in high-performance computing and computational science in the Ireland. Established in 2005, ICHEC is jointly funded by Science Foundation Ireland and the Higher Education Authority.
Sudoku puzzles are believed to have originated from the mathematical concept of Latin Squares – a design where statisticians can control the variation in an experiment related to rows and columns in a field of scientific enquiry.
In Sudoku, the player is presented with a 9x9 grid, where some of the cells are already filled with digits between 1 and 9. To solve the puzzle, the player must complete the grid by filling in the remaining empty cells so that each row, each column and each 3x3 box contains all the digits between 1 and 9 exactly once only.
The puzzle style became internationally popularised following the appearance of puzzles created by Wayne Gould, a retired Hong Kong judge, in the British newspaper, The Times on 12 November 2004.
According to Sudoku lore, Gould first encountered the puzzle in a Tokyo book store, became addicted and began to create his own puzzles before introducing them to the British newspaper.
Wayne Gould is the author of "Su Doku - The Official Utterly Addictive Number-Placing Puzzle".
The new checker algorithm developed by Professor McGuire and his colleagues has applications in software testing, bioinformatics and mobile phone networks.
(Produced by UCD University Relations)
