Jon Lathem

Cracker Barrel VS Python

Date:     11.Aug.2008
Categories:      Python,
Comment:     2 comments

Let be the first to admit. I am an ignoramoose. I enjoy going to the Cracker Barrel for a good dinner of Chicken and Dumplings. Every time I go, I have to try the peg game that is on every table and almost every time that small little wooden triangle calls me an ignoramoose.

So since I am tired of being put down by block of wood I thought to my self... How could I algorithmically solve such a puzzle. At first thought there are 15 places for a peg to be; that means there is 32,768 possible configurations that the board can be in. That number is small enough for a computer to brute force solve the problem by arranging all the possible boards into a tree structure where the root of the tree is the board with only one peg missing and the leaves of the tree are are boards where there are no more possible moves. Each child node in the tree would be a valid "Jump" applied to its parent. The paths that start at the root of the tree and go down to a leaf that have a length of 13 (there is 14 pegs to start with because one of the holes is empty and you have to leave one peg so 14 - 1 = 13)is a valid solution to the puzzle.

Since we are not interested in all possible solutions just one that works this method would be a over kill. A slightly more efficient approach would be start with the root node and build our tree in a depth first manner until we get a branch in the tree that solves the problem. That is to say we will start with a board with only one peg missing, make a move, keep making moves until we either get stuck or solve the puzzle. If we get stuck undo the moves we made until we are at a spot where we could make another move. When we have back tracked to a spot where we had a choice, we will pick a different move then the one we picked previously. We will continue you on in this manner until the puzzle is solved. When the puzzle is solved we can just go up the tree to find the right sequence of moves that solve the puzzle.

Now comes the issue of translating this algorithm into Python code. First I want to start off by creating a class call PegBoard that will represent a configuration of the pegs. We will do this by using a 2D array of ints where 0 represents an open place, 1 represents a peg, and anything less then one and invalid spot of the board (I know i could have made a jagged array but that makes things ugly in my opnion). My class looks something like this:
class PegBoard:
   def __init__(self, pegBoard=None):
      if pegBoard:
         self.parent=pegBoard
         self.board=copy.deepcopy(pegBoard.board)
      else:
         self.parent=None
         self.board = [[1,          -8, -8, -8, -8],
             [1, 1,          -8, -8, -8],
             [1, 1, 1,          -8, -8],
             [1, 1, 1, 1,          -8],
             [0, 1, 1, 1, 1]          ]


   def createPossibles(self):
      . . .
      #Return list of all possible boards
      . . .

   def printBoard(self):
      . . .
      . . .
      
   def isWin(self):
      score=0
      for x in range (len(self.board)):
         for y in range(len (self.board[x])):
            if self.board[x][y]<1:
               continue
            score+=1
      return score==1

I choose not to write out the createPossibles function because it is very long and boring but be content with that basis of the function is loop over ever peg and see if there is a jump. If there is a jump make a copy of the board, make the jump on the copied board, and append the new board to a list, after checking every peg return the list.

Now that we have our Peg Board we can use the following algorithm to solve the puzzle:
stack = [PegBoard()]
is_winner=False
while len(stack)>0 and not is_winner:
   p = stack.pop();
   stack.extend (p.createPossibles())
   for p in stack:
      if p.isWin():
         print "FOUND ONE"
         stack=[]
         while p:
            stack.append(p)
            p=p.parent
         stack.reverse()
         for p in stack:
            p.printBoard()
         is_winner=True
         break
if not is_winner:
   print "DID NOT FIND ONE"

You maybe thinking "Where is my tree? You promised me a tree and I don't see one". You are partly right in that accusation. We are making a very witty use of a stack to simulate a tree here. We are pushing on the newest possible solutions to the top of the stack. These solutions are currently the deepest leaves on the tree. When we get stuck we remove the top element on the stack which will give us the next possible board that we can start from. If the stack becomes empty and no solution is found then there is no possible solution. This is confusing at first look if you aren't used to stacks as trees.

I will note that this is not the most efficient algorithm by a long shot. For starters its possible two different paths lead to the same dead end. We could record paths to dead ends and when we start down that patch stop then since we know there is no solution at the end of the path. Another optimization would be ignore isomorphic boards that have already been checked. I am calling two boards isomorphic if you could get one board from the other just by rotating the triangle. That is to say, the board with just the top peg missing is really the same as the board the the bottom right peg missing because you could rotate the triangle 60 degrees counter clockwise and get the same board. This puzzle lends its self to be solved by dynamic programming. (My algorithm works fine in this case because there are such few possibilities but as the board got bigger you would need to rework the algorithm to use more dynamic programming techniques).

For the history and other peg games that go far beyond the cracker barrel check out this Wikipedia page:http://en.wikipedia.org/wiki/Peg_solitaire

To try out the code you can use this simple web page here