dasimov@earthlink.net wrote:
From the link you provided I see that another interesting question is, What is the smallest number n such that *every* sudoku solution can be reduced to n entries having that solution as its unique completion?
The answer to this is 19, although I can't prove it. There is a canonical grid 123456789 456789123 789123456 231564897 564897231 897231564 312645978 645978312 978312645 which requires 19 clues. Here is a proof that at least 18 are required: The grid can be partitioned into 9 disjoint 3x3 Latin squares of the form 123 231 312 (three of these in each stack of three columns). At least 2 clues must be included from each of the 3x3 Latin squares - if only one clue then the other two digits could be interchanged within that Latin square to obtain another completed sudoku grid. (This has been discovered by lots of people.) It's feasible on the computer to run through all possible ways of choosing two clues from each 3x3 Latin square, and none of these give a puzzle with a unique solution. So at least 19 are required. Guenter did this check, and found one with 19. Finally, if this grid has a 19, then all grids have a 19 (and probably an 18). This completed grid has the largest symmetry group of all grids, and there's a principle that grids with higher symmetry don't have puzzles with smaller numbers of clues. Of course I can't prove that part... Gary McGuire