Irish mathematician solves complex Sudoku riddle

WITH the help of a complex algorithm and by utilising millions of hours of supercomputing time, an Irish mathematician has worked out that Sudoku players need a minimum of 17 clues to definitively solve the puzzle.

Gary McGuire of University College Dublin, has established a puzzle with 16 clues or less will not have a unique solution.

Mathematicians at a conference in Boston over the weekend concluded Mr McGuire’s proof is likely valid and an important advance in the growing field of Sudoku maths. “The approach is reasonable and it’s plausible.

“I’d say the attitude is one of cautious optimism,” Jason Rosenhouse, a mathematician and the co-author of a newly released book on the maths of Sudoku said.

The puzzle requires players to fill out a 9x9 grid with the numbers 1-9 in such a way that no digit is repeated within the same column, row, or within one of nine 3x3 subgrids.

While it had been speculated 16-clue puzzles with unique solutions do not exist, Gary McGuire developed a “hitting set algorithm” to definitively prove the theory.

It searched for what he called unavoidable sets, or arrangements of numbers within the completed puzzle that are interchangeable and so could result in multiple solutions. In order to prevent the unavoidable sets from causing multiple solutions, the clues must overlap, or “hit”, the unavoidable sets.

Having spent two years testing the algorithm, Mr McGuire admitted he now prefers “doing the crossword”.


Lifestyle

Food news with Joe McNameeThe Menu: Upcoming food highlights

THE health properties of tea have long been advertised. “It maketh the body active and lusty” a 1660 promotion suggested. However, before you dunk your teabag into a mug of steaming water, spare a thought for the environment. Some have polypropylene to help to seal them and it doesn’t decompose.Storm in a teacup: Top 8 loose-leaf teas

Bestselling author Isabel Allende talks to Rowena Walsh about life, grief, and why it’s never too late to fall in loveIsabel Allende: It's never too late to fall in love

Cliffs of Moher Retreat owner Michelle Moroney has written a book on finding self-worth and stepping back from our 24/7 lives. She talks to Marjorie Brennan about the need to unwindMichelle Moroney highlights the need to take stock of our lives

More From The Irish Examiner