Rubik's Cube

The 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 Toys in 1980 and won the German Game of the Year special award for Best Puzzle that year. As of January 2009, 350 million cubes have sold worldwide making it the world's top-selling puzzle game. It is widely considered to be the world's best-selling toy.

In a classic Rubik's Cube, each of the six faces is covered by nine stickers, among six solid colours (traditionally white, red, blue, orange, green, and yellow). A pivot mechanism enables each face to turn independently, thus mixing up the colours. For the puzzle to be solved, each face must be a solid colour. Similar puzzles have now been produced with various numbers of stickers, not all of them by Rubik. The original 3×3×3 version celebrates its thirtieth anniversary in 2010.

There are many algorithms to solve scrambled Rubik's Cubes. The minimum number of face turns needed to solve any instance of the Rubik's cube is 20. This number is also known as the diameter of the Cayley graph of the Rubik's Cube group. An algorithm that solves a cube in the minimum number of moves is known as God's algorithm.

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.

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 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 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, an international Group around Morley Davidson gave the final proof that all cube positions could be solved with a maximum of 20 face turns.