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.