Peg Solitaire is a puzzle game for one person. It is played with a board containing a number of holes each of which can accommodate a single peg. The game begins as depicted below with all holes except the central hole containing a peg.

The player must move from this starting configuration to the target position using only legal moves. The target position in the standard game consists of an empty board except for a single peg in the central hole. A legal move consists of a jump by a peg taken from an occupied hole over a single adjacent occupied hole and into an unoccupied hole. The peg jumped over is removed from the board.

A Java applet to play the Solitaire with a number of alternative starting configurations is available here .

The game has a long history and been popular for many years but most people are familiar only with the standard game and are unaware of the many variations and modifications and the rich underlying mathematical theory. The Ins and Outs of Peg Solitaire by John D.Beasley (Oxford University Press, 1992) is a book that aims to rectify this situation. Beasley brings together in one place a thorough survey of the mathematical results known at the time of writing and presents analyses and discussion of a host of closely related puzzles.

One interesting modification proposed by Beasley is Unconstrained Peg Solitaire in which any integer number of pegs, positive, negative, or zero are allowed in each hole. It is not necessary therefore for moves to originate from occupied holes or to terminate in unoccupied holes. A typical sequence of moves beginning with four adjacent pegs may be represented as follows:

In this sequence a peg is transferred from position two to position four and back again and finally a peg is transferred from position one to position three. At each move we reduce the peg count in the intermediate position by on unit.

The objective of the game as with standard solitaire is to move from a starting configuration to a target position, if possible, using only legal moves. A Java applet to familiarise the reader with the game is available here .

The order in which a winning set of moves is carried out does not matter in the unconstrained game and the problem of finding a solution may be formulated as an integer program. Four sets of integer variables are defined, that is, the number of northerly, southerly, easterly and westerly moves to be made from each location on the board. Constraints are needed to ensure that no moves terminate off the board and to ensure that the required target position is consistent with the initial configuration and the moves constituting a solution. Since each move reduces the total peg count by one unit the solution must be reached in exactly n-p moves where n is the peg count in the initial configuration and p is the peg count in the target position. An Excel spreadsheet implementation of an IP model may be downloaded here.

An elegant model of this puzzle proves to be elusive due to the awkward shape of the board and the IP formulation using mathematical notation is cumbersome. In fact, this is one of the few problems the author has come across where a spreadsheet approach seems to be more convenient than a modeling language. Readers who disagree with this are invited to submit their own algebraic formulations.

Beasley also considers Fractional Unconstrained Solitaire in which fractional moves are allowed and holes may contain fractional numbers of pegs. This is clearly a linear program since the decision variables no longer need to be integer valued.

^ã INFORMS