Introduction
For many years, Cracker Barrel⃝R restaurants have popularized peg solitaire played on a triangular board with 15 holes. Many patrons have puzzled over this game, often called “an IQ test”, which is surprisingly difficult given its small size and simple rules. Often people resort to a computer program to solve this puzzle, and it is a popular assignment in computer science classes [8, p. 132]. In this article we consider peg solitaire on a triangular board with n holes on each side. This board will be referred to as Tn and can be conveniently presented on an array of hexagons (Figure 1). The board Tn has T (n) = n(n + 1)/2 holes, where T (n) is the nth triangular number. The Cracker Barrel⃝R board is T5.
We will use two different notations to identify the holes in the board. The notation in Figure 1a is useful for quick hole identification and for describing solutions. The “skew Cartesian coordinate” notation [10] in Figure 1b is useful for the theory of the game, as well as inside computer programs. It is also particularly easy to perform reflections and rotations