From BRYAN@wvnvm.wvnet.edu Tue Oct 17 14:20:20 1995 Return-Path: Received: from WVNVM.WVNET.EDU by life.ai.mit.edu (4.1/AI-4.10) for /com/archive/cube-lovers id AA00357; Tue, 17 Oct 95 14:20:20 EDT Received: from WVNVM.WVNET.EDU by WVNVM.WVNET.EDU (IBM VM SMTP V2R3) with BSMTP id 4701; Tue, 17 Oct 95 14:19:53 EDT Received: from WVNVM.WVNET.EDU (NJE origin BRYAN@WVNVM) by WVNVM.WVNET.EDU (LMail V1.2a/1.8a) with BSMTP id 3051; Tue, 17 Oct 1995 14:19:53 -0400 Message-Id: Date: Tue, 17 Oct 1995 14:19:52 -0400 (EDT) From: "Jerry Bryan" To: Subject: Re: I am in search of Thistlewaite's algorithm In-Reply-To: Message of 10/12/95 at 14:45:45 from preux@lil.univ-littoral.fr On 10/12/95 at 14:45:45 preux@lil.univ-littoral.fr said: >As long as I am a new comer to this mailing list, I will briefly >introduce myself. As a computer science researcher, I am working on >evolutionary algorithms trying to assess their ability to solve >combinatorial optimization problems. One of my old dream has been to >solve the Rubik's cube (for the moment, the very basic 3x3x3 version) >with this kind of algorithms. I have heard about the Thistlethwaite's >algorithm which is able to solve the problem in less than 50 or so >moves. I have also heard about a publication of D. Singmaster that, among >other things, describes this algorithm. Thus, I am looking for >information about this algorithm: how does it work precisely? I wonder >whether this algorithm, either a description or an implementation of >it, is available somewhere on the net. I would also be interested in >having a copy of D. Singmaster's report (either via ftp or paper). I don't know if you received any private replies or not, but I will take a crack at this one. There are two places I have personally read about Thistlethwaite's algorithm. One is Douglas Hofstadter's article in Scientific American in March of 1981. The article is reprinted in Hofstadter's "Metamagical Themas". The other is Frey and Singmaster's "Handbook of Cubik Math". There are probably other sources as well, but some of them (e.g., Singmaster's Cubik Circulars) may be hard to come by at your local library. Any "by hand" solution to the Cube generally involves something like "corners first, then edges" (or vice versa), or "top layer, then middle layer, and finally the bottom layer", or (usually) some combination or variation of these themes. Any such theme has states where it is visually obvious that the cube is becoming more and more solved. These plateau states generally have the attribute that they define a subgroup of G. For example, the set of states where the top layer is solved is a subgroup of G. The subgroups defined by the plateau states form a nested sequence of subgroups as the Cube becomes more and more solved. However, progress is not monotonic. You almost always have to give up some of your progress temporarily on the way to the next plateau. Thistlethwaite's algorithm reverses the role of the plateau states and the subgroups. Instead of plateau states defining nested subgroups, he has nested subgroups defining plateau states. In fact, his nested subgroups are arranged in such a way that once a particular subgroup is achieved, there is no loss of progress on your way to the next subgroup. Also, the plateau states achieved by reaching the next subgroup are generally not visually obvious, and indeed it is not visually obvious that any progress at all is being made until the cube is almost solved. The nested subgroups given by Frey and Singmaster are as follows. I believe that other nested subgroups have been used as well. H0==G H1= H2= H3= H4= I do not recall seeing any practitioners of Thistlethwaite's algorithm posting to Cube-Lovers. However, there are several practitioner's of an algorithm called Kociemba's algorithm who contribute to Cube-Lovers. Kociemba's algorithm is a close cousin to Thistlethwaite's, but does not depend on pre-searching as does Thistlethwaite's. Also, I believe that the best Kociemba programs now utilize only two nested subgroups, and are able to achieve results far better than those achieved by Thistlethwaite. As I understand it, Kociemba's algorithm differs from Thistlethwaite's in two primary respects. Kociemba uses searching, and Thistlethwaite uses tables (what I called "pre-searching" in the previous paragraph). Also, Thistlethwaite simply hooks the nested subgroups together and stops when they are hooked, whereas Kociemba continues searching to see if improvements are possible by merging the nested subgroups at their boundaries. = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = Robert G. Bryan (Jerry Bryan) (304) 293-5192 Associate Director, WVNET (304) 293-5540 fax 837 Chestnut Ridge Road BRYAN@WVNVM Morgantown, WV 26505 BRYAN@WVNVM.WVNET.EDU