Mirrored from Sudopedia, the Free Sudoku Reference Guide

Minimal

A minimal puzzle contains the fewest possible number of givens for its solution grid.

A minimal puzzle is also locally minimal and sometimes the term "minimal" is used where "locally minimal" is meant.

It requires a lot of effort to find minimal puzzles. The solution grid must be searched exhaustively for all possible puzzles. For a standard Sudoku, it is believed that the absolute minimum is 17 givens, but this has not been proven. It is perhaps one of the most difficult and least important unsolved problems in mathematics.

There is a known 16-given puzzle with 2 solutions. If there exists a 16-given puzzle with a unique solution, then we can construct an additional 65 17-given puzzles with the same unique solution by adding one of the 65 (81 - 16) remaining cells to the 16-given puzzle. None of these hypothetical 17-given puzzles have turned up on the list of known 17-given puzzles. People have tried various methods to generate 17-given puzzles and mostly they find puzzles that are already on the list. The argument is that "most" of the 17-given puzzles have been found and none of the 65 17-given puzzles generated from the hypothetical 16-given puzzle are among them, therefore it is "likely" that there is no 16-given puzzle.

Of course, this is not a rigorous argument, but it does suggest that if you are trying to decide the question one way or the other, your time might be better spent working on a proof that the minimum is 17 than looking for an example of a 16-given puzzle.

It is also possible to approach the problem from the other end. 7 givens is clearly too few, since it leaves two numbers undetermined. A distributed computing project has shown 8 givens are too few, 9 givens are too few, and 10 givens are too few. So the minimal number of givens has been shown to be at least 11 and at most 17.

External Link

See Also

This page was last modified 21:50, 9 February 2008.