Peg Solitaire

Peg solitaire is played alone, against the board. Thirty-three holes form a cross; every hole but the centre holds a peg. A move jumps one peg orthogonally over a neighbour into the empty hole beyond, removing the peg jumped. The classic challenge is to finish with a single peg standing in the centre, and it can be done. The harder question is which finishes are possible at all, and that is where integer programming earns an unusual keep: not by finding a solution, but by proving that none exists. The tool is a deliberately loosened version of the game, unconstrained solitaire, proposed by Beasley and modelled as an integer program by Chlond in the INFORMS Transactions on Education column, and the relaxation turns out to be exactly sharp enough to settle the finishing question.

The relaxation

A full account of a game of solitaire would track the board after every jump, a hard combinatorial object. The unconstrained model throws almost all of that away and keeps only a bookkeeping identity. Forget the order of the moves; forget even the rule that a hole holds zero or one peg, and let the count in a hole run to any integer during play. Then a whole game is described by nothing but how many times each possible jump is used, and the only thing that must balance is the net change in each hole.

Every jump does the same three things: it empties the hole it starts from, empties the hole it leaps over, and fills the hole it lands in. So a jump changes the peg total by $-1 -1 +1 = -1$, always. Reaching one peg from the thirty-two of the opening therefore takes exactly thirty-one jumps, no matter how they are arranged, in this relaxation and in the real game alike.

The model

Variables

For each legal jump $m$, a colinear triple of holes $(A, B, C)$ with $A$ the start, $B$ the peg jumped, and $C$ the landing hole, let $n_m \ge 0$ be an integer counting how many times that jump is made. There are seventy-six such directed jumps on the board: four directions from each location, less those that would run off the edge. Counting jumps rather than tracking the board is what keeps the algebra short; Chlond, finding an elegant algebraic model elusive, solved the puzzle on a spreadsheet and invited readers to send formulations of their own.

Constraints

Let $\delta_m(h)$ be the effect of jump $m$ on hole $h$: $+1$ if $h = C$, $-1$ if $h \in \{A, B\}$, and $0$ otherwise. If the game begins with hole $e$ empty and every other hole full, and is to end with a single peg at hole $t$, the net balance at every hole is fixed: $$\big[h \neq e\big] \;+\; \sum_{m} \delta_m(h)\, n_m \;=\; \big[h = t\big] \qquad \text{for every hole } h .$$ The left side is the starting peg count at $h$ plus everything the jumps add or remove there; the right side is the target. There is no objective. If this system has a nonnegative integer solution, the target survives a necessary condition; if it has none, the target is unreachable, and the solver’s infeasibility is the proof.

The solver

from ortools.sat.python import cp_model

def on_board(r, c):
    return 0 <= r <= 6 and 0 <= c <= 6 and not ((r < 2 or r > 4) and (c < 2 or c > 4))

def moves(holes):
    out = []
    for (r, c) in holes:
        for dr, dc in ((0, 1), (0, -1), (1, 0), (-1, 0)):
            B, C = (r + dr, c + dc), (r + 2 * dr, c + 2 * dc)
            if on_board(*B) and on_board(*C):
                out.append(((r, c), B, C))
    return out

def reachable(start_empty, finish):
    holes = [(r, c) for r in range(7) for c in range(7) if on_board(r, c)]
    mv = moves(holes)
    m = cp_model.CpModel()
    n = [m.NewIntVar(0, 99, "") for _ in mv]
    for h in holes:
        net = sum(n[i] * ((h == C) - (h in (A, B)))
                  for i, (A, B, C) in enumerate(mv))
        m.Add((0 if h == start_empty else 1) + net == (1 if h == finish else 0))
    s = cp_model.CpSolver()
    return s.Solve(m) in (cp_model.OPTIMAL, cp_model.FEASIBLE)

What the relaxation knows

Start with the centre empty and ask, hole by hole, where a single peg may finish. The relaxation answers the same for the whole board at once: of the thirty-three holes, exactly five survive, the centre and the four tips of the arms, drawn in copper in Figure 25.1. The other twenty-eight are infeasible, which is to say impossible: no sequence of jumps, however clever, can leave the last peg there. You cannot, for instance, finish one hole away from the centre.

The five survivors are precisely the holes whose row and column are both divisible by three. The model was told nothing of divisibility; it was given only the geometry of the jumps, and the arithmetic fell out of the balance equations. This is the classical rule of three for the board, recovered by a generic integer program, where by hand it takes a clever choice of two three-colourings to see it.

Necessary, not sufficient

A word of honesty about what has been proved. The relaxation discards the rule that a hole never holds more than one peg and the order in which jumps happen, so a feasible move count is only a necessary condition: it does not guarantee a real game realises it. For the five survivors the condition turns out to be tight, the centre finish being the classic solved game, but that tightness is a fact about this board, not a gift of the method. The method’s real power runs the other way. A relaxation can only enlarge the set of feasible answers, so anything it rules out is ruled out for good. That is why an infeasible relaxation is a genuine impossibility proof, and why loosening a problem, counter to instinct, is sometimes the fastest way to show something cannot be done.

Sources. The unconstrained game is due to John D. Beasley, who proposed allowing any integer number of pegs in a hole; the integer-programming treatment, with one move-count variable per direction at each location, follows Martin J. Chlond, Unconstrained Peg Solitaire, INFORMS Transactions on Education volume $2$, number $3$ ($2002$), pages $99$–$100$, who notes the algebra is cumbersome and invites algebraic formulations. That a lone surviving peg from the central opening can rest only where row and column are both multiples of three is the classical rule of three for square-lattice solitaire; the canonical account of the theory, including the resource counts and colourings behind it, is John D. Beasley, The Ins and Outs of Peg Solitaire (Oxford University Press, $1985$). The five-hole result reported here is computed from the model and agrees with that theory.