From:

~~~ ~~~ Subject:

After an initial false start I have now calculated the path-lengths in phase 1 of Kociemba's algorithm. The figures are as follows: path configurations 0: 1 1: 4 2: 50 3: 592 4: 7156 5: 87236 6: 1043817 7: 12070278 8: 124946368 9: 821605960 10: 1199128738 11: 58202444 12: 476 The figure 50 for path length 2 is easily verified by hand. I have a list with information about the configurations requiring a path-length of 12 (actually the paths leading to such a configurations). As should be true for each minimal path in phase 1, all paths start and terminate with a quarter turn of F, R, B or L.

Some details.

Phase 1 of the algorithm brings the cube in the subgroup generated by

[F^2, R^2, B^2, L^2, U, D]. There are in this case 2,217,093,120

(2048 * 2187 * 495) cosets. This can be (and has been) reduced largely

by observing symmetries. In this case rotating the complete cube

along the UD axis by a quarter turn, rotating the cube along the RL

axis by a half turn and mirroring through the FRBL plane reveal

equivalent cosets. Although it is possible to remove *all* cosets that

are equivalent to some canonical coset this was not done. The removal

has only been done for the twists of corner cubes, reducing the factor

2187 to 168, and reducing the number of configurations to be handled to

170,311,680. For each configuration a minimal path was calculated.

This was done starting with an absolute minimum found through the coordinate

axis and through the 2-dimensional coordinate spaces. When a path of that

length was not found the path length was increased and a new attempt was made.

This was done until a path was found. All searches were exhaustive. On

average paths were searched for 3 different lengths (519,177,716 attempts

for 170,311,679 configurations).

The computations were done on a farm of workstations where each workstation

got a portion of the flip dimension (2048 cases of 83,160 configurations).

Computation time for one portion was from 1 to 2 hours (1.5 on average), so

the total computation was about 3000 hours. On a system with enough

memory (50 MByte) it would have taken only 1 hour (this based on experiments

with the corner cubes-only part). It could also have been with a single

processor and a 50 MByte file, in that case CP time would also be about 1

hour, but the I/O time would exceed the 3000 hours very much.

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.

dik

--

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

dik@cwi.nl