A 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

(Turner and Gold 1985, Schönert). Hoey showed using the Pólya-Burnside lemma that there are 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. In 1995, Michael Reid produced the best proven bound of 29 turns (or 42 "quarter-turns"). In 2008, a series of improvements were made by Tomas Rokicki using the computational facilities of the Sony Pictures Imageworks renderfarm for Spiderman 3. As of Aug. 12, 2008, the upper bound is 22 moves. This result required 1.28 million cosets, 25 quadrillion position, and 50 core-years of CPU time. No 21-move positions were found in this search (Rokicki 2008).

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.

Helm, G. "Rubik's Cube." http://webplaza.pt.lu/geohelm/myweb/cubeold.htm.

Hoey, D. "The Real Size of Cube Space." http://www.math.rwth-aachen.de/~Martin.Schoenert/Cube-Lovers/Dan_Hoey__The_real_size_of_cube_space.html.

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.

Hofstadter, D. R. Ch. 14 in Metamagical Themas: Questing of Mind and Pattern. New York: BasicBooks, 1985.

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

Longridge, M. "Domain of the Cube." http://web.idirect.com/~cubeman/.

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

Rokicki, T. "Twenty-Five Moves Suffice for Rubik's Cube." 24 Mar 2008. http://arxiv.org/abs/0803.3435v1.

Rokicki, T. "Twenty-Two Moves Suffice." 12 Aug 2008. http://cubezzz.homelinux.org/drupal/?q=node/view/121.

Scherphuis, J. "Jaap's Puzzle Page: Rubik's Cube ." http://www.geocities.com/jaapsch/puzzles/cube3.htm.

Schoenert, M. "Cube Lovers: Index by Date." http://www.math.rwth-aachen.de/~Martin.Schoenert/Cube-Lovers/.

Schönert, M. "Analyzing Rubik's Cube with GAP." http://www-groups.dcs.st-and.ac.uk/~gap/Intro/rubik.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.

CITE THIS AS:

Weisstein, Eric W. "Rubik's Cube." From MathWorld--A Wolfram Web Resource. http://mathworld.wolfram.com/RubiksCube.html