Advertisement
Dublin: 10 °C Tuesday 19 March, 2024
A contestant works on his puzzle in the final round during the Philadelphia Inquirer Sudoku National Championship. Joseph Kaczmarek/AP/Press Association Images
Groundbreaking

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

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

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

Your Voice
Readers Comments
20
    Submit a report
    Please help us understand how this comment violates our community guidelines.
    Thank you for the feedback
    Your feedback has been sent to our team for review.