> Do you think it is possible to reduce the set of all possible solutions > to a small enough set? I personally doubt it, but IF that was the case > an efficient solver could be easily created.
To expand on the concept, assume for the argument sake that the universe of possible solutions can be reduced to a single grid (it is most likely an unrealistic assumption), an efficient solver (of linear/polinomial complexity) could then be created as follows: 1) Transform the starting puzzle grid to match the unique solution for the available cells 2) Apply inverse transformations to the unique solution to get the solution for the starting puzzle. So we shift the focus from finding "the unique value of cells" to finding "equivalent transformations", which should be an easier problem to tackle. Note that the same process also applies if the universe of possible solutions can be reduced to a "small" set. For istance in 4X4 grid with 2X2 submatrices it can proven that all possible solutions are equivalent transformations of the following matrix: 1 2 3 4 3 4 1 2 4 1 2 3 2 3 4 1 If we now start with a given grid, what we want is to transform it so that the available cells match the grid above. Assume for instance that the cell (0,0)=3. The first transformation is to swap all the 3 into 1... Take a note of the transformations, apply them in reverse to the above grid and you get the solution. According to Anton the number of possible solutions can be reduced using 1) number swapping, 2) mirroring, 3) blocks/rows/columns swapping. All those operations create equivalent matrices. For a 9X9 grid, this should give a reduction factor = (9!)*(48)*(6^12) minus the number of duplicated combinations given by the methods above. I am not sure how to calculate the number of duplicated combinations and therefore do not know if the result is "good enough". As mentioned, I doubt that it is a viable approach, but I find it an intriguing approach nevertheless. -- http://mail.python.org/mailman/listinfo/python-list