Dan mused:
Suppose a sudoku has *exactly* 2 solutions. Then what is the maximum number of boxes that can differ in the two solutions?
Surely it's possible to attain 18: take a sudoku and erase all the 3s and 8s. As long as the permutation i -> the column containing the 8 in the row where the 3 was in column i is a 9-cycle, you can fill it back in as it was originally or with 3 and 8 swapped, and in no other way. I think many sudoku will have such a 9-cycle -- um, the sample that appears in the Wikipedia sudoku article does (for 3 and 8, in fact!), for example. (Of course, this will work for latin squares also.) Needless to say, I have no reason to think this is maximal. --Michael Kleber -- It is very dark and after 2000. If you continue you are likely to be eaten by a bleen.