There are many algorithm

Algorithm

In mathematics and computer science, an algorithm is an effective method expressed as a finite list of well-defined instructions for calculating a function. Algorithms are used for calculation, data processing, and automated reasoning...

s to solve scrambled Rubik's Cube

Rubik's Cube

Rubik's Cube is a 3-D mechanical puzzle invented in 1974 by Hungarian sculptor and professor of architecture Ernő Rubik.Originally called the "Magic Cube", the puzzle was licensed by Rubik to be sold by Ideal Toy Corp. in 1980 and won the German Game of the Year special award for Best Puzzle that...

s. The maximum number of face turns needed to solve any instance of the Rubik's cube is 20. This number is also known as the diameter

Distance (graph theory)

In the mathematical field of graph theory, the distance between two vertices in a graph is the number of edges in a shortest path connecting them. This is also known as the geodesic distance...

 of the Cayley graph

Cayley graph

In mathematics, a Cayley graph, also known as a Cayley colour graph, Cayley diagram, group diagram, or colour group is a graph that encodes the abstract structure of a group. Its definition is suggested by Cayley's theorem and uses a specified, usually finite, set of generators for the group...

 of the Rubik's cube group

Rubik's Cube group

The Rubik's Cube group is a mathematical group which corresponds to the set of all cube operations on Rubik's Cube, with function composition as the group operation....

. An algorithm that solves a cube in the minimum number of moves is known as God's algorithm

God's algorithm

God's algorithm is a notion originating in discussions of ways to solve the Rubik's Cube puzzle, but which can also be applied to other combinatorial puzzles and mathematical games...

.

There are two common ways to measure the length of a solution. 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.

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

Constructive proof

In mathematics, a constructive proof is a method of proof that demonstrates the existence of a mathematical object with certain properties by creating or providing a method for creating such an object...

: it does not exhibit a concrete position that needs this many moves. It was conjecture

Conjecture

A conjecture is a proposition that is unproven but is thought to be true and has not been disproven. Karl Popper pioneered the use of the term "conjecture" in scientific philosophy. Conjecture is contrasted by hypothesis , which is a testable statement based on accepted grounds...

d 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 and edge 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.

Thistlethwaite's algorithm

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 Thistlethwaite

Morwen Thistlethwaite

Morwen B. Thistlethwaite is a knot theorist and professor of mathematics for the University of Tennessee in Knoxville. He has made important contributions to both knot theory, and Rubik's cube group theory.-Biography:...

; details of Thistlethwaite's Algorithm were published in Scientific American

Scientific American

Scientific American is a popular science magazine. It is notable for its long history of presenting science monthly to an educated but not necessarily scientific public, through its careful attention to the clarity of its text as well as the quality of its specially commissioned color graphics...

in 1981 by Douglas Hofstadter

Douglas Hofstadter

Douglas Richard Hofstadter is an American academic whose research focuses on consciousness, analogy-making, artistic creation, literary translation, and discovery in mathematics and physics...

. The approaches to the cube that lead to algorithms with very few moves are based on group theory

Group (mathematics)

In mathematics, a group is an algebraic structure consisting of a set together with an operation that combines any two of its elements to form a third element. To qualify as a group, the set and the operation must satisfy a few conditions called group axioms, namely closure, associativity, identity...

 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

Rubik's Cube group

The Rubik's Cube group is a mathematical group which corresponds to the set of all cube operations on Rubik's Cube, with function composition as the group operation....

 into the following chain of subgroups:

• G₀ = <L,R,F,B,U,D>
• G₁ = <L,R,F,B,U2,D2>
• G₂ = <L,R,F2,B2,U2,D2>
• G₃ = <L2,R2,F2,B2,U2,D2>
• G₄ = {I}

Next he prepared tables for each of the right coset

Coset

In mathematics, if G is a group, and H is a subgroup of G, and g is an element of G, thenA coset is a left or right coset of some subgroup in G...

 spaces G_[i+1]\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₀. Next he found this element in the right coset

Coset

In mathematics, if G is a group, and H is a subgroup of G, and g is an element of G, thenA coset is a left or right coset of some subgroup in G...

 space G₁\G₀. He applied the corresponding process to the cube. This took it to a cube in G₁. Next he looked up a process that takes the cube to G₂, next to G₃ and finally to G₄.

Although the whole cube group G₀ is very large (~4.3×10¹⁹), the right coset spaces
G₁\G₀,
G₂\G₁,
G₃\G₂
and G₃ are much smaller.
The coset space G₂\G₁ 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.

Kociemba's Algorithm

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

• G₀ = <L,R,F,B,U,D>
• G₁ = <L,R,F2,B2,U2,D2>
• G₂ = {I}.

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

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.

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 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

Algorithm

In mathematics and computer science, an algorithm is an effective method expressed as a finite list of well-defined instructions for calculating a function. Algorithms are used for calculation, data processing, and automated reasoning...

 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.

Further improvements

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. Daniel Kunkle and Gene Cooperman in 2007 used a supercomputer

Supercomputer

A supercomputer is a computer at the frontline of current processing capacity, particularly speed of calculation.Supercomputers are used for highly calculation-intensive tasks such as problems including quantum physics, weather forecasting, climate research, molecular modeling A supercomputer is a...

 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,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.
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. In 2009, Tomas Rokicki proved that 29 moves in quarter turn metric is enough to solve any scrambled cube. Finally, in 2010, Tomas Rokicki, Herbert Kociemba, Morley Davidson, and John Dethridge gave the final computer-assisted proof

Computer-assisted proof

A computer-assisted proof is a mathematical proof that has been at least partially generated by computer.Most computer-aided proofs to date have been implementations of large proofs-by-exhaustion of a mathematical theorem. The idea is to use a computer program to perform lengthy computations, and...

 that all cube positions could be solved with a maximum of 20 face turns.

External links

• How to solve the Rubik's Cube, a Wikibooks article that describes an algorithm that has the advantage of being simple enough to be memorizable by humans, however it will usually not give an optimal solution which only uses the minimum possible number of moves.
• Herbert Kociemba's Two-Phase-Solver and Optimal Solver for Rubik's Cube
• Ryan Heise's Human version of the Thistlethwaite algorithm
• A New Upper Bound on Rubik's Cube Group, Silviu Radu
• Online Solver using modified Kociemba's Algorithm to balance optimization vs. compute cycles