This site uses cookies to improve your experience and to provide services and advertising. By continuing to browse, you agree to the use of cookies described in our Cookies Policy. You may change your settings at any time but this may impact on the functionality of the site. To learn more see our Cookies Policy.
Dublin: 22 °C Tuesday 4 August, 2020

Can't get harder than this: Sudoku puzzles must have 17 clues

It was a Dublin mathematician who finally solved this quandary. Yay!

A contestant works on his puzzle in the final round during the Philadelphia Inquirer Sudoku National Championship.
A contestant works on his puzzle in the final round during the Philadelphia Inquirer Sudoku National Championship.
Image: Joseph Kaczmarek/AP/Press Association Images

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 9×9 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.

For Professor McGuire’s study, follow this link>

Read: Want to live out that childhood dream of being an astronaut?>

  • Share on Facebook
  • Email this article

Read next: