I built peg solitaire in the browser — the English 33-hole board and the European 37-hole board — with a solver behind a Solve button. For the classic English game (every hole filled except the centre) a breadth-first sweep visits every reachable position, one representative per symmetry class of the square, and finishes in 126 seconds in one Node process: 187,636,299 positions (23,475,688 up to symmetry), and 40,861,647,040,079,968 jump sequences that leave one peg in the centre. Positions, positions up to symmetry, jump sequences, dead ends, still-winnable positions and still-winnable up to symmetry match six OEIS sequences term for term. The still-winnable column needs no backward search at all, only a duality: reverse a jump sequence and swap pegs for holes, and it is legal again.
The one published number that did not match is on Wikipedia: "23,475,688 reachable positions ... only about 2.2% of all possible board positions". 23,475,688 / 2^33 is 0.27%. The 2.2% belongs to the other count, the 187,636,299 positions not folded by symmetry (2.18%).
The rules
Fill every hole but one. A peg jumps orthogonally over a neighbouring peg into the empty hole straight beyond it, and the jumped peg is removed. You win with one peg left — ideally in the hole that was empty at the start. The English board is a 7×7 square minus its 2×2 corners (33 holes, 76 possible jumps); the European board adds the four inner corners (37 holes, 92 jumps).
A position is a bit set over the holes, 33 or 37 bits. A JavaScript number holds that exactly, but bitwise operators stop at 32 bits, so hot loops keep a (lo, hi) pair of int32s and a jump is two mask tests and an XOR:
// pegs on from and over, `to` empty
if ((lo & f) === f && (hi & fh) === fh && (lo & t) === 0 && (hi & th) === 0) {
const nlo = lo ^ (f | t), nhi = hi ^ (fh | th); // flip all three holes
}
What you know before searching: position classes
Work in the four-element field GF(4) = {0, 1, p, p²} with p² = p + 1. Give a peg in row r, column c the value p^(r+c) for a sum A and p^(r−c) for a sum B. Three holes in a line carry p^k, p^(k+1), p^(k+2), and
p^k + p^(k+1) = p^k (1 + p) = p^k · p² = p^(k+2),
so a jump — which trades the first two pegs for the third — never changes (A, B). That pair takes 16 values: the position class (de Bruijn 1972; the same thing as Conway's rule of three). Addition in GF(4) is XOR on two bits:
const POW = [1, 2, 3]; // p^0, p^1, p^2 coded in two bits
const pw = (k: number) => POW[((k % 3) + 3) % 3];
export function positionClass(board: Board, pos: number): number {
let a = 0, b = 0;
for (let i = 0; i < board.n; i++) {
if (!has(pos, i)) continue;
a ^= pw(board.row[i] + board.col[i]);
b ^= pw(board.row[i] - board.col[i]);
}
return a * 4 + b;
}
A lone final peg can only stand on a hole whose own class equals the position's. The page draws those holes with gold rings, all the time.
- English central game: five rings — d1, a4, d4, g4, d7: the centre and the tip of each arm.
- European central game: no rings at all. The full board minus the centre is in a class no single peg belongs to, so the game has no solution. The solver says so after 0 positions; with the class test switched off it expanded 10,000,001 positions (8.2 s) without an answer.
- European single vacancies: up to symmetry there are 8 holes you can start from, and only three — c1, d2 and d3 — are in a class with any feasible finish. Those are exactly the three solvable starts Wikipedia lists after Brassine (1981). Replaying the three published solutions, all are legal and they end as c1 → e1, d2 → d3 and d3 → d2. So on the European board the class test alone decides which single vacancies are solvable: it proves the impossible ones, and the published solutions prove the rest.
On the English board there are 33 × 33 = 1,089 single-vacancy → single-survivor problems (one hole empty at the start, one peg in a named hole at the end); the class test leaves 125. On the European board it leaves 64 of 1,369.
Counting every position of the English game
The naive version dies on memory
The first version kept each level unfolded, in a 2^26-slot open-addressing table: three Float64Arrays (key, count low, count high), 1.6 GB. The peak level holds about 29 million positions, a load factor of 0.43 — fine on paper.
Level 8, 78 thousand positions, took ten seconds. The profiler put nearly all of it in the insert function, but counting probes gave 1,422 collisions over 1.07 million inserts — the hash was innocent. /usr/bin/time -l told the story: the same run with a 2^22 table took 2.0 s; with 2^26 it took 47.99 s, 31.93 s of it in the kernel. The machine has 24 GB but had 9 GB in swap, and a 1.6 GB table hit at random pages in and out of compression.
Fold by the eight symmetries
Normalise every position to the smallest of its eight images, and the peak level shrinks to 3.63 million representatives; a 2^23-slot table (200 MB) is plenty. The image is three lookups of 11-bit chunks per symmetry:
function canon(key: number): number {
const lo = key >>> 0;
const hi = (key - lo) / TWO32;
const v0 = lo & 0x7ff, v1 = (lo >>> 11) & 0x7ff, v2 = (lo >>> 22) | (hi << 10);
let best = key;
STAB = 1; // symmetries fixing key, identity included
for (let g = 0; g < 7; g++) {
const t = SYM[g];
const img = t[0][v0] + t[1][v1] + t[2][v2];
if (img < best) best = img;
if (img === key) STAB++;
}
return best;
}
A representative stands for 8 / STAB real positions, which gives the unfolded counts for free.
Carrying path counts through the fold
The start is fixed by all eight symmetries, so every member of a class is reached by the same number of jump sequences; a representative P carries paths(P), the count for P itself. A move P → q with canon(q) = Q adds paths(P) × |orbit P| to Q's accumulator. What accumulates is every move from P's whole orbit into Q's whole orbit, which equals paths(Q) × |orbit Q| — so when the level is done, each accumulator is divided back by its orbit size. The code throws if the division is ever inexact; it never has. Counts pass 10^21, so each is a pair of doubles, hi * 2^32 + lo, with a carry on every add.
Winnability without a backward search
Take a jump a over b into c: before it, a and b hold pegs and c is empty; after it, the reverse. Swap every peg and hole, and the after position becomes one where a jump from a over b into c produces the swapped before position. So:
if s → t is a legal jump, then complement(t) → complement(s) is one too.
The complement of "one peg in the centre" is the start. Therefore a position s after n jumps can still finish in the centre exactly when its complement is reachable in 31 − n jumps — one binary search in the sorted level. Complement commutes with the symmetries, so the representative's complement is canonicalised and looked up. That is also why the winnable column reads the same forwards and backwards.
The ledger
126 seconds, one process. Excerpt (all 32 rows are on the page):
| jumps | pegs | positions | up to symmetry | jump sequences | dead ends | still winnable |
|---|---|---|---|---|---|---|
| 0 | 32 | 1 | 1 | 1 | 0 | 1 |
| 4 | 28 | 296 | 39 | 400 | 0 | 292 |
| 8 | 24 | 77,559 | 9,751 | 2,076,744 | 0 | 49,236 |
| 12 | 20 | 4,138,302 | 517,854 | 18,687,793,880 | 0 | 902,056 |
| 15 | 17 | 20,773,236 | 2,598,215 | 13,794,351,556,920 | 40 | 1,841,556 |
| 16 | 16 | 26,482,824 | 3,312,423 | 112,576,101,214,496 | 176 | 1,841,556 |
| 17 | 15 | 28,994,876 | 3,626,632 | 857,945,953,884,624 | 302 | 1,639,652 |
| 20 | 12 | 15,425,572 | 1,930,324 | 222,984,258,240,522,544 | 6,890 | 546,308 |
| 24 | 8 | 800,152 | 100,565 | 56,487,846,008,148,393,896 | 33,051 | 16,628 |
| 28 | 4 | 2,529 | 348 | 287,520,477,058,517,555,304 | 1,295 | 60 |
| 30 | 2 | 32 | 7 | 16,301,649,363,425,363,800 | 28 | 4 |
| 31 | 1 | 5 | 2 | 81,723,294,080,159,936 | 5 | 1 |
- 187,636,299 reachable positions (23,475,688 up to symmetry); the widest level is 17 jumps with 28,994,876.
- Only 13,428,122 (7.16%) of them can still finish in the centre (1,679,072 up to symmetry).
- 162,352 dead ends in all; the earliest are 4 positions after 6 jumps, matching Wikipedia's "the shortest way to fail is in six moves".
- 40,861,647,040,079,968 jump sequences end with one peg in the centre. 10,215,411,760,019,992 end on the arm tip d1 — exactly a quarter. The only position one jump before "d1 alone" is d2 + d3; from there d2 over d3 lands in the centre and d3 over d2 lands on d1. The four ways into the centre are symmetric, so centre = 4 × d1.
The six OEIS sequences are baked into the script, which exits non-zero on any mismatch:
| OEIS | what | result |
|---|---|---|
| A335656 | positions after n jumps | ok (32 terms) |
| A112737 | the same, up to symmetry | ok (32 terms) |
| A350561 | jump sequences of length n | ok (23 terms) |
| A350998 | dead ends after n jumps | ok (32 terms) |
| A351286 | positions that can still finish in the centre | ok (32 terms) |
| A112738 | the same, up to symmetry | ok (32 terms) |
A350561 matches the 23 terms in its OEIS data field (up to 22 jumps). The script also prints the remaining 9 terms; I have not checked them against the b-file.
The 2.2% on Wikipedia
The English Wikipedia article says:
Note that the total number of reachable board positions (sum of the sequence) is 23,475,688, while the total number of possible board positions is 8,589,934,590 (33bit-1) (2^33), so only about 2.2% of all possible board positions can be reached starting with the center vacant.
23,475,688 is the sum of A112737, the count up to symmetry, and the ledger agrees. But 23,475,688 / 2^33 is 0.27%. The 2.2% comes from the unfolded count, 187,636,299 (the sum of A335656), which is 2.18% of 2^33. Since 2^33 counts unfolded configurations, the unfolded numerator is the right one, so the conclusion "about 2.2%" stands; the numerator printed next to it is the wrong one. (8,589,934,590 is also neither 2^33 = 8,589,934,592 nor 2^33 − 1.)
The solver
Solve is a depth-first search with three sound rungs — switching any of them off only makes it slower:
- Class test: different classes for the start and the requested lone peg → impossible, no search.
- Dead-position memo.
- Endgame table: from the target peg, reverse jumps (a peg at c jumps back over an empty b into an empty a, filling both) enumerate every position with at most K pegs that can still finish there. The forward search stops at K pegs and looks the answer up — meet in the middle. By the duality above, the number of k-peg entries in the centre's table is A335656(k − 1); a test checks it.
On the central games (budget 10,000,000 positions):
| board | rungs | result | positions | ms |
|---|---|---|---|---|
| english | class + memo + endgame | solved | 31 | 4,470 |
| english | class + memo | solved | 2,312 | 2 |
| english | memo only | solved | 2,312 | 2 |
| english | neither | solved | 20,275 | 31 |
| european | class + memo + endgame | class | 0 | 0 |
| european | class + memo | class | 0 | 0 |
| european | memo only | budget | 10,000,001 | 8,231 |
| european | neither | budget | 10,000,001 | 16,952 |
Single vacancies, and a mirror image that failed
I ran all 125 class-feasible English single-vacancy problems with 2,000,000 positions each and a 12-peg endgame table (problems that are symmetric images of each other are solved once and counted by class size). Trying jumps in board order solved 70. From the central start, of the four arm tips d1, a4, g4 and d7 — one problem, turned and reflected — it reached d7 but not d1, a4 or g4. When reflecting the board changes the answer, the budget is going into the first few choices.
So the solver now tries the move orders the eight symmetries induce (the same as searching each reflected board in board order), each with an eighth of the budget. The memo and the table are shared across orders: a dead position is dead in any order.
for (let g = 0; g < all.length && !found; g++) {
order = all[g];
out = false;
path.length = 0;
limit = nodes + share; // an eighth of the budget
found = dfs(lo, hi, pegs);
if (!found && !out) break; // exhausted within budget: no order helps
}
That solved 125 of 125 — every class-feasible English single-vacancy problem is solvable. On the European board, 16 of 64, 48 undecided. Asking for one peg anywhere on the European board, with 10 million positions:
| start | holes in class | result | positions | last peg |
|---|---|---|---|---|
| c1 | 8 | solved | 2,265,259 | b4 |
| d1 | 4 | class | 0 | — |
| b2 | 4 | class | 0 | — |
| c2 | 8 | class | 0 | — |
| d2 | 4 | budget | 10,000,008 | — |
| c3 | 4 | class | 0 | — |
| d3 | 4 | budget | 10,000,008 | — |
| d4 | 1 | class | 0 | — |
d2 and d3 have published solutions — replayed above — yet ten million positions of search did not find one. On the European board the search is still the weak part; what is solvable is settled by the class test and the published solutions.
The page
- Pick the board and the goal (centre or anywhere). Click a peg, then its landing hole. Undo, New game, and Edit start to add or remove pegs anywhere.
- The side panel shows pegs, legal jumps, the class (A, B) and the holes the last peg can still reach — the gold rings.
- Solve runs the eight-order search (10-peg table, 4 million positions) and replays the answer; it reports class impossibility, exhaustive failure or "undecided" honestly.
- The notes below the board hold the full 32-row ledger, the OEIS checks and the solver measurements.
Takeaways
- Put the invariant before the search. Sixteen classes, two-bit XORs, and the European central game and all three solvable European starts are settled in zero positions.
- Measure memory before you blame the hash. The 1.6 GB table was over 20× slower from paging; folding by the eight symmetries made it 200 MB and 126 s.
- Carry counts through a fold by multiplying by orbit size and dividing back. An inexact division is a free bug detector.
- Dualities delete searches. Reversal plus complement turns "can still win" into a lookup, and predicts the size of the endgame table.
- If a DFS answers differently on a mirror image, look at the move order. Eight symmetric orders took 70 solved problems to 125.
- Reproduce every published number before doubting one. Six OEIS sequences, the solution count, the five finishing holes, the six-move failure and the three European starts all matched; the one that did not, 2.2%, was a counting mix-up.
Every number here comes from the JSON written by npm run ledger and npm run stats; the page's notes render from the same files. 15 tests.
References:
- N. G. de Bruijn, "A solitaire game and its relation to a finite field", Journal of Recreational Mathematics 5 (1972)
- J. D. Beasley, The Ins and Outs of Peg Solitaire, Oxford University Press (1985)
- M. Brassine, "Découvrez... le solitaire", Jeux & Stratégie (December 1981)
- OEIS A335656, A112737, A350561, A350998, A351286, A112738
- Wikipedia, "Peg solitaire" (retrieved 26 September 2026)
Top comments (0)