Extended Exercise: Board Solitaire

Peg Solitaire is a board game for individuals. The board comes in various shapes. Here is the simplest one:

The circle without a black dot represents an unoccupied hole; the other circles are holes containing little pegs.

The goal of the game is to eliminate the pegs one by one, until only one peg is left. A player can eliminate a peg if one of the neighboring holes is unoccupied and if there is a peg in the hole in the opposite direction. In that case, the second peg can jump over the first one and the first one is eliminated. Consider the following configuration:

Here the pegs labeled 1 and 2 could jump. If the player decides to move the peg labeled 2, the next configuration is

Some configurations are dead-ends. For a simple example, consider the first board configuration. Its hole is in the middle of the board. Hence no peg can jump, because there are no two pegs in a row, column, or diagonal such that one can jump over the other into the hole. A player who discovers a dead-end configuration must stop or backtrack by undoing moves and trying alternatives.

More Uses of Accumulation

Exercise 32.3.1

Develop a representation for triangular Solitaire boards.

Develop a data representation for peg moves. Pegs can move along a row, a column, and a diagonal.

Hints: (1) There are at least four rows, because it is impossible to play the game with three or fewer. Still, develop the data definition independently of such constraints. (2) Translate our examples from above into the chosen data representations. Solution

Exercise 32.3.2

Develop a function that, given a board and the board position of a peg, determines whether or not the peg can jump. We call such a peg enabled.

Develop a function that, given a board and the board position of an enabled peg, creates a board that represents the next configuration. Solution

Exercise 32.3.3

Develop the function solitaire, which solves a Solitaire problem for different sizes of the equilateral triangle. The function should consume a the board. It produces false, if the given problem is not solvable. Otherwise, it should produce a list of moves that specifies in what order the pegs must be moved to solve the given Solitaire problem.

Formulate the tests for all functions as boolean-valued expressions. Solution