I saw the discussion of Dale and Don about the search order
(fillpattern) for rubiks tangle come by, and wondered why they both
missed an even better search order (the best?):Don: Dale: Jan: Equivalent to: 1 3 5 7 9 1 2 6 10 15 1 2 5 10 17 17 16 15 14 13 2 4 6 8 10 3 4 7 11 16 3 4 6 11 18 18 5 4 3 12 11 12 13 14 15 5 8 12 17 20 7 8 9 12 19 19 6 1 2 11 16 17 18 19 20 9 13 18 21 23 13 14 15 16 20 20 7 8 9 10 21 22 23 24 25 14 19 22 24 25 21 22 23 24 25 21 22 23 24 25
I missed it on the 5x5 because my program was fast enough that I didn't
look further. When I modified my program to try the 10x10 last week, I
did come up with the ordering Jan suggests. It shaved about 1/3 the
running time off my 5x5 search, but it actually doesn't seem to make
that big a difference in the 10x10.
It turns out the 10x10 search isn't quite as bad as I thought, because
the tree does get trimmed rather early. When a piece is constrained on
two edges, there are on average only 2/3 choices for that piece. I've
got my program chugging along, and so far it has eliminated 4 of the 96
choices for piece (w/ orientation) for the upper left corner. There are
4896 choices for the first 4 points in the search order, and it's going
through one choice per 25 minutes on average, so it'll finish in a mere
3 months, if I have the patience for it. (I may try to dig up some
otherwise idle workstations to leave running over the holiday break.)
-- Don.