From dik@cwi.nl Mon Jan 9 17:25:44 1995 Return-Path: Received: from hera.cwi.nl by life.ai.mit.edu (4.1/AI-4.10) for /com/archive/cube-lovers id AA12462; Mon, 9 Jan 95 17:25:44 EST Received: from boring.cwi.nl by hera.cwi.nl with SMTP id ; Mon, 9 Jan 1995 23:25:25 +0100 Received: by boring.cwi.nl id ; Mon, 9 Jan 1995 23:24:17 +0100 Date: Mon, 9 Jan 1995 23:24:17 +0100 From: Dik.Winter@cwi.nl Message-Id: <9501092224.AA05290=dik@boring.cwi.nl> To: BRYAN@wvnvm.wvnet.edu, Cube-Lovers@ai.mit.edu Subject: Re: kociemba's algorithm for quarter turns > I read the articles in the archives about Kociemba's algorithm about > a year ago, without (I confess) fully understanding them. In particular, > I do not fully understand what differentiates Kociemba's algorithm from > Thistlethwaite's algorithm, other than it uses a different arrangement > of nested subgroups. The basis is similar (although Kociemba's algorithm uses searching to get solutions while Thistlethwaite's uses tables and directly arrives at solutions). The main difference is that once a solution is found Thistlethwaite's algorithm stops. Kociemba's algorithm continues finding newer solutions (even longer than the original solution) to phase 1 and trying to fit them with a solution for phase 2 such that the total solution is shorter. This proves to be very effective. Of course this is easier to do with a 2 phase algorithm than with a 4 phase algorithm. > But in the meantime, I wonder if you could verify that Kociemba's > algorithm does not guarantee to find a minimal process? In particular, > is it the case that 26q is a minimal superflip, or is it only an > upper bound? Given time Kociemba's algorithm will find a minimal solution. I confess that my implementations does not if the configuration can be solved through phase 2 only, but the cube can be rotated to avoid that. The reason is that ultimately Kociemba's algorithm will find longer part solutions of phase 1 and ultimately stumble on a complete solution in phase 1 which will be minimal because of the breadth first search. But it can take long. Getting a minimal solution if the length is 16 or less appears to be doable. If the length is 19 or more it takes an awfully long time. What I have found until now is: 1. There are no configurations known that require 21 turns or more, and I checked an awfully large number. 2. There are known configurations that require 18 turns. The middle part is a grey area.