*Note: Notation from How to solve the Rubik's Cube is used in this article.*

It is not known how many moves is the maximum number required to solve any instance of the Rubik's cube. This number is also known as the diameter of the Cayley graph. An algorithm that solves a cube in the minimum number of moves is known as 'God's algorithm'.

When discussing the length of a solution, there are two common ways to measure this. The first is to count the number of quarter turns. The second is to count the number of face turns. A move like F2 (a half turn of the front face) would be counted as 2 moves in the quarter turn metric and as only 1 turn in the face metric.

A summary of current state of knowledge is as follows: There exist positions that need 20 face turns (superflip). There exists an algorithm that can always solve in 29 face turns. There exist positions that need 24 quarter turns, and there is an algorithm that can always solve in 42 quarter turns.

Table of contents |

2 Upper bounds 3 External links |

This argument was not improved upon for many years. Also, it is not a constructive proof: it does not exhibit a concrete position that needs this many moves. It was conjectured that the so-called superflip would be a position that is very hard. The superflip is a position on the cube where all the cubies are in their correct position, all the corners are correctly oriented but each edge is oriented the wrong way.

One indication that this might be the case is that it is the only element other than the identity that is in the center of the cube group.

In 1992 a solution was found for the superflip which had 20 face turns by Dik T. Winter. In 1995 Michael Reid proved its minimality, thereby giving a new lower bound for the diameter of the cube group.

Also in 1995 a solution in 24 quarter turns was found by Michael Reid, its minimality was proven by Jerry Bryan. See [1].

There are currently no positions known for which more than 20 face turns or 24 quarter turns are needed. There is however no proof that such positions do not exist. In fact they may occur so rarely that a random sampling of cube positions will not find them.

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. Thistlewaite; 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.

Thistlewaite'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:

- G
_{0}= - G
_{1}= - G
_{2}= - G
_{3}= - G
_{4}= {I}

After these preparations he worked as follows.
A random cube is in the general cube group G_{0}.
Next he found this element in the quotient group G_{0}/G_{1}.
He applied the corresponding process to the cube.
This took it to a cube in G_{1}.
Next he looked up a process that takes the cube to G_{2}, next to G_{3} and finally to G_{4}.

Although the whole cube group G_{0} is very large (~4.3×10^{19}),
the groups
G_{0}/G_{1},
G_{1}/G_{2},
G_{2}/G_{3}
and G_{3} are much smaller.
The quotient G_{1}/G_{2} 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:

- G
_{0}= - G
_{1}= - G
_{2}= {I}.

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. Currently this is the best known upper bound.

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 their estimated length exceeds the current iterations bound.

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

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 found at [2].