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 -- http://mail.python.org/mailman/listinfo/python-list