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
Solution-Finding Methods
Forward Brute-Force
We can first write a brute-force algorithm to look for all solutions to the puzzle following an algorithm something like this:
- for each peg present:
- for each movement direction:
- if movement in this direction is valid:
- perform and record the move
- recurse on the new board state
- if movement of no peg was possible:
- record the game
This will evaluate every possible game.
Reverse Brute-Force
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):
- for each hole present:
- for each movement direction:
- if movement from that direction could have happened:
- perform and record the move
- recurse on the new board state