From:

Subject:

jerry writes

I read the articles in the archives about Kociemba's algorithm about

a year ago, without (I confess) fully understanding them. In particular,

I do not fully understand what differentiates Kociemba's algorithm from

Thistlethwaite's algorithm, other than it uses a different arrangement

of nested subgroups.

thistlethwaite's algorithm is a method which guarantees solving any cube

in at most 52 (well, now it's 44) face turns. i don't think it was ever

really used to find short solutions (although at the time it was invented,

52 face turns may have been considered short).

kociemba's algorithm is a method for finding short solutions. it didn't

come with any guarantees, (although i've just shown that the first solution

it finds is at most 43 quarter [30 face] turns, and in these extreme cases,

it will quickly find a shorter solution.) kociemba gave an effective way

to navigate through the sequence of subgroups

G = <U, D, F, R, B, L>, H = <U, D, F2, R2, B2, L2>, 1 = <>,

without using enormous tables. (this is how it differs from thistlethwaite's

method, and also why there are (well, were) no guarantees.)

kociemba also allows non-optimal sequences in stage 1 in exchange for

shorter sequences in stage 2. we start by finding all length n sequences

in stage 1, and for each, the shortest sequence in stage 2. then we move

on to length n + 1 in stage 1. kociemba's method is so effective, that

searching through length 14 or 15 in stage 1 is usually quite feasible.

also, this technique has been so successful that it's improved many of the

shortest known maneuvers.

But in the meantime, I wonder if you could verify that Kociemba's

algorithm does not guarantee to find a minimal process? In particular,

is it the case that 26q is a minimal superflip, or is it only an

upper bound?

26q is only an upper bound. my program will eventually find the shortest

process, well, if my os doesn't crash first, the universe doesn't end, ...

but i've only given the shortest maneuver it's found so far. at some

point you've gotta give up. (there are plenty of other patterns waiting

to be stuffed into this program. :-) )

The reason I ask is that I have decided to go ahead and calculate God's

Algorithm under quarter turns for depth 11. (Through depth 10 is

already in hand.) Once that is accomplished, it should be a

*fairly* easy task to establish a lower bound on the superflip

at 22 quarter turns via two half depth searches.

you should search with the list you have right now. (i presume you're

talking about a list of all positions within 10q of START.)

you will either find a maneuver of length <= 20q (unlikely, i'd say),

or you will show that its distance from START is >= 22q. this latter

possibility would be very exciting, since it would raise the lower

bound on the diameter of G.

I can already establish a lower bound of 14 quarter turns on the

superflip.

my program can do this in only a few seconds! in fact, it takes 12q

to get from superflip into the subgroup H. since we may also suppose

that the last twist in a shortest maneuver is U , it follows that

superflip requires at least 13q (and thus 14q , by parity).

mike