From dik@cwi.nl Thu May 28 12:33:49 1992 Return-Path: Received: from charon.cwi.nl by life.ai.mit.edu (4.1/AI-4.10) id AA02289; Thu, 28 May 92 12:33:49 EDT Received: from boring.cwi.nl by charon.cwi.nl with SMTP id AA03118 (5.65b/2.10/CWI-Amsterdam); Thu, 28 May 1992 17:18:31 +0200 Received: by boring.cwi.nl id AA00307 (5.65b/2.10/CWI-Amsterdam); Thu, 28 May 1992 15:00:49 +0200 Date: Thu, 28 May 1992 15:00:49 +0200 From: Dik.Winter@cwi.nl Message-Id: <9205281300.AA00307.dik@boring.cwi.nl> To: cube-lovers@life.ai.mit.edu Subject: Corrected calculations are now done. 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