Depth First Search

Program - Solving Teaser Using Depth First Search.
Your next program will use depth first search to solve the "teaser" puzzle.
Before attempting this program first acquire a good understanding of state space search and its terminology.

Depth first search is a type of state space search that searches the state space search tree by proceeding down one branch of the tree until a solution state or a dead end state (i.e., no more moves are possible from that state) is encountered. When a dead-end state is encountered depth first search then backs up to the last decision it made and makes another choice of which direction to pursue downward in the search tree.

Teaser is a puzzle consisting of a triangular board with 15 holes. The holes are arranged in rows so that the 1st row contains 1 hole, the 2nd row 2 holes ... and the 5th row contains 5 holes.

In the puzzle's starting configuration (state) all of the holes but one contain pegs. The puzzle is played by jumping one peg over another into an open peg as one would jump in playing a game of checkers, removing the jumped-over piece. The object of the game is to remove all but one peg with legal moves. For the purpose of this description the words node, state and configuration will be used interchangeably.
We will number the holes as follows.

                    0
                1      2
             3      4      5
          6     7      8      9
       10   11     12     13   14

So, for example, if we have pegs in holes 0 and 2 and hole 5 is empty then we can jump the peg in hole 0 over the peg in hole 2 into hole 5, removing the peg in hole 2. Thus, we would have reduced the number of pegs by 1. Obviously, 13 moves will remove 13 pegs leaving only one of the original 14.

Because we know the depth at which the answer lies in the search tree, depth-first search is an excellent choice among the various state space search algorithms for solving this puzzle.

Depth first search has several variations. The best one to use depends upon several factors. For brevity we will focus mostly on the teaser puzzle, making easy-to-implement generalities where appropriate.

Some Program Internals
The algorithm maintains two lists.

the open list and
the closed list

The open list contains nodes that are the result of moves we have considered but whose successor (child) nodes have not been generated. The closed list contains nodes whose successor nodes have been generated. In addition to saving the node configuration itself on these lists we also save the parent of the node so that we can trace our moves back to the start node once a goal node is encountered (i.e., a solution is found). In depth first search the open list is normally implemented as a stack.

Due to the simplicity of teaser we can utilize data structures that might not be appropriate for more complex puzzles. For example, since the puzzle board has only 15 holes a puzzle configuration can be stored in a single 16 bit integer. Also, since there are only 2¹⁵ possible puzzle configurations, information about each can be stored in an array of size 2¹⁵. This makes searching for a node in a list quite simple. I.e., we do not actually have to search through a list for information about the node, we may simply look up the information at the appropriate index in the array.

You may wish to use the hints/template for the program I have provided. Here is a working version (.exe) of the program.

Program Requirements
Basically, the program should do the following:

Initialize necessary data structures.
Explain the puzzle and display the puzzle board with holes numbered.
Ask the user for the starting configuration (normally which hole contains no peg).
Use depth first search to find a solution if one exists.
If a solution is found then display it
else report that no solution exists.

Efficiency Measure
You may wish to keep track of and display the number of nodes that have been expanded in finding a solution and display that number when the search has terminated. This is a measure of the efficiency of the algorithm. Of course timing the run is also a very important efficiency measure.

Enhancements
There are many opportunities for enhancements to this program. Here are a few

Allow arbitrary configurations for the start state without compromising the convenience of specifying a single hole as the normal start state.
Allow arbitrary configurations for the goal state(s). For example, one might specify that the final peg must be left in a specific hole.
Display puzzle configurations graphically; i.e., in some form other than a crude text format.
Find all (not just one) solutions for a given start state.
Order the children of a given node when placing them on the open list so that the most promising children are placed last (hence retrieved first) to reduce the number of nodes examined.

Top of this page Top of page

Home page