Differences

This shows you the differences between two versions of the page.

--- projects:peg_puzzle [2020/02/09 21:41] – created josh
+++ projects:peg_puzzle [2020/02/09 22:03] (current) – josh
@@ Line 1: / Line 1: @@
 ====== Peg Puzzle ======
-This project involves writing a computer program to solve the "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