From:

Subject:

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.

mike