From:

~~~ Subject:

Because it might interest the readers and to be ahead of Peter Beck:

Saturday I received CFF (Cubism For Fun) # 28.

It has an interesting article by Herbert Kociemba from Darmstadt, who

describes his program to solve Rubik's Cube. He states that he has not

yet encountered a configuration that required more than 21 moves. A short

description follows:

Basicly the program consists of two stages, based on the groups:

G0: [U,D,R,L,F,B]

G1: [U,D,R^2,L^2,F^2,B^2]

G2: I

The stages are from G0 to G1 and next from G1 to G2. Note that the first

stage is the combination of the first two stages of Thistlethwaite, and

the last stages combine his last two stages.

His first stage can loosely be described as working in a three dimensional

coordinate system where the coordinates are resp. twist, flip and permutation.

He searches his way until the coordinate [0,0,0] is reached. Most important

here is that he is able to find multiple ways. The second stage is similar,

although he is not very clear here.

He uses lookup tables, but does not tell us how large his lookup tables

are. But his program runs on 1 MByte Atari ST. The heart is coded in

a few lines of 68k assembly, the remainder in GFA Basic. As far as I

know GFA Basic it can be interpreted, but also compiled. He does also

use tree pruning.

What he does is find successive solutions in stage 1 and fit solutions

from stage 2. Letting the system run longer generally finds shorter

solutions.

His claims are on average less than 14 turns in stage 1, on average less

than 10 turns in stage 2. But according to his article this is not completely

deterministic, so there is no proven upperbound. Perhaps a proof can be

found; I do not know. In practice he finds an upperbound of 21 moves, which

is indeed far better than other algorithms do obtain.

To take this in perspective here Thistlethwaites results from Singmaster's book:

Stage 1 2 3 4

Proven 7 13 15 17

Anticipated 7 12 14? 17

Best Possible 7 10? 13? 15?

(Are there configurations that require the maxima proven for Thistlethwaites

algorithm?)

Apparently the combination of stages largely reduces the number of turns

required.

In CFF 25 there was an article by Hans Kloosterman which did already improve

on the number of moves. His stages 1 and 2 are identical to Thistlethwaites,

he has a third stage that combines the 3rd and 4th stages of Thistlethwaite.

He reports a proven maximum for his three stages of 7, 10 and 25 moves, so

slightly better than Thistlethwaites conjectured best figures.

Kociemba's algorithm appears however to be a big leap forward, although there

are no proofs yet. One example:

In 1981 Christoph Bandelow wrote a book where he offered a prize for the

shortest sequence of moves that would flip every edge cuby and twists

every corner cuby. The deadline was September 1, 1982; at that time the

prize was offered for a 23 move manoeuvre. As Christoph writes:

All solutions presented after the main deadline and shorter than

all solutions submitted before were also proised a prize. Using

his very ingeneous new search program Herbert Kociemba, Darmstadt,

Germany now found:

DF^2U'(B^2R^2)^2LB'D'FD^2FB^2UF'LRU^2F'

for 20 moves.

Kociemba himself writes about this:

Our first solution had 12 moves in stage 1 and 14 moves in stage 2.

In progress solutions 12+13, 12+12 and 12+11 were found. However,

as soon as we introduced manoeuvres of 13 moves in stage 1, we found

successively 9, 8 and at last 7 moves for stage 2. The program was

stopped after treating about 3000 solutions.

He further states that the first solution in general takes 95 seconds, but

successive solutions take much shorter, and in general he finds one of less

than 22 moves in a few hours on his 8 MHz Atari.

What is clear is that one does not need the minimal solution in one stage

to get the minimal overall total.

dik

--

dik t. winter, cwi, kruislaan 413, 1098 sj amsterdam, nederland

dik@cwi.nl