xl. Peg Solitaire

Problem. The English board has 33 holes in a cross shape, all filled with pegs except the centre. A move jumps a peg over an orthogonally adjacent peg into an empty hole, removing the jumped peg. Leave a single peg, in the centre.

    o o o
    o o o
o o o o o o o
o o o . o o o
o o o o o o o
    o o o
    o o o

Fact	Value
English board, centre start	solvable, 31 jumps; the last peg can only end at the centre or at the 4 holes $(0,3),(3,0),(3,6),(6,3)$ (rule of three)
French board (37 holes), centre start	impossible to reduce to one peg anywhere (rule of three)
search effort, English centre start	the memoized search below finds the centre finish after about $10^3$ dead positions and the off-centre finishes after about $7\cdot 10^6$ (a few seconds each)
general boards	deciding solvability is NP-complete (Uehara and Iwata, 1990)
other invariants	Conway’s pagoda functions: weights $w$ with $w(a)+w(b)\ge w(c)$ for every jump $a$ over $b$ into $c$; the total weight never increases

Rule of three. Colour hole $(i,j)$ by $(i+j)\mathrm{mod}3$. A jump involves three consecutive holes in a line, one of each colour: two colour counts drop by one and one rises by one, so all three counts flip parity. Hence the parities of the pairwise sums of counts are invariant. Do the same with $(i-j)\mathrm{mod}3$: four invariant bits in total.

// Peg solitaire on an R x C grid; shape[i][j] != ' ' marks a hole. Positions are bitmasks of pegs (R * C <= 64).
struct PegSolitaire {
    int R, C; vector<array<int, 3>> jumps;                   // (from, over, to)
    unordered_set<ull> dead; vector<array<int, 3>> sol;
    PegSolitaire(const vector<string>& shape) : R(sz(shape)), C(sz(shape[0])) {
        auto on = [&](int i, int j) { return i >= 0 && i < R && j >= 0 && j < C && shape[i][j] != ' '; };
        for (int i = 0; i < R; i++) for (int j = 0; j < C; j++) for (auto [di, dj] : {pair{0, 1}, {0, -1}, {1, 0}, {-1, 0}})
            if (on(i, j) && on(i + di, j + dj) && on(i + 2 * di, j + 2 * dj))
                jumps.push_back({i * C + j, (i + di) * C + j + dj, (i + 2 * di) * C + j + 2 * dj});
    }
    int signature(ull s) const {                             // rule of three: 4 invariant bits
        int p[2][3] = {};
        for (int x = 0; x < R * C; x++) if (s >> x & 1) { int i = x / C, j = x % C; p[0][(i + j) % 3] ^= 1; p[1][((i - j) % 3 + 3) % 3] ^= 1; }
        return (p[0][0] ^ p[0][1]) | (p[0][0] ^ p[0][2]) << 1 | (p[1][0] ^ p[1][1]) << 2 | (p[1][0] ^ p[1][2]) << 3;
    }
    bool solve(ull s, ull goal) {                            // fills sol with the jumps; memoizes dead positions
        if (s == goal) return true;
        if (__builtin_popcountll(s) <= __builtin_popcountll(goal) || dead.count(s)) return false;
        for (auto& [a, b, c] : jumps) if ((s >> a & 1) && (s >> b & 1) && !(s >> c & 1)) {
            sol.push_back({a, b, c});
            if (solve(s ^ (1ULL << a) ^ (1ULL << b) ^ (1ULL << c), goal)) return true;
            sol.pop_back();
        }
        dead.insert(s);
        return false;
    }
};

Usage: build the English shape, start = all holes but the centre, goal = only the centre; first check signature(start) == signature(goal) (necessary), then solve.

Proof: the rule of three, the five end holes, and the French board

Invariant. A jump uses holes $a,b,c$ consecutive in a row or column, so $i+j$ takes three consecutive values on them: one of each residue mod 3, and likewise $i-j$. Pegs at $a,b$ disappear and one appears at $c$: each of the three counts changes by $\pm 1$ and flips parity. Then $n_0+n_1$, $n_0+n_2$ keep their parities, which are the bits returned by signature (for both colourings). Two positions with different signatures are not connected by jumps.

End holes. A single peg at $(i,j)$ has the signature of the one-hot vectors at $(i+j)\mathrm{mod}3$ and $(i-j)\mathrm{mod}3$. For the English centre start the signature equals that of a single peg at the centre $(3,3)$ (computed), so the last peg must satisfy $i+j\equiv 0$ and $i-j\equiv 0(\mathrm{mod}3)$, i.e. $i\equiv j\equiv 0(\mathrm{mod}3)$; on the board that leaves $(3,3)$, $(0,3)$, $(3,0)$, $(3,6)$, $(6,3)$. The search finds a solution for each of the five, so all are attainable.

French board. For the 37-hole board with the centre empty, the computed signature differs from that of every single peg, so no sequence of jumps leaves one peg anywhere.

Search. solve explores every legal jump sequence from s except that it skips positions already proved dead (from which every continuation fails); the memo is sound because whether a position can reach goal depends only on the position. Tested against an unmemoized exhaustive search on small rectangular boards, and every returned sequence was replayed to check legality.

Related notes

• Backtracking and Pruning
• Parity, Coloring and Mod Observations
• Invariants, Parity and Extremal Arguments