This project involves writing a computer program to solve the “peg puzzle”, which is a puzzle something like this:

In this puzzle, you start with pegs in each hole of the board except for one. Each turn, you can move a peg in a straight line over exactly one other peg to land in a hole, and then remove the peg that was jumped over. The goal is to end with only one peg remaining, and in particular, to end with that one remaining peg in a particular location.

The puzzle could in theory have different sizes. We will denote puzzle size by N to represent the number of rows. For example, for the above puzzle, N = 5.

In order to represent the state of the puzzle, we can define a State class to capture the puzzle state. We shall store in this state a two-dimensional array of flags for whether there is a peg present in a given location of the puzzle. For example, assuming the puzzle starts out with pegs in each hole except the top hole, we have a state that looks like:

There are six possible movement directions:

• up-left, corresponding to NW in our 2D array
• up-right, corresponding to N in our 2D array
• left, corresponding to W in our 2D array
• right, corresponding to E in our 2D array
• down-left, corresponding to S in our 2D array
• down-right, corresponding to SE in our 2D array

A peg position is valid iff:

• row >= 0 and
• row < N and
• col >= 0 and
• col <= row

We can first write a brute-force algorithm to look for all solutions to the puzzle following an algorithm something like this:

1. for each peg present:
   1. for each movement direction:
      1. if movement in this direction is valid:
         1. perform and record the move
         2. recurse on the new board state
2. if movement of no peg was possible:
   1. record the game

This will evaluate every possible game.

If we are looking for solutions that end in a particular end state, we can also use a reverse algorithm starting with a desired ending board state (for example, one peg left in the top position):

1. for each hole present:
   1. for each movement direction:
      1. if movement from that direction could have happened:
         1. perform and record the move
         2. recurse on the new board state