[next] [prev] [up] Date: Tue, 12 May 92 23:46:11 +0200
[next] [prev] [up] From: Dik T. Winter <Dik.Winter@cwi.nl >
~~~ [prev] [up] Subject: Re: Diameter of the 2^3 cube and the 3^3 corners

> I sent the results of a quarter-turn analysis of these puzzles to
> Cube-Lovers in several messages during August, 1984.
I must have somewhere a printed stack of cube-lovers mailings, but I never
came around to read them all. Also, my reference to Singmaster was his
notes. The latest page of the latest printing states that the 2x2x2 case
was still unsolved, I never have seen his additional notes.

 >                                                       I counted both
 > positions and local maxima at every distance up to the diameter of 14
 > quarter-turns.
After Mike Reid's question I modified my program to do the counting on the
corners of the 3^3.  The biggest change was that it is now able to handle
that case in memory on this 32 MByte machine.  I did not count local maxima
(although that could be done).  The quarter turn case is identical to Dan
Hoey's results.  If we count half turns as a single move I get the following
         1 with  0 moves
        18 with  1 moves
       243 with  2 moves
      2874 with  3 moves
     28000 with  4 moves
    205416 with  5 moves
   1168516 with  6 moves
   5402628 with  7 moves
  20776176 with  8 moves
  45391616 with  9 moves
  15139616 with 10 moves
     64736 with 11 moves

> The first column agrees with Dik Winter's findings. As Michael Reid
> surmised, the diameters of the two groups are the same.
Also here the diameter is the same.

> My hazy recollection is that the 2^3 program ran for a few minutes on
> a Vax 750, while the corners program took a couple of hours.
My calculation took slightly less than half an hour. The differences in
timings we see are (I think) mostly due to memory constraints on older
machines. So we see a difference between Memory bound and I/O bound.
I could go to disk for storage of (intermediate) results, but even than the
edges can not be handled. (980*10^9 configurations so my program would
require 245 GBytes of storage. I think methods can be found to reduce this by
a factor of 30-40, but it is still much too large to handle, and in that case
you probably get the diameter only.)

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

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