Optimal solutions for the Rubik's Cube

[4] By the same token, it is estimated that there is only 1 configuration which needs 20 moves to be solved optimally in almost 90×109, or 90 billion, random scrambles.

The exact number of configurations requiring 20 optimal moves to solve the cube is still unknown.

Computer solvers can find either optimal or non-optimal solution in a given turn metric.

[6] 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.

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.

[8][9] 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.

[8][11] Four computer algorithms (three of which can find an optimal Rubik's Cube solution in the half-turn metric) are briefly described below.

The approaches to the cube that led to algorithms with very few moves are based on group theory and on extensive computer searches.

In particular he divided the cube group into the following chain of subgroups: Next he prepared tables for each of the right coset spaces

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.

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.

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

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.

In 1997 Richard Korf wrote the first program to solve randomly scrambled cubes optimally.

The method he used is called IDA* and is described in his paper "Finding Optimal Solutions to Rubik's Cube Using Pattern Databases".

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.

[16] 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).

[17][18] Tomas Rokicki reported in a 2008 computational proof that all unsolved cubes could be solved in 25 moves or fewer.

[2] In 2009, Tomas Rokicki proved that 29 moves in the quarter-turn metric is enough to solve any scrambled cube.

[22] And in 2014, Tomas Rokicki and Morley Davidson proved that the maximum number of quarter-turns needed to solve the cube is 26.

In the quarter-turn metric, only a single position (and its two rotations) is known that requires the maximum of 26 moves.

It is capable of generating both suboptimal and optimal solutions in reasonable time on a modern device.

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.