Rubik's Cube
A 
Cube in which the 26 subcubes on the outside are internally hinged in such a way thatrotation (by a quarter turn in either direction or a half turn) is possible in any plane of cubes. Each of the six sidesis painted a distinct color, and the goal of the puzzle is to return the cube to a state in which each side has a singlecolor after it has been randomized by repeated rotations. The Puzzle was invented in the 1970s by the HungarianErno 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). Hoey showed using the Pólya-Burnside Lemma that there are901,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 necessarilyoptimal (i.e., requiring a minimum number of turns). The minimum number of turns required for an arbitrary startingposition is still not known, although it is bounded from above. Michael Reid (1995) produced the best proven bound of 29turns (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 most21 turns. Recently, Richard Korf (1997) has produced a different algorithm which is practical for cubes up to 18 moves awayfrom solved. Out of 10 randomly generated cubes, one was solved in 16 moves, three required 17 moves, and six required 18moves.
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.
- Euler's Conjecture
- Euler's Criterion
- Euler's Displacement Theorem
- Euler's Distribution Theorem
- Euler's Factorization Method
- Euler's Finite Difference Transformation
- Euler's Graeco-Roman Squares Conjecture
- Euler's Homogeneous Function Theorem
- Euler's Hypergeometric Transformations
- Euler's Idoneal Number
- Euler's Machin-Like Formula
- Euler's Pentagonal Number Theorem
- Euler's Phi Function
- Euler's Polygon Division Problem
- Euler's Quadratic Residue Theorem
- Euler Square
- Euler's Rotation Theorem
- Euler's Rule
- Euler's Series Transformation
- Euler's Spiral
- Euler's Sum of Powers Conjecture
- Euler's Theorem
- Euler's Totient Rule
- Euler's Transform
- Euler's Triangle