Progressive Improvements in Solving Algorithms
----------------------------------------------
In the beginning there was Erno Rubik's wooden cube. This first
working model was a wooden 2x2x2 cube held together by elastic
bands. It was shortly after this cube was made that Rubik realized
the solution to the puzzle, that is to get all 6 sides the same colour,
was not trivial but actually quite difficult! Since then millions
of people have been trying to find solutions of their own. Here is
a brief summary of the progressive efforts to reach God's Algorithm
on the standard 3x3x3 cube in rough chronological order (note that here
a move is defined as a turn of a face, also known as the HT metric):
Morwen Thistlethwaite, a pioneer in computer cubing, was initially
the most diligent user of computers to assist in finding an
efficient solution.
One of his early algorithms is as follows...
- Do a 2x2x3 block leaving the F and R faces
- Correctly orient all remaining edges using U or D turns
- Position FU, FL, FD and then put UFL and DFL correctly in place
- Position R edges and R corners in at most 13 and 10 moves
respectively
- Requires 85 moves at most, later improved to 80 moves
Bradley W. (3D) Jackson, complier of "The Cube Dictionary", had a
similar algorithm...
- Do a 2x2x3 block (30 moves)
- Do a remaining face (20 moves)
- Do the last face (20 moves)
- Requires 70 moves at most
Thistlethwaite continued to find better approaches however...
- Orient edges and get them into their slices (18 moves)
- Edges are then placed ( 9 moves)
- Corners are done (36 moves)
- Requires 63 moves at most
Later on Thistlethwaite developed an entirely new approach, the famous
52 move solution which remained the record for some time...
- Work through the following sequence of groups
G0 = < L1, R1, F1, B1, U1, D1 > ( 7 moves)
G1 = < L1, R1, F1, B1, U2, D2 > (13 moves)
G2 = < L1, R1, F2, B2, U2, D2 > (15 moves)
G3 = < L2, R2, F2, B2, U2, D2 > (17 moves)
- Later the final stage was found doable in 15 moves, thus
improving the total to 50 moves
By exhaustively searching the coset spaces it was later found that
the best possible number of moves for each stage was 7, 10, 13, and 15
giving a total of 45 moves at most.
Hans Kloosterman also improved on Thistlethwaite's algorithm, getting
it down 42 moves by several improvements. He verified Morwen's
conjectured values for the first two stages and then combined the last
two stages to get a better method than Morwen's and finally there was
always a way to join the last stage to the previous by the same move,
so this reduced the number by one.
After this several others improved on Thistlethwaite's work in new
ways, beginning with Herbert Kociemba from Darmstad Germany. He used
an Atari ST with 1 megabyte of memory. The improvement was made by
combining phases 1 and 2 to a single phase and phase 3 and 4 also to
a single phase. The major improvement was that the improved system
did not rest when finding an optimal solution for the 1st phase
but also worked with suboptimal solutions.
- Work through the following sequence of groups
G0 = < U1, D1, R1, L1, F1, B1 >
G1 = < U1, D1, R2, L2, F2, B2 >
- Although not proven rigourously, Kociemba has solved all
patterns with his system in 21 moves or less!
Mike Reid has found a 3 stage filtration, using Kociemba's
work as a starting point. The coset sizes were 253440, 15676416,
and 10886400 and were searched exhaustively given a total maximum
of 39 face turns or 56 quarter turns. Some cancellation occurs
between stage 2 & 3.
G0 = < U1, F1, R1, L1, B1, D1> ( 8 moves)
G1 = < U1, R1, F1> (13 moves)
G2 = < U1, R2, F2> (19 moves)
Although God's Algorithm is still unknown for the 3x3x3 cube, several
other puzzles (or subgroups) are now completely solved:
- Pyraminx solvable in 11 moves (not counting the 3 tips)
- 2x2x2 Pocket Cube 11 moves (or 14q turns)
- 3x3x3 Corners only 11 moves (or 14q turns)
- Squares group of 3x3x3 15 moves (using h turns only)
- Rubik's 3x3x2 domino 18 moves (or 19q turns)
- < U , R > group of cube 25 moves (using q turns only)
Dik Winter, Hans Kloosterman and Mike Reid all have improved versions
of Kociemba's program working. The latest versions of the program
have solved all configurations fed to it in 20 moves or less. I'm
not certain what the lower bound is now. I have a program which has
solved all squares group positions in 15 or less, which confirms with
the results from other programs. Mike Reid has also developed a
version which resolves positions minimal in the quarter turn metric.
Possible future projects include finding God's Algorithm for the
Skewb, Square 1, Missing Link. Very little work has been done on
Rubik's Revenge, the 4x4x4 cube. No one has as yet combined the
best cube graphics rendering with the best solving algorithm.