Lower Limit Found For Sudoku Puzzle Clues

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

Comments

Re:Well this will solve world hunger.

[Malk-a-mite]

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

Re:Proof use a lot of brute force

[JoshuaZ]

Er, I made a mistake here. One just needs to check this for 16 clues, so 81 choose 16, and 9^16 are the numbers one cases about, so one gets around 10^30. The other important thing to note is that this is the set of possible clue arrangements. Not all of these lead to valid sudokus at all. There are only around 10^21 of those.

Re:Cue the morons.

[TheRaven64]

Or, for those more interested in computers, sudoku has quite a few things in common with a number of error correction techniques and some compression algorithms. This particular result is moderately interesting from an information theoretic perspective and is probably a fairly minor part of a larger project that may well yield practical results.

Re:What about...

[The Askylist]

No - there exist multiple solutions for up to 77 clues (81 -4), where a particular configuration of numbers exists:

1 x x 2 x x x x x
2 x x 1 x x x x x
x x x x x x x x x
x x x x x x x x x
x x x x x x x x x
x x x x x x x x x
x x x x x x x x x
x x x x x x x x x
x x x x x x x x x
...

or

2 x x 1 x x x x x
1 x x 2 x x x x x
x x x x x x x x x
x x x x x x x x x
x x x x x x x x x
x x x x x x x x x
x x x x x x x x x
x x x x x x x x x
x x x x x x x x x
...

(where the x's are the same in each configuration) are two distinct solutions, but the 77 x's are the same clues.

(Sorry - couldn't be bothered to fill the x's in!)

Re:Proof use a lot of brute force

[JoshuaZ]

This doesn't follow. The question here isn't the general question of solving a generalized Sudoku grid (which is NP complete) but rather the problem of the minimum size needed for a unique solution. This isn't the same problem. It could very well be that there's an easy answer to this question and that the numbers follow some easy pattern (like say 2n-1 for n symbols).