Lower & upper bounds.

Lower & upper bounds.


Lower bound.

One can easily come up with a lower bound, like 0, or 2. But its getting interesting when the lower bound grows. All you need is a position that is known to be 'difficult', ie. far from the origin, ie. needs a lot of move to solve.

Superflip.

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: 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. The superflip is a position where all the cubies are in the correct position, the corners are oriented correctly, but the edges are all flipped, hence 'superflip'. In 1992, a solution for the superflip with 20 face turns was found by Dik T. Winter, of which the minimality was shown in 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. Picture of the superflip position

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 Thistlethwaite; details of Thistlethwaite's Algorithm were published in Scientific American in 1981 by Douglas 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:

* G0 = < L,R,F,B,U,D>

* G1 = < L,R,F,B,U2,D2 >

* G2 = < L,R,F2,B2,U2,D2 >

* G3 = < L2,R2,F2,B2,U2,D2 >

* G4 = {I}

Next he prepared tables for each of the right coset spaces G[i+1]\Gi. 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 G0. Next he found this element in the right coset space G1\G0. He applied the corresponding process to the cube. This took it to a cube in G1. Next he looked up a process that takes the cube to G2, next to G3 and finally to G4.

Although the whole cube group G0 is very large (~4.3.10^19), the right coset spaces G1\G0, G2\G1, G3\G2 and G3 are much smaller. The coset space G2\G1 is the largest and contains only 1.082.565 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 proces also has a name: 'baby step, big step', because in stead of concentrating on finding the greatest distance (big step), you can concentrate on bringing cubes from one coset to the other (baby step).

Later, many improvements have been made on Thistlethwaite's algorithm. Although his original idea has stand the test of time; his idea(s) is(are) used in almost all improvements on the upper bounds.