Lower Limit Found For Sudoku Puzzle Clues

Posted by timothy on Sunday January 8, 2012 @06:46AM from the 17-ain't-young dept.

ananyo writes "An Irish mathematician has used a complex algorithm and millions of hours of supercomputing time to solve an important open problem in the mathematics of Sudoku, the game popularized in Japan that involves filling in a 9X9 grid of squares with the numbers 1–9 according to certain rules. Gary McGuire of University College Dublin shows in a proof posted online [PDF] that the minimum number of clues — or starting digits — needed to complete a puzzle is 17; puzzles with 16 or fewer clues do not have a unique solution. Most newspaper puzzles have around 25 clues, with the difficulty of the puzzle decreasing as more clues are given."

1 of 121 comments (clear)

Min score:

Reason:

Sort:

Re:Well this will solve world hunger. by Malk-a-mite · 2012-01-08 06:56 · Score: 5, Informative

Don't trouble yourself to read to the bottom of the story....
"McGuire says that his approach may pay off in other ways. The hitting-set idea that he developed for the proof has been used in papers on gene-sequencing analysis and cellular networks, and he looks forward to seeing if his algorithm can be usefully adapted by other researchers. “Hopefully this will stimulate more interest,” he says. "