= Peg solitaire
Peg solitaire is a one-player finite board puzzle in which a peg jumps over an adjacent peg into an empty hole, and the jumped peg is removed. In a standard orthogonal version, the three holes must lie consecutively in one row or column. Board shape, initial occupied holes and the desired final configuration are part of the problem specification.
Every move decreases the number of pegs by exactly one, so a play starting with $n$ pegs has at most $n-1$ moves if at least one peg remains. A solution reducing to a single peg must have exactly $n-1$ moves. This is a counting necessity, not a guarantee of solvability.
The puzzle illustrates <state-space search>: a position is a subset of occupied holes, and directed edges are legal jumps. Backtracking explores possible continuations, while board symmetries can identify equivalent states. Algebraic invariants and monotone weight functions can prove some target configurations unreachable without enumerating every play.
Back to article page
