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