# Optimal solutions for the Rubik's Cube

Optimal solutions for the Rubik's Cube are solutions that are the shortest in some sense. There are two common ways to measure the length of a solution. The first is to count the number of quarter turns. The second and more popular is to count the number of outer-layer twists, called "face turns". A move to turn an outer layer two quarter (90°) turns in the same direction would be counted as two moves in the quarter turn metric (QTM), but as one turn in the face metric (FTM, or HTM "Half Turn Metric"). It means that the length of an optimal solution in HTM ≤ the length of an optimal solution in QTM.
The maximal number of face turns needed to solve any instance of the Rubik's Cube is 20, and the maximal number of quarter turns is 26. These numbers are also the diameters of the corresponding Cayley graphs of the Rubik's Cube group. In STM (slice turn metric) the minimal number of turns is unknown, lower bound being 18 and upper bound being 20.
A randomly scrambled Rubik's Cube will most likely be optimally solvable in 18 moves (~ 67.0%), 17 moves (~ 26.7%), 19 moves (~ 3.4%), 16 moves (~ 2.6%) or 15 moves (~ 0.2%) in HTM. By the same token, it is estimated that there is only 1 configuration which needs 20 moves to be solved optimally in almost 90×10$^9$, or 90 billion, random scrambles. The exact number of configurations requiring 20 optimal moves to solve the cube is still unknown.

## Move notation

To denote a sequence of moves on the 3×3×3 Rubik's Cube, this article uses "Singmaster notation", which was developed by David Singmaster.
The following are standard moves, which do not move centre cubies of any face to another location:
The letters L, R, F, B, U, and D indicate a clockwise quarter turn of the left, right, front, back, up, and down face respectively. A half turn (i.e. 2 quarter turns in the same direction) are indicated by appending a 2. A counterclockwise turn is indicated by appending a prime symbol ( ' ).
Computer solvers can find either optimal or non-optimal solution in a given turn metric. To distinguish between these states, an asterisk symbol ( * ) is being used. For example, a solution followed by a (18f) means that an 18-move long solution in the face-turn metric was found but that specific solution was not proved to be optimal. On the contrary, a solution followed by a (18f*) means that an 18-move long solution in the face-turn metric was found and that specific solution was proved to be optimal.

## Lower bounds

It can be proven by counting arguments that there exist positions needing at least 18 moves to solve. To show this, first count the number of cube positions that exist in total, then count the number of positions achievable using at most 17 moves starting from a solved cube. It turns out that the latter number is smaller.
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 difficult. A Rubik's Cube is in the superflip pattern when each corner piece is in the correct position, but each edge piece is incorrectly oriented. In 1992, a solution for the superflip with 20 face turns was found by Dik T. Winter, of which the minimality was shown in 1995 by Michael Reid, providing a new lower bound for the diameter of the cube group. Also in 1995, a solution for superflip in 24 quarter turns was found by Michael Reid, with its minimality proven by Jerry Bryan. In 1998, a new position requiring more than 24 quarter turns to solve was found. The position, which was called a 'superflip composed with four spot' needs 26 quarter turns.

## Upper bounds

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.
Perhaps the first concrete value for an upper bound was the 277 moves mentioned by David Singmaster in early 1979. He simply counted the maximum number of moves required by his cube-solving algorithm. Later, Singmaster reported that Elwyn Berlekamp, John Conway, and Richard K. Guy had come up with a different algorithm that took at most 160 moves. Soon after, Conway's Cambridge Cubists reported that the cube could be restored in at most 94 moves.
Five computer algorithms (four of which can find an optimal Rubik's Cube solution in the half-turn metric) are briefly described below. An animated example solve has been made for each of them. The scrambling move sequence used in all example solves is: U2 B2 R' F2 R' U2 L2 B2 R' B2 R2 U2 B2 U' L R2 U L F D2 R' F'. Use the buttons at the top right to navigate through the solves, then use the button bar at the bottom to play the solving sequence. Example solves.

### Thistlethwaite's algorithm

Thistlethwaite's four-phase algorithm is not designed to search for an optimal solution, its average move count being about 31 moves. Nevertheless, it is an interesting solving method from a theoretical standpoint.
The breakthrough in determining an upper bound, known as "descent through nested sub-groups" was found by Morwen Thistlethwaite; details of Thistlethwaite's algorithm were published in Scientific American in 1981 by Douglas Hofstadter. The approaches to the cube that led 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 that could be executed. In particular he divided the cube group into the following chain of subgroups:
    $G_{0}=\langle U,D,L,R,F,B\rangle$
    $G_{1}=\langle U,D,L,R,F^{2},B^{2}\rangle$
    $G_{2}=\langle U,D,L^{2},R^{2},F^{2},B^{2}\rangle$
    $G_{3}=\langle U^{2},D^{2},L^{2},R^{2},F^{2},B^{2}\rangle$
    $G_{4}=\{1\}$
Next he prepared tables for each of the right coset spaces $G_{i+1}\setminus G_{i}$. 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 $G_{0}$. Next he found this element in the right coset space $G_{1}\setminus G_{0}$. 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 right coset spaces $G_{1}\setminus G_{0},G_{2}\setminus G_{1},G_{3}\setminus G_{2}$ and $G_{3}$ are much smaller. The coset space $G_{2}\setminus G_{1}$ 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.
Initially, Thistlethwaite showed that any configuration could be solved in at most 85 moves using a totally different method. In January 1980 he improved his strategy to yield a maximum of 80 moves. Later that same year, he reduced the number to 63 using a new approach, and then again to 52 using an entirely different approach which is now known as Thistlethwaite's algorithm. By exhaustively searching the coset spaces it was later found that the worst possible number of moves for each stage was 7, 10, 13, and 15 giving a total of 45 moves at most. There have been implementations of Thistlewaite's algorithm in various computer languages.

### 4-list algorithm

The main idea behind the 4-list algorithm (sometimes denoted as Shamir's algorithm) is a bidirectional search, also known as a meet-in-the-middle approach. A group of researchers - Adi Shamir, Amos Fiat, Shahar Mozes, Ilan Shimshoni and Gábor Tardos - demonstrated how to apply the algorithm to the Rubik's Cube in 1989, based on earlier work by Richard Schroeppel and Adi Shamir from January 1980 (which was published in 1981).
The 4-list algorithm is not designed to search for an optimal solution as quickly as possible. Its purpose is to find a solution being at most 20 moves long, but without any guarantee that the solution found is optimal. If the algorithm is not terminated upon finding the first solution, it can find all solutions including optimal ones. However, the first report of optimal solutions for randomly scrambled cubes came from Richard E. Korf in 1997, using his own algorithm. The search time required for the 4-list algorithm to find an optimal solution is considerably longer compared to Kociemba's or Feather's algorithm.
Bidirectional search works by searching forward from the scrambled state, and backward from the solved state simultaneously, until a common state is reached from both directions. The solution is then found by combining the forward search path with the inverse of the backward search path.
To find a solution using the 4-list algorithm, a list of all 621,649 permutations that reach depths 0-5 is first stored in RAM. By cleverly multiplying all possible pairs of elements from that list and sorting the resulting products, all permutations that reach depths 0-10 are then generated in lexicographical order from both scrambled and solved states, ultimately leading to a match being found at their intersection. As a consequence of the lexicographic ordering, it is possible to eliminate duplicate permutations and to count the number of unique permutations without storing any of the created products in RAM.

### Kociemba's algorithm

Thistlethwaite's algorithm was improved by Herbert Kociemba in 1992. He reduced the number of intermediate groups to only two:
* $G_{0}=\langle U,D,L,R,F,B\rangle$
* $G_{1}=\langle U,D,L^{2},R^{2},F^{2},B^{2}\rangle$
* $G_{2}=\{1\}$
Kociemba's two-phase algorithm is not designed to search for an optimal solution, its purpose is to quickly find a reasonably short suboptimal solution. A randomly scrambled cube would be typically solved in a fraction of a second in 20 moves or less, but without any guarantee that the solution found is optimal. While it is technically possible to search for an optimal solution using Kociemba's algorithm by reducing a two-phase solver to only a one-phase solver (only phase 1 would be used until the cube is completely solved, no phase 2 operation being done at all), more hardware utilization would be necessary in that case because a fast optimal solver requires significantly more computing resources than an equally fast suboptimal solver.
As with Thistlethwaite's algorithm, he would search through the right coset space $G_{1}\setminus G_{0}$ to take the cube to group $G_{1}$. Next he searched the optimal solution for group $G_{1}$. The searches in $G_{1}\setminus G_{0}$ and $G_{1}$ were both done with a method equivalent to iterative deepening A* (IDA*). The search in $G_{1}\setminus G_{0}$ needs at most 12 moves and the search in $G_{1}$ at most 18 moves, as Michael Reid showed in 1995. By also generating suboptimal solutions that take the cube to group $G_{1}$ and looking for short solutions in $G_{1}$, much shorter overall solutions are usually obtained.
In 1995 Michael Reid proved 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.
At first glance, this algorithm appears to be practically inefficient: if $G_{0}$ contains 18 possible moves (each move, its prime, and its 180-degree rotation), that leaves $18^{12}$ (over 1 quadrillion) cube states to be searched. Even with a heuristic-based computer algorithm like IDA*, which may narrow it down considerably, searching through that many states is likely not practical. To solve this problem, Kociemba devised a lookup table that provides an exact heuristic for $G_{0}$. When the exact number of moves needed to reach $G_{1}$ is available, the search for suboptimal solutions becomes virtually instantaneous (note that the search for optimal solution takes much longer time): one need only generate 18 cube states for each of the 12 moves and choose the one with the lowest heuristic each time. This allows the second heuristic, that for $G_{1}$, to be less precise and still allow for a solution to be computed in reasonable time on a modern computer.

### Korf's algorithm

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 E. Korf wrote the first program to solve randomly scrambled cubes optimally. 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:
* 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.
Clearly the number of moves required to solve any of these subproblems is a lower bound for the number of moves needed 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 lower bounds to still be optimal it can be eliminated from the list.
Although this algorithm will always find optimal solution, its search time is considerably longer in comparison with Kociemba's or Feather's algorithm.

### Feather's algorithm

In 2015, Michael Feather introduced a unique two-phase algorithm on his website. It is capable of generating both suboptimal and optimal solutions in reasonable time on a modern device. Unlike Thistlethwaite's or Kociemba's algorithm, Feather's algorithm is not heavily based on the mathematical field of group theory.
The Rubik's Cube can be simplified by using only 3 colors instead of usual 6 colors. Generally, opposite faces would share the same color. On a 6-color cube, a solved 3-color cube would be represented by a state in which only opposite colors appear on opposite faces.
In a nutshell, Feather's algorithm goes like this: any 3-color solutions that arise from the nodes being generated are then looked up in the array containing distances from intermediate 3-color solutions to the final 6-color solution (a total of 3,981,312 configurations), and if it is 8 moves or less (of which there are 117,265 configurations) then a solution is generated. One can think of it as a brute-force search enhanced by using distance arrays to prune the search tree where possible, and also reducing the size of the distance arrays effectively by using cube symmetry.
When searching for an optimal solution, Feather's algorithm is finding suboptimal solutions on the way. This is an advantage because in many cases it does not have to search the depth of the optimal solution length because it has already found a suboptimal solution at a lower depth that is equal to the optimal solution length, hence it only has to complete search depth N−1 to prove that solution length N is optimal.
Feather's algorithm was implemented in the first online optimal Rubik's Cube solver, more specifically in the first client-side processing (JavaScript) solver with a graphical user interface running in a web browser and being able to generate optimal solutions in a timely manner. That includes computing 19-move long optimal solutions as they will occur roughly in a 3.4% of all cases in a batch of randomly scrambled cubes. The solver has multiple options for different size distance arrays to maximize use of available RAM, and it also uses all available processors to get the best performance from a wide variety of platforms.

## Finding God's number

Two terms - God's number and God's algorithm - are closely related to the optimal solution for the Rubik's Cube. God's number is referring to the fewest number of moves required to solve a scrambled cube in a given turn metric. God's algorithm is referring to the shortest move sequence required to solve a scrambled cube in a given turn metric. For instance, God's number for a scrambling move sequence given in the Upper bounds section above is 18 in FTM, and each of four example solves from that section being 18 moves long in FTM is God's algorithm for a such specifically scrambled cube.
In 2006, Silviu Radu proved that every position can be solved in at most 27 face turns or 35 quarter turns. Daniel Kunkle and Gene Cooperman in 2007 used a supercomputer to show that all unsolved cubes can be solved in no more than 26 moves (in face-turn metric). Instead of attempting to solve each of the billions of variations explicitly, the computer was programmed to bring the cube to one of 15,752 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.
Tomas Rokicki reported in a 2008 computational proof that all unsolved cubes could be solved in 25 moves or fewer. This was later reduced to 23 moves. In August 2008, Rokicki announced that he had a proof for 22 moves.
Finally, in 2010, Tomas Rokicki, Herbert Kociemba, Morley Davidson, and John Dethridge gave the final computer-assisted proof that all cube positions could be solved with a maximum of 20 face turns. In 2009, Tomas Rokicki proved that 29 moves in the quarter-turn metric is enough to solve any scrambled cube. And in 2014, Tomas Rokicki and Morley Davidson proved that the maximum number of quarter-turns needed to solve the cube is 26.
The face-turn and quarter-turn metrics differ in the nature of their antipodes. An antipode is a scrambled cube that is maximally far from solved, one that requires the maximum number of moves to solve. In the half-turn metric with a maximum number of 20, there are hundreds of millions of such positions. In the quarter-turn metric, only a single position (and its two rotations) is known that requires the maximum of 26 moves. Despite significant effort, no additional quarter-turn distance-26 positions have been found. Even at distance 25, only two positions (and their rotations) are known to exist. At distance 24, perhaps 150,000 positions exist.