[next] [prev] [up] Date: Fri, 16 Dec 94 17:33:48 -0500
[next] [prev] [up] From: michael reid <mreid@ptc.com >
[next] [prev] [up] Subject: Re: Cyclic Decomposition

tim writes

If a certain state (such as the 12 flip) is known to be reachable
in no more than 20 moves, then isn't that state within reach of
a brute force search? Start one brute force at the initial state,
one at the final state, expand the position trees one move at a time
until the trees touch. A state 20 moves from start will require a
tree (well, two trees) 10 moves deep, which is about 10 billion states.

unfortunately, this estimate is too optimistic. the number of positions
within 10 face turns of start is more like 2.6 x 10^11.

[ keep in mind that while "billion" means  10^9  in the u.s., it may
  mean  10^12  elsewhere. ]

That seems achievable in a reasonable time on fast computers of today.
Doesn't it?

i don't know, but it would be nice if it were possible.

i recall that dik winter was doing some work on this front, although i
think he was working on "superfliptwist". also, he was using kociemba's
algorithm (first stage only). my impression was that this would take
too long. (any results here, dik?)

however, there's a method similar to the one tim mentions that hasn't
received much attention here. i don't have all the details handy, but
here's a sketch:

the idea is to start with a list of permutations L and to
generate (on the fly!) all products p1 p2 (with p1, p2 in the list L)
in (lexicographically) increasing order. this means that while the list
itself is stored in memory, the list of products (denoted L L) need
not be. also, the technique for doing this (which i don't remember
offhand) is easily adapted to generate all products q p1 p2 where
q is a fixed permutation and p1 p2 are in the list L (q L L), again
in (lexicographically) increasing order, and again, on the fly.

now let L be the list of all configurations within 5 face turns of
start, and let q be "superflip" or "superfliptwist". now simultaneously
generate the products L L and q L L in increasing order, and look for
common configurations. a common configuration gives

p1 p2  =  q p3 p4   ==>  q  =  p1 p2 p4^-1 p3^-1

which gives a manuever of (at most) 20 face turns for q.

of course, this technique can be used for quarter turns as well.

i don't know much about the practicality of implementing this algorithm,
but i'd be happy to hear from anyone who's done it, or even thought
about it.


[next] [prev] [up] [top] [help]