Rubik's Cube

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.