The Daily Edge uses cookies. By continuing to browse this site you are agreeing to our use of cookies. Click here to find out more »
Dublin: 9 °C Wednesday 22 November, 2017
Advertisement

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

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:

COMMENTS (20)