Introduction

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.

Try It

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.

<!-- Hint paragraph + invariant display bar + board + controls -->
<p class="hint">Each cell is labeled <b>0</b> (blue) or <b>1</b> (amber) — a cell gets label 1 only when both its row AND column index are not multiples of 3. The <b>invariant</b> is the XOR (parity) of labels of all pegs on the board: it never changes no matter how you jump. Click a peg to select it, then click a green-outlined hole to jump.</p>
<div class="top-bar">
  <div class="inv-display">
    <span class="inv-label">Invariant (XOR of labels):</span>
    <span id="inv-value" class="inv-badge" aria-live="polite">0</span>
  </div>
  <div class="legend">
    <span class="leg-chip leg-zero">Label 0</span>
    <span class="leg-chip leg-one">Label 1</span>
  </div>
</div>
<div id="board" class="board" role="grid" aria-label="Peg solitaire board, 33 holes in a cross shape"></div>
<div id="status" class="status" aria-live="polite">Click a peg to select it, then click a highlighted hole to jump.</div>
<div class="btns">
  <button id="btn-target" type="button">Check center target</button>
  <button id="btn-reset" type="button" class="ghost">Reset board</button>
</div>
/* Peg solitaire invariant demo — styles */
* { 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; }
/* 7x7 grid; only the 33 cross-shaped holes are rendered */
.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; }
const i18nFmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Standard English peg solitaire board — 33 holes in a cross shape
const VALID = new Set([
  '0,2','0,3','0,4',
  '1,2','1,3','1,4',
  '2,0','2,1','2,2','2,3','2,4','2,5','2,6',
  '3,0','3,1','3,2','3,3','3,4','3,5','3,6',
  '4,0','4,1','4,2','4,3','4,4','4,5','4,6',
  '5,2','5,3','5,4',
  '6,2','6,3','6,4'
]);
const key = (r,c) => r+','+c;
// GF(2) invariant: label(r,c) = 1 iff r%3 != 0 AND c%3 != 0; else 0
// Every legal jump XORs labels of start, mid, end — net XOR = label(start)^label(mid)^label(end) = 0 for all jumps
const label = (r,c) => ((r%3!==0)&&(c%3!==0)) ? 1 : 0;
// Invariant = XOR of labels of all occupied cells (= parity of count of label-1 pegs)
function invariant(ps) {
  let v = 0;
  for (const k of ps) { const [r,c] = k.split(',').map(Number); v ^= label(r,c); }
  return v;
}
// Standard starting position — all 33 holes filled except the center (3,3)
const pegs = new Set([...VALID]);
pegs.delete('3,3'); // Standard start — center hole empty
let selected = null;
let landings = [];
// A legal jump goes 2 cells orthogonally over an occupied cell into an empty cell
function validLandings(r, c) {
  const out = [];
  for (const [dr,dc] of [[-2,0],[2,0],[0,-2],[0,2]]) {
    const lr=r+dr, lc=c+dc, mr=r+dr/2, mc=c+dc/2;
    const lk=key(lr,lc), mk=key(mr,mc);
    if (VALID.has(lk) && !pegs.has(lk) && pegs.has(mk)) out.push([lr,lc]);
  }
  return out;
}
function updateInvDisplay() {
  const v = invariant(pegs);
  const el = document.getElementById('inv-value');
  el.textContent = v;
  el.className = 'inv-badge inv-' + v;
}
function setStatus(t, cls) {
  const s = document.getElementById('status');
  s.innerHTML = t; s.className = 'status ' + cls;
}
function render() {
  const board = document.getElementById('board');
  board.innerHTML = '';
  for (let r=0; r<7; r++) for (let c=0; c<7; c++) {
    const d = document.createElement('div');
    const k = key(r,c);
    if (!VALID.has(k)) { d.className = 'cell empty-border'; board.appendChild(d); continue; }
    const lbl = label(r,c);
    const isPeg = pegs.has(k);
    const isSel = selected === k;
    const isLand = landings.some(([lr,lc]) => lr===r && lc===c);
    if (isLand) {
      d.className = 'cell landing hole-'+lbl;
      d.title = 'Jump here';
      d.addEventListener('click', () => doJump(r,c));
    } else if (isPeg) {
      d.className = 'cell peg-'+lbl + (isSel ? ' selected' : '');
      d.title = i18nFmt('Label %lbl% — click to select', { lbl: lbl });
      d.addEventListener('click', () => selectPeg(r,c));
    } else {
      d.className = 'cell hole-'+lbl;
    }
    board.appendChild(d);
  }
  updateInvDisplay();
}
function selectPeg(r, c) {
  const k = key(r,c);
  if (selected === k) { selected=null; landings=[]; render(); setStatus('Click a peg to select it, then click a highlighted hole to jump.',''); return; }
  selected = k;
  landings = validLandings(r, c);
  render();
  if (landings.length === 0) setStatus('No legal jumps from this peg.', 'info');
  else setStatus(i18nFmt('%n% landing hole(s) available — click a highlighted hole to jump.', { n: landings.length }), 'info');
}
function doJump(lr, lc) {
  if (!selected) return;
  const [sr,sc] = selected.split(',').map(Number);
  const mr = (sr+lr)/2, mc = (sc+lc)/2;
  pegs.delete(selected); pegs.delete(key(mr,mc)); pegs.add(key(lr,lc));
  selected = null; landings = [];
  render();
  setStatus(i18nFmt('Jumped! %remaining% peg(s) left. Invariant still %inv%.', { remaining: pegs.size, inv: invariant(pegs) }), 'info');
}
function checkTarget() {
  // Classic goal — one peg remaining at the center (3,3)
  // Center (3,3): r=3, c=3; both 3%3=0, so label=0. Invariant of target = 0.
  const targetLabel = 0; // center (3,3) has label 0 — parity of one label-0 peg = 0
  const cur = invariant(pegs);
  if (cur === targetLabel) setStatus('Invariant = 0 matches the center-peg target (invariant 0) — not ruled out by this invariant!', 'ok');
  else setStatus('Invariant mismatch — the center-peg target has invariant 0, but current board has invariant 1. The center goal is provably unreachable from here!', 'bad');
}
function resetBoard() {
  pegs.clear();
  for (const k of VALID) pegs.add(k);
  pegs.delete('3,3');
  selected = null; landings = [];
  render(); setStatus('Click a peg to select it, then click a highlighted hole to jump.', '');
}
document.getElementById('btn-target').addEventListener('click', checkTarget);
document.getElementById('btn-reset').addEventListener('click', resetBoard);
render();
setStatus('Click a peg to select it, then click a highlighted hole to jump.', '');
Result
Console

Why does every jump preserve the XOR? For any legal jump — peg at AA over BB into CC — the three cells are collinear and BB lies between AA and CC. No matter where they are on the board, ℓ(A)⊕ℓ(B)⊕ℓ(C)=0\ell(A) \oplus \ell(B) \oplus \ell(C) = 0 (where ℓ\ell is the label function and ⊕\oplus is XOR). Removing AA and BB and adding CC changes the total XOR by exactly ℓ(A)⊕ℓ(B)⊕ℓ(C)=0\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 Real Math

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

The GF(2) invariant in detail. Define ℓ(r,c)=1\ell(r,c) = 1 if r≢0(mod3)r \not\equiv 0 \pmod{3} and c≢0(mod3)c \not\equiv 0 \pmod{3}, else ℓ(r,c)=0\ell(r,c) = 0. For any legal jump — peg at (r1,c1)(r_1,c_1) over (r2,c2)(r_2,c_2) into (r3,c3)(r_3,c_3) (collinear, distance 2) — one can verify that ℓ(r1,c1)⊕ℓ(r2,c2)⊕ℓ(r3,c3)=0\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 ⨁(r,c)∈occupiedℓ(r,c)\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)(1,2)) are forever out of reach.

Pagoda functions. Conway and co-authors generalized this with pagoda functions: assign a real value f(h)f(h) to each hole such that for every jump a→b→ca \to b \to c, the inequality f(a)+f(b)≤f(c)f(a) + f(b) \leq f(c) holds. The total board weight ∑h occupiedf(h)\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}\{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)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.

Where It Matters

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.

Conclusion

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.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/peg-solitaire-invariants/Content licensed under CC BY-NC 4.0.