From:

~~~ Subject:

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=<L,R,F,B,U,D>=G H1=<L,R,F,B,U2,D2> H2=<L,R,F2,B2,U2,D2> H3=<L2,R2,F2,B2,U2,D2> H4=<I>

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