Peg Solitaire Invariants

Peg solitaire — sold as Brainvita in India, Hi-Q in the US — is a one-player board game played on a cross-shaped grid of holes. The board starts full of pegs except for the center hole. You slide a peg over a neighbor into an empty hole; the jumped peg is removed. The classic goal: empty the board down to exactly one peg, standing on the center.

The puzzle looks deceptively easy. You can jump for hours and end up with two or three pegs stuck in the corners. The frustrating question is: was the goal you were aiming for ever reachable, or did you doom yourself from the first move?

This is where mathematics delivers a decisive answer — not by exhaustive search, but by a coloring argument. Paint the board with three colors following a simple repeating pattern. Assign each color a number. A single quantity built from those numbers never changes no matter which jump you make. If start and target disagree on that number, no sequence of moves — not even the cleverest one imaginable — can get you there.

This kind of quantity is called an invariant. Conway and his co-authors formalized it as the pagoda function in their landmark book Winning Ways for Your Mathematical Plays (1982). The invariant technique is solved: given any starting position and any target, you can compute in seconds whether the target is reachable in principle (necessary but not always sufficient). The peg solitaire problem itself, in its general form, is PSPACE-complete (Demaine et al., 2021), but the invariant gives a cheap necessary filter before any deeper search.

Each cell on the board below is labeled 0 (blue) or 1 (amber). The rule is simple: label a cell 1 if and only if both its row index and its column index are non-multiples of 3; otherwise label it 0. The invariant is the XOR (exclusive-or) of labels of all occupied pegs — equivalently, the parity of the count of label-1 pegs.

Click any peg to select it, then click a highlighted hole to jump. Watch the invariant value in the top bar: it never changes. Then click Check center target to see whether the one-peg-at-center goal is consistent with the invariant.

<!-- {{c_layout_comment}} -->
<p class="hint">{{hint_para}}</p>
<div class="top-bar">
  <div class="inv-display">
    <span class="inv-label">{{inv_label}}</span>
    <span id="inv-value" class="inv-badge" aria-live="polite">0</span>
  </div>
  <div class="legend">
    <span class="leg-chip leg-zero">{{leg_zero}}</span>
    <span class="leg-chip leg-one">{{leg_one}}</span>
  </div>
</div>
<div id="board" class="board" role="grid" aria-label="{{board_aria}}"></div>
<div id="status" class="status" aria-live="polite">{{hint_select}}</div>
<div class="btns">
  <button id="btn-target" type="button">{{btn_target}}</button>
  <button id="btn-reset" type="button" class="ghost">{{btn_reset}}</button>
</div>

/* {{c_style_comment}} */
* { box-sizing: border-box; margin: 0; padding: 0; }
body { font-family: system-ui, sans-serif; color: #222; }
.hint { font-size: .85rem; color: #444; margin-bottom: .6rem; line-height: 1.45; }
.top-bar { display: flex; align-items: center; justify-content: space-between;
           margin-bottom: .5rem; flex-wrap: wrap; gap: .4rem; }
.inv-label { font-size: .82rem; color: #555; margin-right: .3rem; }
.inv-badge { font: 700 1rem ui-monospace, monospace;
             padding: .15rem .55rem; border-radius: 6px; min-width: 2rem;
             display: inline-block; text-align: center; transition: background .2s; }
.inv-badge.inv-0 { background: #d4f0d4; color: #1a5c1a; border: 1px solid #8ecb8e; }
.inv-badge.inv-1 { background: #ffe8c0; color: #7a4500; border: 1px solid #e0b870; }
.legend { display: flex; gap: .4rem; }
.leg-chip { font: 600 .78rem system-ui; padding: .18rem .45rem; border-radius: 5px;
            border: 1px solid #bbb; }
.leg-zero { background: #e8eef3; color: #1d3557; border-color: #c2cedb; }
.leg-one  { background: #ffe8c0; color: #7a4500; border-color: #e0b870; }
/* {{c_board_comment}} */
.board { display: grid; grid-template-columns: repeat(7, 40px);
         grid-template-rows: repeat(7, 40px); gap: 3px; margin: .25rem 0; }
.cell { width: 40px; height: 40px; border-radius: 7px; display: flex;
        align-items: center; justify-content: center;
        user-select: none; position: relative; }
.cell.empty-border { background: transparent; }
.cell.hole-0 { background: #e8eef3; border: 1px solid #c2cedb; }
.cell.hole-1 { background: #f8f0e0; border: 1px solid #d8c898; }
.cell.peg-0 { background: #1d3557; border: 2px solid #14273e; cursor: pointer; }
.cell.peg-1 { background: #c07000; border: 2px solid #9a5a00; cursor: pointer; }
.cell.peg-0::after, .cell.peg-1::after { content: "●"; font-size: 1.25rem;
  color: #fff; position: absolute; top: 50%; left: 50%; transform: translate(-50%,-52%); }
.cell.selected { outline: 3px solid #e63946; outline-offset: -2px; }
.cell.landing { outline: 3px solid #0a7d33; outline-offset: -2px; cursor: pointer; }
.cell.landing::after { content: "○" !important; font-size: 1.2rem;
  color: #0a7d33 !important; }
.status { font-size: .9rem; font-weight: 600; margin: .4rem 0; min-height: 1.3em; }
.status.ok  { color: #0a7d33; }
.status.bad { color: #c92f3c; }
.status.info { color: #1d3557; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; }
button { font: 600 13px system-ui; padding: .42rem .85rem;
         border: 1px solid #1d3557; background: #1d3557;
         color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }

// Code not found

Why does every jump preserve the XOR? For any legal jump — peg at $A$ over $B$ into $C$ — the three cells are collinear and $B$ lies between $A$ and $C$. No matter where they are on the board, $\ell(A) \oplus \ell(B) \oplus \ell(C) = 0$ (where $\ell$ is the label function and $\oplus$ is XOR). Removing $A$ and $B$ and adding $C$ changes the total XOR by exactly $\ell(A) \oplus \ell(B) \oplus \ell(C) = 0$ — so the invariant is unchanged. If your current board has invariant 1 and the target has invariant 0, no path leads there.

The XOR demo captures one peg solitaire invariant, but the mathematical theory is richer.

The GF(2) invariant in detail. Define $\ell(r,c) = 1$ if $r \not\equiv 0 \pmod{3}$ and $c \not\equiv 0 \pmod{3}$, else $\ell(r,c) = 0$. For any legal jump — peg at $(r_1,c_1)$ over $(r_2,c_2)$ into $(r_3,c_3)$ (collinear, distance 2) — one can verify that $\ell(r_1,c_1) \oplus \ell(r_2,c_2) \oplus \ell(r_3,c_3) = 0$. This means every jump XORs zero into the total, keeping it fixed. The quantity $\bigoplus_{(r,c)\in\text{occupied}} \ell(r,c)$ is therefore an exact invariant of the game. Starting from the standard position (all 32 pegs), the invariant is 0; any reachable position also has invariant 0; positions with invariant 1 (like a single peg at $(1,2)$) are forever out of reach.

Pagoda functions. Conway and co-authors generalized this with pagoda functions: assign a real value $f(h)$ to each hole such that for every jump $a \to b \to c$, the inequality $f(a) + f(b) \leq f(c)$ holds. The total board weight $\sum_{h\,\text{occupied}} f(h)$ can only decrease. If a target's pagoda score exceeds the starting score, that target is unreachable — a one-line proof by inequality. The XOR invariant is the special case where equality holds and the values are in $\{0,1\}$.

Computational complexity. Beyond single impossible positions, the general question — given an arbitrary subset of pegs as start and another as goal, does a sequence of jumps exist? — was shown PSPACE-complete by Demaine, Demaine, Eppstein and Winstanley (2021). The invariant test runs in $O(n)$ and rules out all cases it can instantly; only remaining positions need the full search.

Why this matters conceptually. The invariant method is a cornerstone of algorithm analysis and combinatorial proof — the same pattern appears in P vs NP impossibility arguments and in correctness proofs of greedy algorithms where loop invariants track progress.

The invariant method that kills off impossible peg-solitaire targets is the same technique deployed across computer science:

• Combinatorial game theory: pagoda functions are the standard tool for analyzing peg solitaire and similar jump games. Conway, Berlekamp and Guy's Winning Ways (1982) made them famous.
• Algorithm analysis: loop invariants are the formal backbone of correctness proofs — the assertion that holds before and after every iteration and implies the result when the loop ends.
• Formal verification and model checking: state invariants rule out unsafe system states without searching the entire reachable state space, the same principle as the pagoda bounding the reachable pegs.
• Distributed systems: mutual-exclusion protocols rely on invariants (e.g., at most one process holds the lock) to prove that a forbidden state is never reached.
• Cryptographic protocols: many impossibility results — you cannot sign without the private key — are stated and proved as invariants of the protocol execution.

Once you recognize the pattern — "define a quantity, show every move preserves or worsens it, conclude the target is unreachable" — you see it everywhere. Peg solitaire makes the idea concrete enough to hold in your hand.

Peg solitaire looks like a patience test, but it hides one of mathematics' cleanest lessons: sometimes the reason you cannot reach a goal has nothing to do with cleverness or search depth. A single invariant — a number the rules of the game never let you change — settles the question in constant time.

Conway's pagoda functions turn that intuition into a complete theory. Color the board, assign weights, verify the inequality. If the target score is higher than any reachable score, the target is provably out of reach — not just hard to find, but impossible.

The same reasoning powers loop-invariant proofs in algorithms, state invariants in formal verification, and monovariant arguments in P vs NP theory. The next time you are stuck on a puzzle and wonder whether the goal is even achievable, you are asking an invariant question — and mathematics may well hand you the answer before you make your next move.