From dik@cwi.nl Sun May 24 07:31:21 1992
Return-Path:
Received: from charon.cwi.nl by life.ai.mit.edu (4.1/AI-4.10) id AA05498; Sun, 24 May 92 07:31:21 EDT
Received: from boring.cwi.nl by charon.cwi.nl with SMTP
id AA18991 (5.65b/2.10/CWI-Amsterdam); Sun, 24 May 1992 13:31:14 +0200
Received: by boring.cwi.nl
id AA07227 (5.65b/2.10/CWI-Amsterdam); Sun, 24 May 1992 13:31:13 +0200
Date: Sun, 24 May 1992 13:31:13 +0200
From: Dik.Winter@cwi.nl
Message-Id: <9205241131.AA07227.dik@boring.cwi.nl>
To: anneke@fwi.uva.nl, cube-lovers@life.ai.mit.edu
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
memory.
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.
dik
--
% These processors would have been idle most of the time otherwise!
--
dik t. winter, cwi, kruislaan 413, 1098 sj amsterdam, nederland
dik@cwi.nl