Rubik's Cube

A $3\times 3\times 3$ Cube in which the 26 subcubes on the outside are internally hinged in such a way that rotation (by a quarter turn in either direction or a half turn) is possible in any plane of cubes. Each of the six sides is painted a distinct color, and the goal of the puzzle is to return the cube to a state in which each side has a single color after it has been randomized by repeated rotations. The Puzzle was invented in the 1970s by the Hungarian Erno Rubik and sold millions of copies worldwide over the next decade.

The number of possible positions of Rubik's cube is

$\begin{displaymath} {8!12!3^82^{12}\over 2\cdot 3\cdot 2} = 43{,}252{,}003{,}274{,}489{,}856{,}000 \end{displaymath}$

(Turner and Gold 1985). Hoey showed using the Pólya-Burnside Lemma that there are 901,083,404,981,813,616 positions up to conjugacy by whole-cube symmetries.

Algorithms exist for solving a cube from an arbitrary initial position, but they are not necessarily optimal (i.e., requiring a minimum number of turns). The minimum number of turns required for an arbitrary starting position is still not known, although it is bounded from above. Michael Reid (1995) produced the best proven bound of 29 turns (or 42 ``quarter-turns''). The proof involves large tables of ``subroutines'' generated by computer.

However, Dik Winter has produced a program based on work by Kociemba which has solved each of millions of cubes in at most 21 turns. Recently, Richard Korf (1997) has produced a different algorithm which is practical for cubes up to 18 moves away from solved. Out of 10 randomly generated cubes, one was solved in 16 moves, three required 17 moves, and six required 18 moves.

See also Rubik's Clock

References

Hofstadter, D. R. ``Metamagical Themas: The Magic Cube's Cubies are Twiddled by Cubists and Solved by Cubemeisters.'' Sci. Amer. 244, 20-39, Mar. 1981.

Larson, M. E. ``Rubik's Revenge: The Group Theoretical Solution.'' Amer. Math. Monthly 92, 381-390, 1985.

Miller, D. L. W. ``Solving Rubik's Cube Using the `Bestfast' Search Algorithm and `Profile' Tables.'' http://www.sunyit.edu/~millerd1/RUBIK.HTM.

Schubart, M. ``Rubik's Cube Resource List.'' http://www.best.com/~schubart/rc/resources.html.

Singmaster, D. Notes on Rubik's `Magic Cube.' Hillside, NJ: Enslow Pub., 1981.

Taylor, D. Mastering Rubik's Cube. New York: Holt, Rinehart, and Winston, 1981.

Taylor, D. and Rylands, L. Cube Games: 92 Puzzles & Solutions New York: Holt, Rinehart, and Winston, 1981.

Turner, E. C. and Gold, K. F. ``Rubik's Groups.'' Amer. Math. Monthly 92, 617-629, 1985.