UCD mathematician discovers sudoku's magic number - it's 17

Puzzle breakthrough:A UNIVERSITY College Dublin mathematician has managed a world-first – confirming the minimum number of starting clues needed to deliver a unique answer when playing the number grid game Sudoku. The public fascination with the number grid game Sudoku has diminished somewhat but that has not cooled the interest of mathematicians in the game.

Prof Gary McGuire in UCD’s school of mathematical sciences joined the Sudoku craze back in 2004. But as director of the Claude Shannon Institute – which specialises in advanced cryptography – it did not take long before he was trying to solve the ultimate Sudoku puzzle.

“I started wondering what the fewest number of clues you could possibly have and have a unique solution,” he says. Too few clues and the grid can’t be solved, too many and there may be multiple answers. He and former student Bastian Tugemann now based in Munich built an algorithm, a software- based method to answer this question.

They fed in thousands of completed grids to see if that would deliver but it only showed that no grid had been solved with fewer than 17 starting clues. The problem was this did not prove that 17 was a minimum, only that no solved grid had yet been found with less than 17.

The two went back to the drawing board and developed a more powerful algorithm, a clever piece of work that hugely reduced the number of checks needed to confirm the clues needed to solve a grid. Gilles Civario ran the numbers on the supercomputer at the Irish Centre for High-End Computing in Dublin and despite the algorithm it still took seven million computer processor hours to deliver a final answer.

So now it is official. If someone hands you a Sudoku grid with less than 17 clues, just hand it back and say it’s impossible to solve.

- Dick Ahlstrom