Date: Sun, 10 May 92 02:43:31 +0200
From: Dik T. Winter <Dik.Winter@cwi.nl
>
~~~
Subject: More on the Cube (2x2x2 in this case).
Singmaster states that the diameter of the group for the 2x2x2 cube is not
known. I do not know whether it has been calculated in the mean time, so
I just did calculate it. The number of elements in the group is
3,674,160. (Fix one corner, the others allow every permutation and one
third of all possible twists.) The diameter is 11 if we do allow half-turns,
it is 14 if we do not allow half-turns. The distribution is:
If we allow half-turns:
1 with 0 moves
9 with 1 moves
54 with 2 moves
321 with 3 moves
1847 with 4 moves
9992 with 5 moves
50136 with 6 moves
227536 with 7 moves
870072 with 8 moves
1887748 with 9 moves
623800 with 10 moves
2644 with 11 moves
If we do not allow half-turns:
1 with 0 moves
6 with 1 moves
27 with 2 moves
120 with 3 moves
534 with 4 moves
2256 with 5 moves
8969 with 6 moves
33058 with 7 moves
114149 with 8 moves
360508 with 9 moves
930588 with 10 moves
1350852 with 11 moves
782536 with 12 moves
90280 with 13 moves
276 with 14 moves
In the first case heuristics give a diameter of at least 9. We see that the
majority of the configuration is within distance 9 from start. So it appears
that heuristics get close to the real value.
We see also that in both cases there is more than one diametrally opposite
configuration. Next I will find out which those are (and if they have
something in common).
BTW, calculation did not take very long, only a few (<3) minutes on an FPS
(i.e. an extremely fast SPARC). But as the calculations are memory bound
rather than compute bound, the speed of the processor is not so very important.