Games - Optimal solutions for Rubik's Cube

Home > Listing Index > Games > Optimal solutions for Rubik's Cube

	Games - Optimal solutions for Rubik's Cube

There are many algorithms to solve scrambled Rubik's Cubes. One such method is described in Wikibooks's article How to solve the Rubik's Cube. This algorithm has the advantage of being simple enough to be memorizable by humans, however it will usually not give an optimal solution for the Rubik's Cube which only uses a minimum possible number of moves.

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 the 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 26 quarter turns, and there is an algorithm that can always solve in 42 quarter turns.

Lower bounds

It can be proven by counting arguments there exist positions that need 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: 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 . Later a different position was found that needs 26 quarter turns for a solution, see .

There are currently no positions known for which more than 20 face turns or 26 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.

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

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 spaces G\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 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.

[ Visit the complete Wikipedia entry for Optimal solutions for Rubik's Cube ]

Searches on eBay

optimal solutions for rubik's cube