How to Solve a Rubik's Cube Easy

Good video on learning how to solve a rubik’s cube with one hand.

The first upper bounds were based on the ‘human’ algorithms. By combining the worst-case scenarios for each part of these algorithms, the typical upper bound was found to be around 100. The breakthrough was found by Morwen B. Thistlethwaite; details were published in Scientific American in 1981 by Douglas R. Hofstadter. The approaches to the cube that lead to algorithms with very few moves are based on group theory and on extensive computer searches.

Thistlethwaite’s idea was to divide the problem into subproblems. Where algorithms up to that point divided the problem by looking at the parts of the cube that should remain fixed, he divided it by restricting the type of moves you could execute. In particular he divided the cube group into the following chain of subgroups:

* G0 = L,R,F,B,U,D
* G1 = L,R,F,B,U2,D2
* G2 = L,R,F2,B2,U2,D2
* G3 = L2,R2,F2,B2,U2,D2
* G4 = {I}

Next he prepared tables for each of the right coset spaces G[i+1]\Gi. For each element he found a sequence of moves that took it to the next smaller group.

After these preparations he worked as follows. A random cube is in the general cube group G0. Next he found this element in the right coset space G1\G0. He applied the corresponding process to the cube. This took it to a cube in G1. Next he looked up a process that takes the cube to G2, next to G3 and finally to G4.

Although the whole cube group G0 is very large (~4.3×1019), the right coset spaces G1\G0, G2\G1, G3\G2 and G3 are much smaller. The coset space G2\G1 is the largest and contains only 1082565 elements. The number of moves required by this algorithm is the sum of the largest process in each step. In the original version this was 52.

This algorithm was improved by Herbert Kociemba in 1992. He reduced the number of intermediate groups to only two:

* G0 = L,R,F,B,U,D
* G1 = L,R,F2,B2,U2,D2
* G2 = {I}.

As with Thistlethwaite’s algorithm, he would search through the right coset space G1\G0 to take the cube to group G1. Next he searched the optimal solution for group G1. The searches in G1\G0 and G1 were both done with a method equivalent to IDA*. The search in G1\G0 needs at most 12 moves and the search in G1 at most 18 moves, as Michael Reid showed in 1995. By generating also suboptimal solutions that take the cube to group G1 and looking for short solutions in G1, you usually get much shorter overall solutions. Using this algorithm solutions are typically found of less than 21 moves, though there is no proof that it will always do so.

Next in 1995 it was proven by Michael Reid that using these two groups every position can be solved in at most 29 face turns, or in 42 quarter turns. This result was improved by Silviu Radu in 2005 to 40.

Using these group solutions combined with computer searches will generally quickly give very short solutions. But these solutions do not always come with a guarantee of their minimality. To search specifically for minimal solutions a new approach was needed.

In 1997 Richard Korf announced an algorithm with which he had optimally solved random instances of the cube. Of the ten random cubes he did, none required more than 18 face turns. The method he used is called IDA* and is described in his paper “Finding Optimal Solutions to Rubik’s Cube Using Pattern Databases.” Korf describes this method as follows

IDA* is a depth-first search that looks for increasingly longer solutions in a series of iterations, using a lower-bound heuristic to prune branches once a lower bound on their length exceeds the current iterations bound.

It works roughly as follows. First he identified a number of subproblems that are small enough to be solved optimally. He used:

1. The cube restricted to only the corners, not looking at the edges
2. The cube restricted to only 6 edges, not looking at the corners nor at the other edges.
3. The cube restricted to the other 6 edges.

Clearly the number of moves required to solve any of these subproblems is a lower bound for the number of moves you will need to solve the entire cube.

Given a random cube C, it is solved as iterative deepening. First all cubes are generated that are the result of applying 1 move to them. That is C * F, C * U, … Next, from this list, all cubes are generated that are the result of applying two moves. Then three moves and so on. If at any point a cube is found that needs too many moves based on the upper bounds to still be optimal it can be eliminated from the list.

Although this algorithm will always find optimal solutions there is no worst case analysis. It is not known how many moves this algorithm might need. An implementation of this algorithm can be found here.

In 2006, Silviu Radu further improved his methods to prove that every position can be solved in at most 27 face turns or 35 quarter turns.

In August 2007, Daniel Kunkle and Gene Cooperman used a supercomputer to show that all unsolved cubes can be solved in no more than 26 moves. Instead of attempting to solve each of the billions of variations explicitly, the computer was programmed to bring the cube to one of 15,000 states, each of which could be solved within a few extra moves. All were proved solvable in 29 moves, with most solvable in 26. Those that could not initially be solved in 26 moves were then solved explicitly, and shown that they too could be solved in 26 moves.

- Wikipedia