§28

Peg Solitaire — colouring invariants, pagoda functions, GF(4)

English 33-cell peg solitaire: start full except for centre, end with a single peg in the centre. The game looks combinatorially wild, but Reiss (1857), Conway and Beasley (1962–85) pinned it down with algebra: starting from a central hole, the only legal single-peg endpoints are the centre itself and the four arm-tips — 5 cells. We unpack the argument layer by layer: the elementary 3-colouring, Conway's GF(4) framework, the pagoda function family, and Zantema's reinforced parity argument for the European 37-board.

28.1 The board and legal moves

Definition 28.1 — English 33-cell board

The English board is the 33 cells left after cutting

2 \times 2

corners from a

7 \times 7

grid — a cross shape. Standard start: centre cell d4 is empty, the other 32 cells each carry one peg. Standard goal: reduce to one peg sitting in d4.

Definition 28.2 — legal jump

Three adjacent collinear cells

a, c, b

in a row or column. If

a

and

c

hold pegs and

b

is empty, the jump

a \to b

moves the peg from

a

b

and removes the peg on

c

. Diagonal jumps are not allowed on the English board. A chain of consecutive jumps by the same peg is normally counted as a single move.

Four boards · free play

English 33 / European 37 / Triangle 15 / Diamond 25 · click a peg, then click an empty cell to jump

pegs 48

moves 0

28.2 The three-colouring invariant

Colour cells by $r + c (mod 3)$ using 3 hues. Any three collinear cells in any orthogonal direction cover all 3 hues. So every jump simultaneously toggles the parity of each hue-count. Encode the state by the parity vector $(σ_{R}, σ_{B}, σ_{Y}) \in F_{2}^{3}$ :

(σ_{R}, σ_{B}, σ_{Y}) mod 2 is invariant up to simultaneous flip of all three coordinates.

Theorem 28.3 — Reiss (1857), the 5-cell theorem

If a single-peg endgame is reachable from the centre-vacant English start, the surviving peg must occupy one of these 5 cells: centre d4, or the four arm-tips d1, d7, a4, g4.

Proof

The 33-peg starting board has counts $(11, 11, 11)$ . Removing the centre (colour R) yields $(10, 11, 11)$ , parities $(0, 1, 1)$ . Every jump flips all three parities, so any reachable parity vector lies in ${(0, 1, 1), (1, 0, 0)}$ . At the 1-peg endgame, parity (1, 0, 0) forces the survivor onto a hue-R cell.

Apply the same argument with the independent ↘ colouring. The survivor lies in the intersection of the two R-classes — exactly 5 cells: d4, d1, d7, a4, g4.

∎

English 33 · with 3-colouring overlay

click peg → destination to jump. Toggle ↗ / ↘ to overlay the colourings; live counts update.

pegs 48

moves 0

28.3 Reuss / Bell impossibility for sweep games

The 3-colouring argument doesn't decide solvability; it pins where the single survivor can land. Running it independently along ↗ and ↘ yields much stronger obstructions. A typical application, systematised by George Bell (2007) for "sweep games": start with an arbitrary single empty hole, finish with a single peg at a prescribed cell.

Theorem 28.4 — Reuss/Bell sweep table

Let

s

be the empty cell at the start and

t

the single peg position at the end. The "complementary" problem (the other 32 cells filled at start, only

t

filled at end) is solvable only if

s

and

t

agree under both the ↗ and ↘ mod-2 colour classes. The compatibility table:

class_{↗} (s) \equiv class_{↗} (t) (mod 3), class_{↘} (s) \equiv class_{↘} (t) (mod 3)

For example: start vacant at a4 (west tip), end at g4 (east tip) — both endpoints are R-class under ↗ and R-class under ↘. The double constraint is satisfied, and computer search (Bell 2007) confirms the problem is solvable. Conversely, start at b2, end at d4 — same ↗ class but different ↘ class — unsolvable.

Crucially the 3-colouring is necessary, not sufficient. About 5% of (s, t) pairs that pass the double mod-3 check still fail a finer pagoda or GF(4) test. The full classification of solvable start/end pairs took Beasley 1985 plus subsequent exhaustive search — by 1999 every 33-peg problem had been resolved on computer.

28.4 The pagoda function family

Definition 28.5 — pagoda function

An assignment

f (p) \geq 0

to each cell that satisfies, for every collinear triple

(a, c, b)

in the legal-jump sense,

f (b) \leq f (a) + f (c) and (by symmetry) f (a) \leq f (c) + f (b) .

Then

f

is a pagoda function. Immediate consequence: for any board state

P \subseteq cells

, the total

Φ (P) := \sum_{p \in P} f (p)

is non-increasing under any legal jump.

Verification: a jump $a \to b$ replaces ${a, c}$ with ${b}$ , so $ΔΦ = f (b) - f (a) - f (c) \leq 0$ by definition. ∎

The Fibonacci pagoda (Conway)

Let

ϕ = \frac{1 + 5}{2}

be the golden ratio and define

f (p) = ϕ^{- d (p, t)}

where

d (p, t)

is the Manhattan distance from

p

to a target cell

t

. Because

ϕ^{- (d - 2)} = ϕ^{- d} (ϕ^{2}) = ϕ^{- d} (ϕ + 1) = ϕ^{- (d - 1)} + ϕ^{- d}

, every collinear triple has

f (far) = f (mid) + f (near)

: equality holds, still a valid pagoda. This quantifies "peg far from target contributes little" and is the standard tool for ruling out specific long-range starts.

A concrete obstruction: take $t =$ centre d4 and let $f$ be the Fibonacci pagoda rooted at d4. The 32-peg initial total works out to roughly $9 + 45 \approx 17.94$ . The final total (single peg at d4) is exactly 1. Non-increasing doesn't by itself forbid the d4 finish (17.94 ≥ 1). But on extended boards where $t$ sits at a remote corner, the initial total can drop below 1 and the finish is algebraically excluded.

Pagoda calculator · 7 × 7 numeric grid

edit any cell. "verify pagoda" checks every collinear triple (a, c, b) for f(b) ≤ f(a) + f(c); violating cells turn red

∑ f 157

28.5 Conway's GF(4) colouring

In 1961 John Conway unified every parity argument above into linear algebra over the 4-element field $GF (4) = {0, 1, ω, ω^{2}}$ . Viewed as the group $Z_{2} \times Z_{2} = {0, a, b, a + b}$ , assign each cell a non-zero label $ξ (p) \in {1, a, b, ab}$ with the property

ξ (a) + ξ (c) + ξ (b) = 0 in GF (4), for every legal triple (a, c, b) .

One explicit choice: $ξ (r, c) = (r mod 2, c mod 2) \in Z_{2} \times Z_{2}$ . Sanity check on a horizontal triple $(r, c), (r, c + 1), (r, c + 2)$ : the labels are $(r, 0), (r, 1), (r, 0)$ , and the sum is $(3 r, 1) = (r, 1) \neq = 0$ .

That is why Conway's actual assignment toggles labels across even / odd rows — a cyclotomic correction that lifts $ξ$ into the multiplicative group $GF (4)^{\times}$ before summing. The working version: $ξ (r, c) = ω^{r} \cdot ω^{2 c} \in GF (4)^{\times}$ with $ω^{3} = 1$ . Every collinear triple has product $ω^{3 r + 6 c} = 1$ (or its row-shifted analogue), equivalently sum 0. The careful proof is Beasley 1985 §4.

Theorem 28.6 — Conway / Beasley 1985

For any GF(4) labelling

ξ

with the constraint above, the board's GF(4)-weighted sum

Σ (P) := \sum_{p \in P} ξ (p) \in GF (4)

is invariant under every legal jump. Hence a transition from

P_{0}

P_{1}

requires

Σ (P_{0}) = Σ (P_{1})

The space of valid GF(4) labellings is a 2-dimensional vector space over GF(4) (the collinearity constraints have rank 3 in a 5-dim ambient, leaving 2). So we can pick two independent labellings $ξ_{1}, ξ_{2}$ giving two independent GF(4) invariants — the algebraic source of the ↗ / ↘ argument in §28.2. Writing both as equality constraints in $F_{4}^{2}$ immediately recovers Reiss's 5-cell theorem and generalises it to a necessary condition on every start-end pair.

Conway GF(4) labelling · static display

each cell labelled (r mod 2, c mod 2) ∈ {1, a, b, ab}; every legal jump preserves the GF(4) sum

1 · even,even · 16

a · odd,even · 12

b · even,odd · 12

ab · odd,odd · 9

Every legal jump a → b over c satisfies a + b + c = 0 ∈ GF(4); hence the board-wide GF(4) sum is invariant.

28.6 Bergholt's 18-move sweep (English 33)

Invariants only tell us what's impossible; proving possibility needs a concrete solution. The shortest solution of the English 33-cell centre-to-centre problem was found by Ernest Bergholt in 1912 — 18 moves, counting multi-jump chains as single moves. John Beasley verified it as globally optimal by computer search in 1964 — no fewer moves are possible.

Theorem 28.7 — Bergholt 1912, Beasley 1964

The shortest English 33-cell centre-to-centre solution counted in multi-jump moves is exactly 18. All 31 pegs are removed and the survivor sits at d4.

The animation below replays the 18 macro-moves (6 of which chain through multiple elementary jumps for a total of ~30 single jumps). Press ▶ play for the full game, or step manually; the survivor ends at d4.

Bergholt 18-move sweep · replay

18 macro-moves in standard a1..g7 coordinates; multi-jump chains count as one

step 0 / 18

pegs 48

28.7 The SAX invariant on the 15-peg triangle

The 15-peg triangle (5 rows of 1 / 2 / 3 / 4 / 5 cells) carries a separate invariant, the SAX number. Partition the 15 cells into 3 "central" cells (highlighted gold) and 12 "perimeter" cells; let $A$ count filled centrals, $X$ filled perimeters, and $S$ count collinear triples (length-3 lines) that already hold ≥ 2 pegs.

SAX (P) := S + A - X is non-increasing under legal play.

Invariance proof sketch (Beasley 1985): a single jump $a \to b$ over $c$ replaces ${a, c}$ with ${b}$ . Case-analyse the central / perimeter labels of $(a, c, b)$ . Each case bounds $Δ A, Δ X, Δ S$ so that $Δ SAX \leq 0$ overall. Full case bash in Beasley §8.

15-peg triangle · live SAX

central 3 cells highlighted; watch S + A − X be non-increasing (diagonal jumps included)

S (≥2/triple) 13

A (中央 / central) 3

X (外围 / perimeter) 11

S + A − X 5

non-increasing under play — invariant

28.8 European 37-cell board · centre-to-centre impossibility

The European 37-cell board adds 4 "shoulder" cells (b2, f2, b6, f6), totalling 37. An old puzzle: can the centre-to-centre problem be solved on this board? On English yes (Bergholt 18); on European no.

The pure 3-colouring isn't enough: centre (3, 3) and the four tips (0, 3), (3, 0), (3, 6), (6, 3) share class 0 under both ↗ and ↘, so 3-colouring allows a d4 finish. The block comes from Hans Zantema's (1996) reinforced "ABC position" argument: adjoin a second invariant — the parity of pegs on "even-shell" cells (both r and c even). Every legal jump's triple contains 0 or 2 even-shell cells (case check on the 37-cell geometry), so the even-shell parity is preserved. Removing d4 leaves 8 even-shell pegs (parity 0); a single peg at d4 has 1 (parity 1). Contradiction.

Theorem 28.8 — Zantema 1996

On the European 37-cell board, the centre-to-centre single-peg problem is unsolvable.

European 37 · Zantema labelling

numbers = (r + c) mod 3 colouring; bold cells = "even shell"

European 37-cell board. The centre (3, 3) and four arm-tips (0, 3), (3, 0), (3, 6), (6, 3) all share class 0 (A). Pure 3-colouring alone does NOT forbid centre→centre — Zantema's (1996) reinforced "ABC position" argument is needed.

Overlay the "even shell" (cells with both r and c even): every legal jump has 0 or 2 even-shell cells in its triple, so the count's parity is invariant. Start (centre vacant) has 8 even-shell pegs (parity 0); a final single peg at centre has 1 (parity 1). Contradiction. ∎

28.9 Peg solitaire on graphs · sandpiles and chip-firing

Abstract the board to a graph $G = (V, E)$ : vertices = cells, edges = adjacencies. A "legal jump" on the length-2 path $a - c - b$ with chips on $a, c$ and none on $b$ moves a chip from $a$ to $b$ and removes the chip on $c$ . This is a directed variant of chip-firing / sandpile dynamics — ordinary sandpiles fire a vertex when it has at least deg(v) chips, whereas here a triple-based rule governs.

This recasts peg-solitaire solvability as a reachability question for graph chip-firing. The GF(4) labelling becomes a linear chip-firing invariant (Laplacian cohomology); SAX and pagoda functions are non-linear conserved quantities. Beasley (2005) and Engbers-Stocker (2015) generalised this to arbitrary graphs — trees, cycles, the Petersen graph, the cube graph all admit explicit solvability criteria — see §29.

28.10 Computer searches · solved boards and extremal records

Since the 1990s, exhaustive search has turned peg solitaire from "theorems plus clever solutions" into a complete catalogue. Core results on English 33:

problem	solvable?	min moves	reference
centre → centre	✓	18	Bergholt 1912 / Beasley 1964
centre → arm-tip	✓	17	Beasley 1985
any non-centre start → singleton	partial	—	Bell 2007 (全分类)
European 37: centre → centre	✗	—	Zantema 1996
Triangle 15: apex → apex	✓	9	Beasley 1985
Triangle 15: apex → arbitrary	5 of 15 solvable	—	Hentzel 1973

By 1999, all 33 × 33 = 1089 single-hole / single-peg endpoint pairs on the English 33 board had been computer-resolved; roughly a third are solvable. The longest known shortest-solution among them is a 31-move chain from a non-standard start.

This thread, begun by Reiss in 1857 and systematised by Conway and Beasley in the 1960s, has reached "complete table" status for the English board. Larger boards remain open: the 45-cell Wiegleb (6 × 6 plus 4-shell) has not been fully classified — the state space blows past the few hundred million equivalence classes of the 33 board. Active research extends to 3-D boards, arbitrary graphs, and "reverse-jump" variants — see Beasley's supplement, George Bell's database, and the OEIS entries A014225 / A112737.

28.11 Summary · hierarchy of invariants

Ranking the tools of §28 from weakest to sharpest:

Parity: peg count mod 2. Each jump decreases by 1, so 32 → 1 needs 31 jumps; no algebraic obstruction beyond move counting.
3-colouring (Reiss 1857): yields the 5-cell theorem; necessary but not sufficient.
GF(4) labelling (Conway, Beasley 1985): unifies ↗ and ↘ into a 2-dim $F_{4}$ -linear constraint; necessary, still not sufficient.
Pagoda functions (Conway): a family of non-linear (real-valued) invariants; the Fibonacci pagoda excludes long-distance survivors.
SAX number (Beasley 1985): a mixed invariant tuned for the triangular board; strictly stronger than GF(4) alone there.
Zantema's ABC position (1996): on the European 37, "3-colouring + even-shell parity" together forbid centre-to-centre.
Computer enumeration (1999): the ultimate necessary-and-sufficient test — at the cost of state space size. The theorems above are the filters that make the search tractable.

This "colouring / GF(4) / pagoda / SAX / computer" hierarchy is the foundation laid by Conway and Beasley in the 1960s, raising puzzle analysis from clever case-bashing to computable algebra. The same template — find an invariant, verify it under generators, exclude unreachable states — recurs in §5 (cube invariants), §15 (Rubik's-group cohomology), §29 (Petersen graph), and is one of the spine motifs of this book.

∎

cuberoot.me · Rubik's Cube as a Group · 2026