This is an old revision of the document!
Table of Contents
Peg Puzzle
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.
State
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:
| 0 | 1 | 2 | 3 | 4 | |
|---|---|---|---|---|---|
| 0 | 0 | ||||
| 1 | 1 | 1 | |||
| 2 | 1 | 1 | 1 | ||
| 3 | 1 | 1 | 1 | 1 | |
| 4 | 1 | 1 | 1 | 1 | 1 |
Movement Directions
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
Valid Peg Positions
A peg position is valid iff:
- row >= 0 and
- row < N and
- col >= 0 and
- col <= row