From: tordro@ifi.uio.no (Tord Kallqvist Romstad)
Newsgroups: sci.math
Subject: Re: Rubik's Cube
Date: 3 Sep 1996 13:13:08 +0200

David Franklin (kaoskat@dircon.co.uk) wrote:
: Tord Kallqvist Romstad (tordro@ifi.uio.no) wrote:
: : You can find several algorithms on the Web. Just search for the name "Rubik",
: : and you will find a lot of information. It is a lot more fun, however,
: : to develop your own solution. Even when you have solved the cube, it can
: : still give you a lot of fun. Your first algorithm will probably be
: : terribly inefficent. My first cube solving algorithm requiered about
: : 800 moves to execute! After a lot of "optimizing", I can now solve the
: : cube in ~100 moves (some people do much better than that). "God's algorithm",
: : the algorithm that restores the cube in the least number of moves from any
: : position, is still (I believe, I haven't followed the development the last
: : few years) unknown. But there are algorithms which solve the cube in as 
: : little as 20-25 moves! These algorithms (which do not belong to any of the
: : categories described above) are very complex and not well suited for carrying
: : out by hand. 

: I think the best known algorithm takes 50 moves; it went down from 52 a few
: years ago. "God's Algorithm" is s'posed to be aroound 18-21 IIRC.

The 50 moves record (the algorithm was invented by Morwen Thistlethwaite)
has been improved considerably. Hans Kloosterman found a few improvements
in Thistlethwaite's algorithm, his algorithm is proved to solve any position
in at most 42 moves. Since then, lots of additional improvements have been
made. There are computer programs that have solved all configurations
fed to them in 20 moves or less! However, nobody have proved that this is
the theoretical upper limit of the algorithm. It seems that we are pretty 
close to God's algorithm!

I found this information at
http://admin.dis.on.ca:80/~cubeman/

Tord