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