[next] [prev] [up] Date: Sun, 10 May 92 02:43:31 +0200
[next] [prev] [up] From: Dik T. Winter <Dik.Winter@cwi.nl >
[next] ~~~ [up] 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.

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