When I was but a little tyke, my grandmother bought me a puzzle
to play with that I've held onto ever since. If you've eaten at
a Cracker Barrel restaurant, you may recognize it. The puzzle
consisted of a triangle-shaped slab of wood with fifteen holes
drilled into it like so (the "O"s are the holes, of course):
/ \
/ \
/ O \
/ \
/ O O \
/ \
/ O O O \
/ \
/ O O O O \
/ \
/ O O O O O \
/_______________________\
The puzzle also came with 14 plastic pegs, which I then inserted
into any 14 of the 15 holes, like so (the "X"s represent pegs
in holes):
/ \
/ \
/ O \
/ \
/ X X \
/ \
/ X X X \
/ \
/ X X X X \
/ \
/ X X X X X \
/_______________________\
The challenge then was to remove all the pegs but one from the triangle
according to the following rules:
A peg can jump over any adjacent peg to occupy an empty hole on
the other side of the peg that was jumped.
A peg that has been jumped is removed from the board.
A peg must jump another peg to move; you can't just move a peg from
one hole to an adjacent hole.
So, given the starting board above, I might choose the following
jump as my next move:
/ \
/ \
/ X \ {--- this peg jumped from here -
/ \ |
/ X O \ {- this peg was removed |
/ \ |
/ X X O \ -----------------------------
/ \
/ X X X X \
/ \
/ X X X X X \
/_______________________\
and my next jump might result in this layout:
/ \
/ \
/ X \
/ \
/ X O \
/ \
/ O O X \
/ \
/ X X X X \
/ \
/ X X X X X \
/_______________________\
If I started with the right initial arrangement of pegs and I made
the right jumps in the right order, I might end up with one peg
and fourteen holes, in which case I was classified as a "genius",
or so it was printed on the piece of wood. If I left two pegs,
I was "above average", and if I left three pegs on the board I was
a "mental midget". Just call me "Shorty".
Anyway, let's take another look at solving this peg puzzle, but
this time from the perspective of a state-space search. The initial
state in the state space is any configuration of fourteen pegs and
one empty hole on the triangle-shaped board. The goal state is
any configuration of one peg and fourteen holes which can be
obtained through the correct application of the operators.
One way to look at the operators is that there are effectively six
of them. Any peg is adjacent to at most six other pegs, and that
peg could jump a peg in any of those six different directions so
long as there's an empty hole on the other side of the peg being
jumped. (Pegs cannot however jump off the board.) As part of the
operator, the peg that was jumped over is removed from the board.
Your assignment is to write a program called PEG-PUZZLE which employs a
depth-first state space search to try to solve this puzzle with any legal
initial state. PEG-PUZZLE takes two arguments. The first is a
description of the initial state as a list of five sublists, with
each sublist corresponding to a row on the board. Thus, the initial
state that looks like this:
/ \
/ \
/ O \
/ \
/ X X \
/ \
/ X X X \
/ \
/ X X X X \
/ \
/ X X X X X \
/_______________________\
is represented by a list of lists that looks like this:
((o) (x x) (x x x) (x x x x) (x x x x x))
You can assume that the left-to-right ordering of elements of a
sublist corresponds to the left-to-right ordering of pegs and
holes in a given row.
If you pretty-print this list, it will look more like the pictures
above:
((o)
(x x)
(x x x)
(x x x x)
(x x x x x))
but not quite.
We don't need to pass the goal state, as it will always be the same regardless
of the initial state. The goal state will always be any legally-obtained
configuration of one peg and fourteen holes.
The second argument is either #f or #t. If the value is #t (or not
#f), your program should print on the screen a trace of the sequence of
states or moves being tried as the search progresses. The trace should also
point out where the program runs into a dead end and has to backtrack, as
well as pointing out when the goal has been reached. If the second argument
is #f, no trace should be printed. (You'll want to look up some of the
input/output stuff to make this pretty. Your TAs will undoubtedly provide
some appropriate code for printing that you can just plug into your program.)
When (if?) the goal has been reached, PEG-PUZZLE should terminate and return a
list of successive states that constitutes the path from the initial state to
the goal state. So, if your TA invokes PEG-PUZZLE in this way:
> (peg-puzzle '((o) (x x) (x x x) (x x x x) (x x x x x)) #f)
your program should return something like this (although not necessarily
exactly this) if your grader pretty-printed it:
(((o)
(x x)
(x x x)
(x x x x)
(x x x x x))
((x)
(x o)
(x x o)
(x x x x)
(x x x x x))
((x)
(x o)
(o o x)
(x x x x)
(x x x x x))
:
: [ the rest of the states would go in here]
:
((o)
(o o)
(o o o)
(o o o o)
(o o o o x)))
Note that every move of a peg involves jumping another which in turn
causes that peg that was jumped over to be removed. Thus, every move
removes a peg and adds a hole. If you start with fourteen pegs and
end with one peg, then the list of states returned by PEG-PUZZLE
will contain exactly fourteen states. The first state will have
fourteen pegs, the second state has thirteen pegs, the third state
will have twelve pegs, and so on until the fourteenth and last state
which has only one peg.
Your program may find a different path because your program may apply its
operators in a different order than the hypothetical program above does.
Also, I haven't verified that the start state given in the above example
will actually lead to the desired goal state; what's given above is
merely intended as an example of what the list that PEG-PUZZLE returns
should look like if it does find a goal state of one peg and fourteen holes.
If the goal state can't be reached from the initial state, PEG-PUZZLE should
just return #f.
If you wish, you can convert my representation for the PEG-PUZZLE into
any other representation of your choice if you think that would make your life
easier. I make no claim that the representation I'm using above for passing
the start state to your program is necessarily a great representation to
use in solving the problem. It just happens to be convenient for representing
the start state. So like I said, if you think things might go easier for
you if you use a different representation, please feel free to do so.
However, you still have to deal with my representation as input to
your function as specified above. Furthermore, you'll need to convert your
representation to my representation in order to return the path from the
initial state to the goal state in the correct (i.e., my) format.
If you want to work as part of a two-person team in preparation for the
next homework assignment, that's ok with me.
Last revised: November 4, 2003