[next] [prev] [up] Date: Fri, 29 May 92 19:20:22 +0100 (MET)
[next] ~~~ [up] From: Hans Kloosterman <J.M.Kloosterman@research.ptt.nl >
[next] ~~~ [up] Subject: Lower-bound Kociemba's algorithm

Dik Winter writes:

Using this result and the result by Hans Kloosterman the diameter of the
cube group is at most 37. I conjecture the maximal path length in phase 2
of Kociemba's algorithm is 16, although the requirements on computer time
cq. memory do inhibit calculations at this moment (only in memory would be
feasible, but that requires 500 to 1000 MByte and computation time would be
about one day). This figure of 16 would reduce the upperbound of the groups
diameter to 28.

Unfortunately Dik's conjecture for phase 2 is too optimistic.
Recall the maximum distances of the 4 stages of my algorithm:
1. 7 moves within the group <R, L, F, B, U,D>
2. 10 moves within the group <R, L, F2,B2,U,D>
3. 8 moves within the group <R2,L2,F2,B2,U,D>
4. 18 moves within the group <R2,L2,F2,B2,U,D>

(Stage 3 and 4 together requires at most 25 moves.)

These number of moves are minimal and cannot be improved within their
group of moves. (Stage 2 can also not be improved using all moves.)
>From this we may conclude that the maximum path length in stage 2 of
the algorithm of Kociemba is at least 18 moves.

Taking the results of Dik Winter for stage 1 into account, the lower-bound
for the mximum of Kociemba's algorithm becomes 30 moves.

Hans Kloosterman


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