Sudoku solver: reduction + brute force

[Anton Vredegoor]

ago wrote:

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

No I don't think so, but it's a great idea :-) . Iff we would have some
ultimate symmetry detector we could reduce all positions to variations
of a few base types and start *generating* solutions from there in
stead of checking possible mistakes.

> In reducing the set of all solutions for instance you could always swap
> the numbers (3rd axis) so that the first submatrix reads
> [[1,2,3],[4,5,6],[7,8,9]]. By this we reduced the set of solutions by
> 362880. You can then always move blocks, columns and rows to fix the
> following elements (1,4)=4, (4,1)=2, (9,9)=9. Further reductions are
> still possible, but I do not know how far can this go and if the end
> result is a small enough set.

I think one could reduce more than just a factor 9! . A 3-dim cube has
48 symmetric mirror images and we could multiply 9! by this. Then there
are the horizontal slice swaps and the whole 3-slice swaps. Anyway I
wasn't thinking about a grand unified theory but more about limiting
the search space (in a depth first tree) early.

If for example some field would allow only 2 values it would pay off to
check that field first in the search (before fields that can have say 9
values) because that would be the next best thing to having that value
as a fixed starting value.

Similarly if we would only check a subtree position once (by using the
hash) it could save some computations, but I have no idea how effective
it would be, all this mirrorring could be expensive too. On the other
hand this is done on the single leaf level, perhaps cutting off whole
branches, so it might indeed pay off very much. Remember that some
subtrees can be identical even though the routes to get to there were
different.

Here's the idea to make all the mirrors (I have the code at home, but I
can't reach it now, but it should be easy to code):

Say one has dimension x with values [0,1,....,8]

Now rescale this to [-4,-3,...,+4]

Then do this for all x,y and z coordinates.

Now to generate all mirrors, make all 6 permutations and all +-
variations of all coordinate points  x,y,z for each mirror.

So x,y,z gives 6 permutations and doing +-x,+-y,+-z for each of these
makes for 48 (6*2**3) mirror images of each point.

for example a coordinate [-3,-2,-1] mirrored through mirror [z,-x,y]
would give coordinate point [-1,3,-2].

Do this for all points.

Repeat for each mirror.

Now convert back to [0,1,..8] coordinates and select the smallest
mirrored cube.

Eh, maybe math notation wouldn't be such a bad idea after all, only
then I wouldn't be able to read what I wrote here. I hope you can :-)

Anton