AN IRISH MATHEMATICIAN has discovered there is a limit to how hard a Sudoku puzzle can get.
A true Sudoku only has one solution and to achieve this there must be a minimum of 17 clues (or numbers provided), Professor Gary McGuire of University College Dublin has discovered.
Sudokuists have always thought that 17 was the magic number but were never completely sure…until now.
The UCD professor’s algorithm named checker was ran through a “supercomputer” to search all possible Sudoku solution grids for a 16-clue puzzle.
But no 16-clue puzzle was found.
“A brute force exhaustive search would not have been feasible, so we developed a novel algorithm that made the search possible,” said McGuire.
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 9x9 grid puzzles are believed to have originated from Latin squares but regained popularity in 2004 following their appearance in The Times in London.
They soon became the math lovers’ crossword and appear in daily newspapers across the world.
Professor McGuire’s computation was carried out at the Irish Centre for High-End Computing (ICHEC). The algorithm also has applications in software testing, bioinformatics and mobile phone networks.