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:I prefer my Sudoku with

[tempest69]

Though there must be at least 78 clues to prevent the author from having the opportunity of slipping you an ambiguous puzzle.

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

[Anonymous Coward]

Given that Sudoku with a generalized base of size N (IE, not necessarily 9 symbols but N symbols in an N^2xN^2 grid with blocks of size N) has been shown to be NP complete since 2002 (http://www-imai.is.s.u-tokyo.ac.jp/~yato/data2/SIGAL87-2.pdf), I find it unlikely that even N=3 sudoku (given how rapidly NP complete problems scale in difficulty relative to a given N) will have any small elegant general solution, as literally speaking, all satisfiability problems up to a certain (small) size can be framed within it. It is possible, but IMHO highly unlikely.

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