The Mathematics Behind the Rubik's Cube #PID1.3
The previous post described how humans approach the cube through staged reduction: fix one subgroup of pieces, then the next, until nothing remains. That framing was intuitive but informal. This post makes it precise.
The Rubik’s Cube is a mathematical object with a well-defined algebraic structure, and understanding that structure is what allows computer algorithms to navigate the state space efficiently. Without this foundation, Thistlethwaite’s algorithm reads like a sequence of clever tricks. With it, the algorithm is a direct consequence of the cube’s group-theoretic properties.
The Cube as a Group
A group is a set G equipped with a binary operation satisfying four axioms:
- Closure: for all a, b in G, a * b is in G.
- Associativity: for all a, b, c in G, (a * b) * c = a * (b * c).
- Identity: there exists e in G such that e * a = a * e = a for all a.
- Inverses: for each a in G, there exists a^{-1} in G such that a * a^{-1} = e.
The Rubik’s Cube group G is the set of all reachable cube states, with the group operation being sequential application of moves. This satisfies all four axioms: applying two moves produces another reachable state (closure); sequential application is associative; the solved state is the identity; and every move sequence has an inverse (apply moves in reverse order, each inverted). The group is generated by the six face moves {U, D, F, B, R, L}.
G is non-abelian: the operation is not commutative. R followed by U gives a different result than U followed by R. This is not a quirk of the cube but a consequence of composition of non-commuting permutations, which is the central reason the state space is large and the solving problem is non-trivial. If the group were abelian, the state space would factor into independent cyclic components and the problem would reduce to linear algebra over Z_2 x Z_3.
Counting the 43 Quintillion States
The order |G| = 43,252,003,274,489,856,000 is derived by counting the independent degrees of freedom for each piece type.
Corner pieces. 8 corners can be arranged in 8! = 40,320 ways. Each corner has 3 possible orientations (0, 120, 240 degrees of twist). The orientations are not fully independent: summing all 8 corner orientations modulo 3 always yields 0 for any state reachable by legal moves. This is because each face move applies a specific pattern of orientation changes that sum to zero mod 3. The constraint eliminates one degree of freedom, leaving 3^7 independent orientation states.
Edge pieces. 12 edges can be arranged in 12! ways. Each edge has 2 orientations (correctly oriented or flipped). The same constraint applies: the sum of all 12 edge orientations modulo 2 is invariant under legal moves and equals 0 for the solved state. This leaves 2^{11} independent orientation states.
Parity constraint. The corner permutation and edge permutation are not independent. Each face move is a 4-cycle of corners composed with a 4-cycle of edges. A 4-cycle is an odd permutation (it decomposes into 3 transpositions). So each face move changes the parity of both the corner permutation and the edge permutation simultaneously. The parities are therefore always equal: both even or both odd. States where corner parity is odd and edge parity is even are unreachable by legal moves, halving the total count.
The exact state count:
$$ |G| = \frac{8! \times 3^7 \times 12! \times 2^{11}}{2} = 43{,}252{,}003{,}274{,}489{,}856{,}000 $$Each factor is a direct encoding of a physical constraint imposed by the cube mechanism. For the 2x2x2, there are no edge pieces, and one corner is fixed by convention to eliminate the 24 redundant whole-cube rotations:
$$ |G_{2\times2}| = \frac{8! \times 3^7}{24} = 3{,}674{,}160 $$The factor of 24 accounts for the 24 orientations of the rotation group of the cube, which are all equivalent when no centers are present to define absolute orientation.
Moves as Permutations
Every legal move is a permutation of the 20 movable pieces (8 corners + 12 edges). Consider the move R. In cycle notation on piece positions:
R = (UBR URF DRF DBR)(UR RF DR BR)
The first 4-cycle means: the piece at UBR goes to URF, URF goes to DRF, DRF goes to DBR, DBR goes back to UBR. The second 4-cycle does the same for the four right-face edges. All other pieces are fixed points of this permutation.
Composing two moves means composing two permutations, which is the group operation. The full cube group is isomorphic to a subgroup of S_{48} (all permutations of 48 stickers) or equivalently a subgroup of S_{20} x (Z_3^8 x Z_2^{12}) when positions and orientations are tracked separately.
The cycle type of a permutation determines its order. A k-cycle has order k; a permutation with cycle type (k_1, k_2, …, k_r) has order lcm(k_1, k_2, …, k_r). For the move R, which consists of two 4-cycles, the order is lcm(4, 4) = 4: applying R four times returns the cube to the state before R was applied.
For a composed sequence like (R U), the cycle structure of the composition determines the order. The sequence R U, as a permutation, has order 105. This can be verified by computing the permutation corresponding to R U explicitly and decomposing it into disjoint cycles:
- If the cycle decomposition of (R U) as a permutation on the 48 stickers produces cycles of lengths whose least common multiple is 105, then (R U)^{105} = identity.
That lcm(3, 5, 7) = 105 and the cycles of (R U) happen to have lengths from {3, 5, 7} is a calculable consequence of the group structure, not a coincidence. Order calculations like this are how advanced solvers design efficient commutators.
Commutators and Conjugates
Two operations appear throughout cube solving, usually without being named.
A commutator is [A, B] = A B A^{-1} B^{-1}. If A and B commuted (AB = BA), then [A, B] = identity. Because G is non-abelian, [A, B] is generally not the identity, and it produces a contained transformation: pieces affected by both A and B are moved in a specific cycle, while pieces affected by only one of A or B tend to cancel out.
The sequence R U R’ U’ is [R, U]: a commutator of the right face and the top face move. As a permutation, it is a 3-cycle on three corner pieces. Repeated application or composition with conjugates produces the standard corner placement algorithms.
More precisely: if A affects only the top layer and B affects only the right layer, then the support of [A, B] (the set of non-fixed points) is contained in the intersection of the supports of A and B. This containment is what makes commutators useful: they let solvers affect a small number of pieces while leaving the rest fixed.
A conjugate is X A X^{-1}. If A produces a specific cycle (a_1 a_2 … a_k) on pieces a_1, …, a_k, then X A X^{-1} produces the cycle (X(a_1) X(a_2) … X(a_k)) on the images of those pieces under X. Conjugation relocates algorithms: a sequence that 3-cycles three specific corners can be conjugated with a setup move to 3-cycle any three corners on the cube.
Every serious human solving algorithm is a commutator, a conjugate, or a composition of both. This follows from the group structure: to move a small number of pieces without disturbing others, you need operations whose non-abelian interactions are controlled, and commutators are the natural tool for achieving that.
Subgroups and Cosets
A subgroup H of G is a subset of G that is itself a group under the same operation. Important subgroups of the cube group include:
- The subgroup of all states with correctly oriented edges (H_1). This is the kernel of the edge orientation homomorphism phi: G -> (Z_2)^{11}, the map sending each cube state to its edge orientation vector. H_1 = ker(phi).
- The subgroup of all states with correctly oriented corners (H_2).
- The subgroup of all states reachable using only half-turns {U2, D2, R2, L2, F2, B2}.
The intersection of subgroups is a subgroup. Thistlethwaite’s and Kociemba’s algorithms work by targeting the intersection of carefully chosen subgroups as intermediate states.
A left coset of H in G is a set gH = {g * h : h in H} for some g in G. The cosets of H partition G into equal-sized subsets, each of size |H|. The number of cosets is |G|/|H|, which is the index [G : H]. Reducing the cube from an arbitrary state to a specific coset gH is the essence of each phase in Thistlethwaite’s and Kociemba’s algorithms: Phase 1 in Kociemba maps any state to the identity coset of the subgroup H (that is, to H itself).
God’s Number and the Cayley Graph
The state space of G has a natural graph structure. Construct the Cayley graph Cay(G, S) where the generating set S = {U, U’, U2, D, D’, D2, F, F’, F2, B, B’, B2, R, R’, R2, L, L’, L2} (18 generators in the half-turn metric). Each node is a group element (a cube state), and each directed edge from g to g*s represents applying generator s. The graph has |G| = 43.25 * 10^18 nodes, each of degree 18.
God’s Number is the diameter of this graph: the maximum over all nodes of the shortest-path distance to the identity. In the half-turn metric (HTM), where each quarter-turn and half-turn counts as one move, God’s Number is 20. This was proven in 2010 by Rokicki, Kociemba, Davidson, and Dethridge.
The proof structure:
- Exploit the 48-element symmetry group of the cube (rotations and reflections) to partition the 4.3 * 10^19 states into equivalence classes under symmetry. This reduces the number of distinct cases to about 2.2 * 10^18.
- Apply Kociemba’s algorithm to pre-solve states into specific cosets of the subgroup H (which has about 2 * 10^10 states). This further reduces cases to about 55,882 cosets.
- For each of the 55,882 coset representatives, run an exhaustive search (with pruning) to find the maximum required distance. Show all are at most 20.
In the quarter-turn metric (QTM), where every move counts as 1 regardless of angle, God’s Number is 26.
The distribution of optimal solution lengths is asymmetric. The number of states requiring exactly k moves grows with k up to about k = 18 and then drops sharply. States requiring exactly 20 moves in HTM are relatively rare, roughly 490 million out of 43 quintillion.
Parity in Detail
Parity deserves precise treatment because it is the most common source of implementation errors in cube solvers.
Every face move is a 4-cycle of corners composed with a 4-cycle of edges. A 4-cycle (a b c d) = (a b)(b c)(c d) is a product of 3 transpositions, so it is an odd permutation. Each face move therefore applies an odd permutation to the corners and an odd permutation to the edges.
Let sgn(sigma_C) denote the sign (+1 or -1) of the corner permutation, and sgn(sigma_E) the sign of the edge permutation. After each face move, both signs flip. Therefore, for any state reachable by legal moves, sgn(sigma_C) = sgn(sigma_E). A state where sgn(sigma_C) != sgn(sigma_E) is physically unreachable without disassembling the cube. This is the parity constraint, and it is the source of the factor of 2 in the denominator of |G|.
Concretely: a state where exactly two corners are swapped and all edges are in their correct positions has odd corner parity and even edge parity. No sequence of legal moves can solve it. A solver fed such a state will loop indefinitely if it does not check this invariant first.
On the 4x4x4, the middle-layer edge pieces come in pairs of physically identical cubies. Swapping two pairs (without any other changes) is undetectable by the color-matching objective but changes the permutation parity. States arising from this situation require explicit parity correction algorithms that are not part of the standard 3x3 move set.
For any solver implementation, parity should be verified before solving: compute sgn(sigma_C) and sgn(sigma_E) from the input state and confirm they are equal. If not, the input state is invalid.
The State Space as a Graph and Mixing Time
The Cayley graph Cay(G, S) is regular: every node has the same degree (18 in HTM). BFS from the solved state on this graph finds optimal solutions but is computationally intractable. The frontier at depth 20 covers the entire graph, but the frontier at depth 10 already contains roughly 10^13 nodes, which exceeds the memory of any practical system.
For testing purposes, a relevant question is: how many random moves does it take to produce a state drawn approximately uniformly from G? This is the mixing time of the random walk on Cay(G, S).
The spectral gap of the Cayley graph controls mixing time. For a d-regular graph with second-largest eigenvalue lambda_2 of the adjacency matrix, the mixing time is O(log(|G|) / log(d / lambda_2)). For the cube group, computing lambda_2 exactly is difficult, but empirical evidence suggests that after approximately 20 to 25 random moves, the distribution over states is close to uniform in total variation distance.
This is why the World Cube Association uses a random-state scramble procedure: generate a uniformly random state (using a known algorithm), then find a move sequence reaching that state. Applying 25 random moves from solved does not produce a uniform distribution and tends to undersample states that require many moves to reach, which biases scrambles toward easier positions.
For solver testing: a test suite built from random-move scrambles will systematically underrepresent hard states (those requiring close to 20 moves optimally). A proper test suite samples uniformly from G.
Geometric Representations
Face moves correspond to rigid rotations in three dimensions. The move R is a 90-degree rotation around the x-axis applied to the right-face pieces. As a rotation matrix:
$$ R_x(90°) = \begin{bmatrix} 1 & 0 & 0 \\ 0 & 0 & -1 \\ 0 & 1 & 0 \end{bmatrix} $$A piece at position vector v moves to R_x(90°) * v. Composing two moves is matrix multiplication. Rotation matrices form the rotation group SO(3) in the continuous case, but for the cube only the finite subset of 90-degree rotations around the coordinate axes is needed.
Quaternions offer an alternative. A rotation by angle theta around unit axis n = (n_x, n_y, n_z) is encoded as:
$$ q = \cos\left(\frac{\theta}{2}\right) + \sin\left(\frac{\theta}{2}\right)(n_x i + n_y j + n_z k) $$Rotating a point p (encoded as a pure quaternion) gives p’ = q p q^{-1}. Composing two rotations is quaternion multiplication, which is associative and avoids gimbal lock. For robot arm control systems that compute continuous joint-space trajectories, quaternion interpolation (slerp) produces smoother paths than Euler angle interpolation.
For a pure combinatorial solver, neither rotation matrices nor quaternions are needed: piece positions and orientations are discrete labels, and the group operations are table lookups. Both representations become relevant when the solver must interface with physical hardware – computing camera-to-cube transforms, calibrating robot arm positions, or rendering 3D state visualizations.
Computational Complexity
Finding the optimal solution to an arbitrary 3x3x3 cube state is, for the fixed-size problem, technically O(1): the state space is finite and a complete lookup table exists in principle (though not in practice). The interesting complexity questions arise for the generalized n x n x n cube.
For n x n x n Rubik’s Cube variants, finding an optimal solution is NP-hard in n. This result (Demaine et al.) follows from a reduction showing that optimal cube solving on the generalized cube can encode instances of NP-complete problems. Finding any solution (not necessarily optimal) is in P for fixed n and can be done in O(n^2) moves for general n.
For the fixed 3x3, the interesting complexity tradeoff is between precomputation time and space on one side, and per-query search time on the other. Kociemba’s algorithm occupies a practical optimum: roughly 50 MB of precomputed tables, and per-query search in milliseconds. The full God’s Algorithm table (storing optimal solutions for all 43 quintillion states) would require approximately 43 petabytes with one byte per state, and does not exist in practice.
The subgroup-reduction strategy at the heart of Thistlethwaite’s and Kociemba’s algorithms is the principled way to navigate this tradeoff. By targeting a nested sequence of subgroups G = G_0 supset G_1 supset … supset {identity}, with each G_i small enough to be searched exhaustively with precomputed tables, the algorithms avoid both the intractable full-graph search and the impractical complete lookup table. The group structure, specifically the existence of useful subgroups with small index, is what makes this decomposition possible.
That decomposition is what the next two posts are about.
Summary of the Algebraic Structure
The key facts that drive the algorithms discussed in subsequent posts:
The cube group G has order 8! * 3^7 * 12! * 2^{11} / 2 = 43.25 * 10^18, generated by six face moves. It is non-abelian, which is what makes it interesting and what makes commutators and conjugates useful tools. Every element is a permutation with an associated orientation tuple; the group operation is composition. Legal moves preserve two parity invariants: edge orientation parity (sum of edge orientations mod 2 = 0) and the joint permutation parity (corner and edge permutations have equal sign).
The cube group has subgroups defined by these invariants, and those subgroups are the targets of the phase-reduction algorithms. Entering the subgroup where all edges are correctly oriented is Phase 1 of Kociemba’s algorithm; solving within the subgroup where additionally all corners are correctly oriented and the middle-slice edges are in the middle slice is Phase 2. The mathematical justification for why this decomposition works – and why it produces solutions in 18 to 22 moves – follows from the order and structure of those subgroups and the diameter of the Cayley graph restricted to each.