Rotational puzzles on graphs — Jaap's (x, y, z) classification

Abstract the cube's face turns to any graph: a connected graph with marked faces (directed cycles); each face gives a generator that cyclically rotates its pieces. The puzzle group $\Gamma$ is a subgroup of $S_n$ ($n$ = piece count). Natural question: which graphs give $\Gamma =S_n$, which $A_n$, which something exotic?

31.1 Formalisation: graph, face, generator

Three immediate examples:

• 3×3 corners: G = the 8 corner-vertices of a 3-cube; 6 length-4 face cycles; $\Gamma$ on positions contains $A_8$ (orientation tracked separately).
• Pyraminx edges: G = midpoints of the 6 edges of a tetrahedron; 4 length-3 face cycles; gives a subgroup of $A_6$.
• 15-puzzle (as a degenerate example): a 4×4 grid plus one "blank." Cycling the blank around any 2×2 face is essentially a face turn — Wilson's 1974 bridge.

31.2 Two-face theorem — the (x, y, z) triple

Two faces share a contiguous segment. Let face 1 have $x$ unique pieces, face 2 have $z$ unique, and $y$ be shared, so $n=x+y+z$. Without loss of generality $x\le z$. Face lengths are $f_1=x+y$, $f_2=y+z$.

Proof sketch (Jaap's exposition):

1. Parity: ${\rho }_1$ is an $f_1$-cycle with $\mathrm{sgn}({\rho }_1)=(-1{)}^{f_1-1}$. If both $f_i$ are odd, $\Gamma \subseteq A_n$; if one is even, $\Gamma$ contains an odd permutation, so it can equal $S_n$ once we know $A_n\subseteq \Gamma$.
2. Constructing a 3-cycle: the commutator ${\rho }_1{\rho }_2{\rho }_1^{-1}{\rho }_2^{-1}$ is non-trivial and, in most face-size combinations, equals a 3-cycle or factors into 3-cycles. Key cases:
3. y = 1: with one shared piece, the commutator is exactly a 3-cycle (${\rho }_1$ pushes it one step on face 1, ${\rho }_2$ pushes onto face 2, the inverses retrace — three vertices touched).
4. y ≥ 3 and (x,z) ≠ (2,2): a seven-step combination of ${\rho }_1{\rho }_2$ and ${\rho }_2^{-1}{\rho }_1^{-1}$ produces a 3-cycle. Since 3-cycles generate $A_n$, we get $\Gamma \supseteq A_n$.
5. Verifying the exceptions: (2,2,2) and (1,3,2) both have $n=6$ but order stops at 120 = 5! < 360 = 6!/2. Direct group-theoretic computation or GAP confirms.

What is this order-120 group? It is not the standard $S_5$-on-5-points but the exceptional action of $S_5$ on 6 points coming from $PG{L}_2({\mathbb{F}}_5)$ on the projective line ${\mathbb{P}}^1({\mathbb{F}}_5)$ (6 points). This is the same "6-vs-5" sporadic isomorphism that drives §30.

This covers Pyraminx two-face (2,1,2 ⇒ $A_5$), Impossiball two-face (3,2,3 ⇒ $A_8$), Alexander's Star (4,1,4 ⇒ $A_9$). It also explains why (2, 2, 2) feels special — its 6 corners are exactly the §30 story.

31.3 Worked examples — eight (x, y, z) specimens

Substitute the theorem into eight notable triples and see where each falls. The "construction" column gives an explicit short commutator producing a 3-cycle — easy to verify by hand:

Note (2,1,2) ⇒ $A_5$ of order 60 — the smallest non-Abelian simple group, proven in §21. Pyraminx's two-face local pattern realises the very bottom of the classification of finite simple groups. A plastic toy bottoms out one of the 19th century's greatest mathematical achievements.

Try (2,1,2): press L, R, L⁻¹, R⁻¹ — you should see a 3-cycle (type 3·1², sgn = +1). Try (2,2,2): the same commutator yields a longer cycle, not a 3-cycle — visual evidence of (2,2,2)'s "stuck at 5!" anomaly.

31.4 Three faces and beyond — open classification

Real physical puzzles are mostly not two-faced. The cube has 6 faces, the Megaminx 12, the Pyraminx 4 — each extra face is a new generator and the combinatorics explodes. What's known:

• Three-face "rescue": add a third face to (2,2,2); if the new face pairs with one of the original two in a non-exceptional way (falling into the $A_n$ or $S_n$ branch of Thm 31.2), the whole group jumps up to $A_n$ or $S_n$. This is why (2,2,2) is abstractly fascinating but never the bottom line of any physical puzzle — a third face always erases the anomaly.
• Independent piece types: physical puzzles usually have "corners + edges" (3×3) or "edges + centres + tips" (Pyraminx); pieces of different types are never mixed by face turns. The group factors as$$\Gamma \hookrightarrow {\Gamma }_{\text{corners}}\times {\Gamma }_{\text{edges}}\times \cdots$$and parity/orientation laws are then imposed. This is the heart of §6's "right place, wrong orientation" classification.
• Open problem (Jaap): given $k\ge 3$ faces with pairwise overlap lengths $y_{ij}$ and face sizes $f_i$, classify $\Gamma$. No full theorem is known for $k\ge 3$ — only "large enough ⇒ $A_n$ or $S_n$" partial results. Whether the exception list is finite remains open.
• Multi-arc overlaps: Hungarian Rings and friends have two faces sharing on two disjoint arcs. This breaks the (x,y,z) parameterisation; Singmaster's Cubic Circular handles special cases, no general answer.

31.5 Wilson 1974 — the sliding-puzzle companion classification

In 1974 R. M. Wilson published Graph Puzzles, Homotopy, and the Alternating Group giving the complete classification for sliding puzzles: a single "blank" slides along edges of a connected graph $G$ from initial vertex $b$. The state group is generated by "blank-around-a-face" operations — essentially the "blank-included" cousin of Thm 31.2.

Three families of exceptions:

• Cycle $C_n$: blank traversing once gives cyclic ${\mathbb{Z}}_n$, far short of $A_{n-1}$
• Bipartite graph (not a cycle): the blank alternates between two parts on each move, so its parity is constrained, $W\subseteq A_{n-1}$
• θ₀: sporadic 7-vertex exception with $|W|=120$ — isomorphic to (1,3,2) of Thm 31.2

The 15-puzzle is bipartite (the 4×4 grid is two-coloured by checkerboard), so Wilson's theorem gives $A_{15}$, not $S_{15}$. That is the algebraic explanation of Loyd's 1880 "$1000 prize for swapping 14 and 15": the swap is a transposition, an odd permutation in $S_{15}\setminus A_{15}$ — provably unreachable.

31.6 Computer-aided classification — Schreier-Sims

Given generators $\{g_1,\dots ,g_k\}$ compute $|G|$. Brute enumeration is exponential. In 1970 C. Sims gave a polynomial-time algorithm — Schreier-Sims:

1. Choose a base $(b_1,b_2,\dots ,b_m)$ so that $G\supset G_{b_1}\supset G_{b_1{b}_2}\supset \cdots \supset \{e\}$
2. For each stabiliser layer compute its orbit via "Schreier generators"
3. Orbit-stabiliser yields $|G|={\prod }_i|{\text{orbit}}_i|$

Complexity $O(n^5\log |G|)$; Seress 2003 surveys many refinements that handle $n\sim 10^6$. GAP, sympy and Magma ship Schreier-Sims out of the box: feed in the cube's six face generators and get $|G|=43,252,003,274,489,856,000$ in seconds.

Schreier-Sims output for small puzzle groups:

31.7 Surfaces, quotients, and wreath products

Strip away the physical packaging and a rotational puzzle is a discrete quotient of a manifold rotation action. The 2×2×2 corner state space is exactly$$({\mathbb{Z}}_3{)}^7⋊S_8,$$where $({\mathbb{Z}}_3{)}^7$ tracks "the 7 independent corner orientations (the 8th is forced by the orientation-sum conservation law)" and $S_8$ tracks corner positions. The semidirect product encodes "positions move first, orientations follow."

More generally, the wreath product ${\mathbb{Z}}_n\wr S_k$ describes "$k$ objects, each with ${\mathbb{Z}}_n$ orientation, freely permuted and individually twisted":$${\mathbb{Z}}_n\wr S_k=({\mathbb{Z}}_n{)}^k⋊S_k,$$with $S_k$ acting on $({\mathbb{Z}}_n{)}^k$ by permuting coordinates. Order $|{\mathbb{Z}}_n\wr S_k|=n^k\cdot k!$.

• 2×2×2 corners: $({\mathbb{Z}}_3\wr S_8)/{\mathbb{Z}}_3$ (quotient by the orientation-sum law). Order $3^8\cdot 8!/3=3,674,160$.
• 3×3 corners: same, coupled to edges by parity — full group is the index-2 subgroup of $({\mathbb{Z}}_3\wr S_8)\times ({\mathbb{Z}}_2\wr S_{12})$.
• Pyraminx: the 4 tips are independent $({\mathbb{Z}}_3{)}^4$ (non-interacting); the 6 edges form $A_6\times ({\mathbb{Z}}_2{)}^{?}$; the 4 centres each ${\mathbb{Z}}_3$ with constraints — assembled by semidirect product.
• Skewb: 8 corners + 6 centres, 4 diagonal-axis generators, wreath ${\mathbb{Z}}_3\wr S_8$ divided by two constraints (corner-twist sum, centre-permutation parity) gives 3,149,280.

Wreath products correspond directly to covering spaces: each ${\mathbb{Z}}_n$ is one piece's orientation circle ($S^1$), and the configuration space of $k$ pieces is a $\left(\genfrac{}{}{0ex}{}{n}{k}\right)$-fold quotient; the wreath product is the discrete symmetry of this "position × orientation" total manifold. See M. Davis, The Geometry and Topology of Coxeter Groups.

31.8 Puzzle gallery — 12 physical specimens vs (x, y, z)

Apply the classification to physical puzzles. Click each card to inspect its (x,y,z) decomposition (when applicable), its group, its order, and a one-line intuition:

Note that (2,1,2) recurs: Pyraminx, Skewb, and any "tetrahedron-face-plus-an-axis" local pattern look like this, making $A_5$ the "algebraic LCM of tetrahedral symmetry." This is exactly why the Pyraminx's edge positions embed in $A_6$ — 6 edges modulo 4 face rotations equals the induced action of $A_5$.

31.9 Open problems

1. k-face classification: the two-face theorem has 2 exceptions. For $k=3$ how many exceptions are there? Is the list finite? Jaap lists a few specific three-face anomalies but no general theorem.
2. Disconnected overlap: Hungarian Rings, Whip-It, etc. share two disjoint arcs. The (x,y,z) parameterisation fails; one needs the multiset $\{y_1,y_2,\dots \}$ of overlap lengths. Only scattered results.
3. Oriented graph puzzles: Jaap's classification assumes unoriented pieces. Add per-vertex ${\mathbb{Z}}_n$ orientation with conservation laws, the puzzle group becomes a subgroup of ${\mathbb{Z}}_n\wr \Gamma$ — which conservation laws can arise?
4. Jumbling puzzles: helicopter cube and friends have "non-integer face turns"; the state space is no longer a group but a manifold. Modern attempts beyond Hofstadter are sparse — the next frontier of puzzle algebra.
5. Diameter: for (x,y,z) rotational puzzles, what is the Cayley diameter of $\Gamma$? The exceptional (2,2,2) has diameter 5. No closed form is known for the generic case.

31.10 Wreath products S_k ≀ ℤ_n — the algebra of orientation

Take $k$ objects each carrying ${\mathbb{Z}}_n$ orientation (n = 2 for edges, n = 3 for corners, n = 4 for cube centres). Orientation is a function $f:\{1,\dots ,k\}\to {\mathbb{Z}}_n$; permuting positions $\sigma \in S_k$ drags orientations along. The total group is$${\mathbb{Z}}_n\wr S_k={\mathbb{Z}}_n^k⋊S_k,|{\mathbb{Z}}_n\wr S_k|=n^k\cdot k!.$$Multiplication rule:$$(f,\sigma )(g,\tau )=(f+\sigma \cdot g,\sigma \tau ),$$where $(\sigma \cdot g)(i)=g({\sigma }^{-1}(i))$ ("permute, then twist").

The group of an actual puzzle is the subgroup of a wreath product cut out by conservation laws. For example:

• $G_{\text{2×2 corners}}=\ker (\Sigma :{\mathbb{Z}}_3\wr S_8\to {\mathbb{Z}}_3)$, the kernel of the twist-sum, index 3
• $G_{\text{3×3}}=\ker ({\Sigma }_c,{\Sigma }_e,{\mathrm{sgn}}_c\cdot {\mathrm{sgn}}_e)$ with three conservation laws, index 12
• $G_{\text{Megaminx}}$ sits inside $({\mathbb{Z}}_3\wr S_{20})\times ({\mathbb{Z}}_2\wr S_{30})\times (S_5\wr \text{stuff})$ — full formula in §15.1

Graph-theoretic side: ${\mathbb{Z}}_n\wr S_k$ is the symmetry of "$k$ dangling ${\mathbb{Z}}_n$-strings, freely permuted." In Cayley-graph theory wreath products are the classical recipe for constructing groups of large diameter, used in the 1930s to settle questions about maximal subgroups of $S_n$. Modern view: a wreath product is the automorphism group of a "coloured forest" (the algebraic dual of Boyer-Moore data structures).

This section promotes "Rubik's cube" to "rotational puzzle on a graph": two faces give (x, y, z); many faces give wreath subgroups; computation runs through Schreier-Sims; the limit is jumbling manifolds. Wilson 1974's sliding cousin supplies the dual viewpoint, and homotopy translates combinatorics into algebraic topology. The exception lives forever at (2,2,2): $PG{L}_2({\mathbb{F}}_5)\cong S_5$ acting on 6 points — the puzzle theory's smallest pretty counterexample, and the stitch that sews this section into §30.