[next] [prev] [up] Date: Sun, 24 May 92 13:31:13 +0200
[next] [prev] [up] From: Dik T. Winter <Dik.Winter@cwi.nl >
[next] ~~~ [up] Subject: New upper bound on God's algorithm for Rubik's cube
Earlier than expected I have gotten my results.  Using a farm of workstations
I have calculated the distances for all cosets in phase 1 of Kociemba's
algorithm.  As I have conjectured already, the maximal distance is 12.
Together with Kloosterman's result for their third and fourth phase (which
together form Kociemba's second phase) the upperbound on God's algorithm
is now 37.  Below follows the set of distances for the first phase:
  0:          1
  1:          4
  2:         74
  3:       1230
  4:      18056
  5:     245902
  6:    3082221
  7:   34529024
  8:  301243996
  9: 1209021801
 10:  663711855
 11:    5238847
 12:        109
tot: 2217093120

It took quite a bit of computer time. In all 116 processors in 112 different
machines have cooperated, although not all at the same time %. The maximal
amount of concurrent processing was on 100 processors last night. The
distribution was: 69 Sun's (SS 1, SS 1+, SLC, ELC), 40 SGI's, 1 SGI 4D/310VGX,
5 processors of an SGI 260S compute server and the scalar (SPARC) processor
of an FPS 500. I expect it would have taken one or two hours only on a machine
with 1 GByte of memory. Calculations on the second phase are still out of
the question. Distributing the processing would take much more than 9 times
as much. I expect it would take about a day on a machine with 4 GByte of

I conjecture that the maximal distance in phase 2 is at most 16. There is a
lower bound on it of 14. This would make the upperbound for God's algorithm 28.

% These processors would have been idle most of the time otherwise!
dik t. winter, cwi, kruislaan 413, 1098 sj amsterdam, nederland

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