Steve Rowley wrote: << . . . On the other hand, if you mean a "typical" sudoku in the sense that it's randomly selected, then we can MEASURE that! Assuming that "difficulty" translates into computer time, which is of course dubious... . . .
There ought to be an objective measure of the *paucity* of useful information readily provided by the diagram. IDEA: If (i,j) is empty, let P(i,j) be the subset of {1,2,...,9} that does NOT appear in the union of row i, column j, and the 3x3 box containing (i,j); if (i,j) is filled with the number k, then P(i,j) = {k}. (P stands for "Possible set".) Let s(i,j) := #(P(i,j)). I propose that a good intrinsic measure of the difficulty of a Sudoku is the *geometric* mean of the 81 s(i,j)'s, since the number of possibilities is multiplicative. -------------------------------------------------------------------------------------- It would be interesting to see how this measure compares with the time it takes software to solve a puzzle. --Dan