Holtrop Wiki

This page is read only. You can view the source, but not change it. Ask your administrator if you think this is wrong.
====== Peg Puzzle ======

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

{{:projects:peg_puzzle:peg_puzzle.jpeg?direct&400|}}

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