Peg Game Advisor

It would be nice if our Peg Game application could keep the player from painting herself into a corner. Take the board to the right. The correct sequence of moves are: 7 to 9, 13 to 6, 10 to 3, and 1 to 6. If the player chooses 13 to 4 instead; then 7 can jump to 2, and 1 to 4. That would result in two pegs remaining: 4 and 10. So, our game needs to sound an alarm (e.g. draw a red dot) when the user asks for the 13 to 4 move.

Consider a strategy that uses a stack to record all possible moves. Solutions are found by: pushing all "possible moves" on the stack, popping the first entry off the stack, executing that move, testing if a single peg remains, if so - a solution was found, if not - repeat the process.

Consider the following first 2 moves ...

       

Here is a "tree" representation of "possible moves" ...

Here is an alternate representation that demonstrates four non-solutions. After 7 moves, the board has reached the state shown at the top. Four moves are now possible. If the 3-8 move is chosen, then two moves are possible. The 13-4 move eventually leads to three pegs remaining, and the 1-4 move leads to an end state of five pegs.

A graphical representation is optimal for carbon-based intelligence (i.e. people), but it doesn't map directly to silicon-based intelligence (computers). If we had a representation that was more sequential in nature (like a computer's memory), then we could perhaps kill two birds with one stone: discuss a solution strategy for the problem, and, lay the foundation for the eventual algorithm.

Another issue with the graphical representation above is overhead. Modeling all the possible moves of a game as separate nodes in a fully populated tree consumes a lot of memory. As we come up with a more sequential encoding of the game, is there a way we could accommodate some kind of "just in time" representation? The motivation is to maintain as little game state as possible.

Instead of building a full-grown tree, perhaps a step-by-step "list of lists" representation will provide sufficient bookkeepping for: testing one specific game, backtracking to alternate games, and ultimately testing every possible game. How about the following procedure and data structure?

  1. generate a list of all possible initial moves
  2. execute the last move on the list, and replace it with a new list of all currently possible moves
  3. go to step 2
Here is a representation for the sequence of moves: 6-1, 15-6, 8-3, 14-5, 2-9 The board now looks like -  

To eliminate some clutter, let's focus only on the last list of moves. The steps remain: move, generate, replace.

At this point, the pegs remaining are 1, 6, 11; and there are no more possible moves.

We've hit a dead-end, and need to backtrack to an alternate pathway. Lets add a new step 3 to our procedure.

  1. generate a list of all possible initial moves
  2. execute the last move on the list, and replace it with a new list of all currently possible moves
  3. when a solution or dead-end is reached, backtrack (undo and remove moves) until a parent list with an unused move is found
  4. go to step 2
In our example, we need to undo the 4-6 move, and backtrack to the parent list. That list has no more unused moves, so we must repeat the process by undoing the 14-5 move and backtracking. Again, there are no more unused moves in the parent list, so the 7-9 move is undone as well. Finally, we have found an unused move - 7 to 2.

The top line below looks like the fourth line above - except - the 7-9 move at the end has been removed. We are ready to proceed forward again. As each last move of the last list is executed, there is only one possible move on the board. So, each replacement is performed with a list composed of a single move.

We now have a "sequential" representation of our puzzle. It should give us a good start on a search algorithm. Notice how the list demonstrates last in, first out behavior.

Our 4-step procedure seems to suggest a loop where step 4 feeds back to step 2. Would recursion be preferable?

complete implementation