Rubik's cube is 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 Ernő
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 Cauchy-Frobenius Lemma that there are
positions up to conjugacy by whole-cube symmetries.
The group of operations on Rubik's cube is known as Rubik's group, and the Cayley
graph of that group is called Rubik's graph.
The minimum number of turns required to solve the cube from an arbitrary starting
position is equal to the graph diameter of Rubik's
graph, and is sometimes known as God's number.
While algorithms exist for solving a cube from an arbitrary initial position, they
are not necessarily optimal (i.e., requiring a minimum number of turns) and computation
of God's number is very difficult. It had been known
since 1995 that a lower bound on the number of moves for the solution (in the worst
case) was 20, it was not known until demonstrated by Rokicki et al. (2010)
that no configuration requires more than 20 moves, thus establishing that God's number
is 20.
The configurations of a
Rubik's cube reachable using only half twists form a Nauru
graph. Wolfram (2022) analyzed of the Rubik's cube via a multiway
graph, the first few steps of which are illustrated above.