xxxix. Rubik's Cube and Permutation Puzzles

A permutation puzzle (Rubik’s cube, 15-puzzle, Megaminx, Pyraminx, Top Spin…) is a set of moves, each a permutation of the stickers; the reachable positions form the group generated by the moves. Two questions: how many positions are reachable (group order: Schreier–Sims), and which ones (invariants: parity, orientation sums).

Puzzle	Positions	Notes
$3\times 3\times 3$ Rubik’s cube	$\frac{8!\cdot 3^8\cdot 12!\cdot 2^{12}}{12}=43252003274489856000$	three invariants divide the naive count by $3\cdot 2\cdot 2$
$2\times 2\times 2$ cube	$7!\cdot 3^6=3674160$	one corner fixed (whole-cube rotations removed)
God’s number, $3\times 3\times 3$	20 face turns (Rokicki, Kociemba, Davidson, Dethridge 2010); 26 quarter turns (2014)	computer proofs with symmetry and cosets
God’s number, $2\times 2\times 2$	11 face turns, 14 quarter turns	plain BFS over 3.67M states
group structure	$({\mathbb{Z}}_3^7\times {\mathbb{Z}}_2^{11})⋊((A_8\times A_{12})⋊{\mathbb{Z}}_2)$	orientations, then permutations with equal parity

Invariants of the $3\times 3\times 3$ cube (with fixed centres): (1) the corner permutation and the edge permutation have the same parity; (2) the corner twists sum to $0\mathrm{mod}3$; (3) the edge flips sum to $0\mathrm{mod}2$. Every position satisfying the three is reachable.

// Order of the permutation group generated by the added permutations (of 0..n-1), by Schreier-Sims.
// Level i: orbit of point i under G_i = stabilizer of 0..i-1, with transversal tr[i][j] mapping i -> j.
struct SchreierSims {
    using P = vector<int>;
    int n; vector<vector<P>> gens, tr;                       // gens[i]: strong generators lying in G_i
    SchreierSims(int n) : n(n), gens(n), tr(n, vector<P>(n)) { P id(n); iota(all(id), 0); for (int i = 0; i < n; i++) tr[i][i] = id; }
    static P mul(const P& a, const P& b) { P c(sz(a)); for (int i = 0; i < sz(a); i++) c[i] = a[b[i]]; return c; }   // a after b
    static P inv(const P& a) { P c(sz(a)); for (int i = 0; i < sz(a); i++) c[a[i]] = i; return c; }
    void add(const P& g) { sift(g, 0); }
    void sift(P p, int i) {                                  // p fixes 0..i-1; strip it through the transversals
        for (; i < n; i++) {
            int j = p[i];
            if (tr[i][j].empty()) { addGen(p, i); return; }
            p = mul(inv(tr[i][j]), p);
        }
    }
    void addGen(const P& g, int lvl) {                       // g fixes 0..lvl-1, so it lies in G_0, ..., G_lvl
        for (int i = lvl; i >= 0; i--) {
            gens[i].push_back(g);
            for (int j = 0; j < n; j++) if (!tr[i][j].empty()) { P t = tr[i][j]; extend(mul(g, t), i); }
        }
    }
    void extend(const P& t, int i) {                         // t in G_i maps i to t[i]
        int j = t[i];
        if (!tr[i][j].empty()) { sift(mul(inv(tr[i][j]), t), i + 1); return; }   // Schreier generator
        tr[i][j] = t;
        for (int k = 0; k < sz(gens[i]); k++) { P g = gens[i][k]; extend(mul(g, t), i); }
    }
    i128 order() const {
        i128 r = 1;
        for (int i = 0; i < n; i++) { int c = 0; for (auto& t : tr[i]) c += !t.empty(); r *= c; }
        return r;
    }
};
 
// The 6 outer-face quarter turns of the N x N x N cube as permutations of its 6N^2 stickers.
vector<vector<int>> cubeMoves(int N) {
    vector<array<int, 6>> st;                                // (position, outward normal); coordinates 1-N, 3-N, ..., N-1
    for (int x = 1 - N; x < N; x += 2) for (int y = 1 - N; y < N; y += 2) for (int z = 1 - N; z < N; z += 2) {
        array<int, 3> p{x, y, z};
        for (int a = 0; a < 3; a++) if (abs(p[a]) == N - 1) { array<int, 6> s{x, y, z, 0, 0, 0}; s[3 + a] = p[a] > 0 ? 1 : -1; st.push_back(s); }
    }
    sort(all(st));
    vector<vector<int>> moves;
    for (int a = 0; a < 3; a++) for (int sgn : {-1, 1}) {
        int b = (a + 1) % 3, c = (a + 2) % 3; vector<int> perm(sz(st));
        for (int i = 0; i < sz(st); i++) {
            auto s = st[i];
            if (s[a] == sgn * (N - 1)) {                     // in the turning layer: rotate 90 degrees about axis a
                s[b] = -st[i][c]; s[c] = st[i][b]; s[3 + b] = -st[i][3 + c]; s[3 + c] = st[i][3 + b];
            }
            perm[i] = int(lower_bound(all(st), s) - st.begin());
        }
        moves.push_back(perm);
    }
    return moves;
}

Feeding the six moves of cubeMoves(3) to SchreierSims(54) prints $43252003274489856000$ instantly; three moves of cubeMoves(2) give $3674160$.

Proof: Schreier–Sims computes the group order

Let $G_i$ be the group generated by $S_i=$ gens[i] (every generator added at a level $\ge i$; all of them fix $\mathrm{0..}i-1$) and $O_i$ the set of $j$ with tr[i][j] defined. Closure: every pair (generator $g\in S_i$, transversal element $t$) is processed by extend(g t, i) — when $g$ arrives (loop in addGen) or when $t$ arrives (loop in extend) — so $O_i$ is closed under $S_i$ and is the full orbit of $i$ under $G_i$, and each $t$ maps $i$ to its point. Schreier generators: for each pair whose image point $j$ was already known, $\mathrm{tr}[i][j{]}^{-1}gt$ fixes $\mathrm{0..}i$ and is sifted: either it is stripped to the identity, meaning it is a product $t_{i+1}{t}_{i+2}\cdots$ of transversal elements, or the residue is added as a new generator at the level where stripping failed. Structures only grow, so a product of transversal elements stays one.

Induction from the last level: suppose the products $t_{i+1}\cdots t_{n-1}$ (one from each level) are exactly $G_{i+1}$. By Schreier’s lemma the stabilizer of $i$ in $G_i$ is generated by the Schreier generators $\mathrm{tr}[i][(gt)(i){]}^{-1}gt$, all of which lie in $G_{i+1}$; conversely $S_{i+1}\subseteq S_i$ fixes $i$. So ${\mathrm{Stab}}_{G_i}(i)=G_{i+1}$, every element of $G_i$ is uniquely $t_i\cdot h$ with $h\in G_{i+1}$ (coset decomposition by the image of $i$), and $|G_i|=|O_i|\cdot |G_{i+1}|$. Hence $|G_0|=\prod |O_i|$. Termination: a generator is added at level $i$ only when $O_i$ gains a point, so at most $n^2$ generators exist. Note that a new generator must be added to every level $\le$ its own (the loop in addGen): a permutation fixing $0$ can still enlarge the orbit of $0$ (generators $(01)$ and $(12)$). Checked against brute-force closure for random groups on up to 7 points.

Proof: the three cube invariants, and that they are the only ones

Parity. A quarter turn is a 4-cycle on the corner positions and a 4-cycle on the edge positions, both odd permutations; so after any sequence the corner and edge permutations have equal parity.

Corner twist. Mark on each corner cubie its U or D sticker; its twist is $0,1,2$ according to which of its three faces (in clockwise order starting from the U/D face of the position) carries the mark. U and D turns move corners within the U or D layer and keep the marks on U/D: twists unchanged. An R (or L, F, B) quarter turn changes the twists of its four corners by $+1,+2,+1,+2$, total $6\equiv 0(\mathrm{mod}3)$. Edge flip: mark each edge’s U/D sticker (or F/B sticker for middle-layer edges); with this convention U, D, R, L turns preserve all flips and F, B quarter turns flip exactly four edges, so the total flip is invariant mod 2.

Sufficiency. The positions satisfying the invariants number $\frac{8!\cdot 12!}{2}\cdot 3^7\cdot 2^{11}$: arrangements with equal parities, any twists of 7 corners (the 8th is forced) and flips of 11 edges. The Schreier–Sims computation shows the group generated by the six quarter turns has exactly this order, so every such position is reachable. The $2\times 2\times 2$ count $7!\cdot 3^6$ follows the same way (fix one corner; the twists of 6 of the other 7 corners are free; the permutation parity is free since there are no edges).

Related notes

• Burnside and Pólya (permutation groups)
• Fifteen Puzzle
• Meet in the Middle (bidirectional search for God’s number style problems)