Sudoku solver: reduction + brute force

[ago]

> 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.