Jake Pusateri
If you’ve ever been to a Cracker Barrel restaurant, you’ve probably played this game: Cracker Barrel Peg Game.
Rules
If you haven’t played it before, the rules are fairly straightforward.
- There are 14 pegs that are placed in a triangle made of 15 holes.
- One hole is open at the beginning of every game.
- The choice of this hole is up to the player.
- The goal of the game is to eliminate all but 1 peg from play.
- Pegs can be elimated by jumping one peg over another.
- A jump consists of picking up on peg, moving over another peg, and placing it down in an empty hole. The jumped peg is then removed from the board.
Even with these simple rules and my many visits to Cracker Barrel, I hadn’t ever solved it down to one. So let’s see if we can write a program to solve it for us. Is such a thing possible? Let’s consider the number of possible game states. A hole can be occupied or not and there are 15 holes for 215 states. For a computer, that’s practically nothing. This means no fancy puzzle-solving or constraint techniques are probably going to be needed.
Algorithm
The simplest way to solve the game would be to make a valid move, then make another valid move, and keep going until there aren’t any moves left. If you then have one peg left then you have won. If you have no moves left but haven’t won, undo the move you just made and try a different one. If you’ve tried all moves and not found a solution, then one must not exist. This algorithm is essentially Depth First Search. Since you want to be able to reproduce your success and show off to your friends, you also might want to keep track of the moves you have made on the way to the solution.
Does this produce the optimal solution? Maybe the first solution found isn’t the shortest. As it turns out, every solution is exactly 13 moves, since 1 peg is removed each time and there are 14 pegs to begin. Therefore, the first solution found is just as good as any other in terms of length.
Representation
In order to identify each hole, I chose to start at 0 and increase left to right, top to bottom to 14.
0
1 2
3 4 5
6 7 8 9
10 11 12 13 14
Implementation
To implement this solution, we’ll need a list of all possible jumps on the board. I’m choosing Python to solve this in, so each jump will be represented by a 3-tuple. The first number is the source hole, the second is the jumped hole, and the last number is the destination hole. Game state can be represented by a set of occupied pegs. A list is used to keep track of moves made to get to the state the board is in. Wrapping that all in a class gives to following code:
class Triangle5(object):
def __init__(self, missing):
# source, jumped, destination
self.jumps = [(0,1,3),
(0,2,5),
(1,3,6),
(1,4,8),
(2,4,7),
(2,5,9),
(3,1,0),
(3,4,5),
(3,6,10),
(3,7,12),
(4,7,11),
(4,8,13),
(5,4,3),
(5,8,12),
(5,9,14),
(6,3,1),
(6,7,8),
(7,4,2),
(7,8,9),
(8,4,1),
(8,7,6),
(9,5,2),
(9,8,7),
(10,6,3),
(10,11,12),
(11,7,4),
(11,12,13),
(12,7,3),
(12,8,5),
(12,11,10),
(12,13,14),
(13,8,4),
(13,12,11),
(14,9,5),
(14,13,12)]
self.pegs = set([0,1,2,3,4,5,6,7,8,9,10,11,12,13,14])
self.pegs.remove(missing)
self.moves_made = []
self.won = False
The constructor takes a parameter called missing to indicate which peg was picked to be blank. That peg is removed from the set of pegs when the game begins.
We still need a few more things to implement the algorithm above. First, the list of valid moves. A move is valid to be made if the source hole and hole to be jumped are occupied, but the destination is not. To generate the list, the list of all jumps is filtered by this criteria.
def can_move(self, move):
return (move[0] in self.pegs and
move[1] in self.pegs and
move[2] not in self.pegs)
def valid_moves(self):
return filter(self.can_move, self.jumps)
Next, we need to be able to make a move. The first two pegs are removed and a peg is inserted at the destination. The move made is also added to the list of moves.
def make_move(self, move):
self.pegs.remove(move[0])
self.pegs.remove(move[1])
self.pegs.add(move[2])
self.moves_made.append(move)
Undo does the opposite of making a move, taking the move to undo from the list of moves already made.
def undo(self):
move = self.moves_made.pop()
self.pegs.add(move[0])
self.pegs.add(move[1])
self.pegs.discard(move[2])
Finally, to write the actual solving bit. It implements the recursive DFS algorithm described above. When a win is found, the sequence of winning moves is printed and the search stopped.
def solve(self):
if self.won:
return
for move in self.valid_moves():
self.make_move(move)
if len(self.pegs) == 1:
print self.moves_made
self.won = True
self.solve()
self.undo()
Results
With the class created, we can use the following code to solve every starting position. You only need to consider 0,1,2,3, and 4 because other starting positions can be rotated into becoming one of those.
for i in range(0,5):
t = Triangle5(i)
print "Solution for start " + str(i)
t.solve()
- Start 0: [(3, 1, 0), (5, 4, 3), (0, 2, 5), (6, 3, 1), (9, 5, 2), (11, 7, 4), (12, 8, 5), (1, 4, 8), (2, 5, 9), (14, 9, 5), (5, 8, 12), (13, 12, 11), (10, 11, 12)]
- Start 1: [(6, 3, 1), (0, 1, 3), (8, 4, 1), (1, 3, 6), (10, 6, 3), (11, 7, 4), (2, 4, 7), (9, 5, 2), (13, 12, 11), (11, 7, 4), (3, 4, 5), (2, 5, 9), (14, 9, 5)]
- Start 2: [(9, 5, 2), (0, 2, 5), (7, 4, 2), (2, 5, 9), (13, 8, 4), (1, 4, 8), (6, 3, 1), (9, 8, 7), (11, 12, 13), (14, 13, 12), (12, 7, 3), (1, 3, 6), (10, 6, 3)]
- Start 3: [(0, 1, 3), (6, 3, 1), (5, 4, 3), (1, 3, 6), (10, 6, 3), (11, 7, 4), (2, 4, 7), (13, 12, 11), (3, 7, 12), (9, 8, 7), (11, 12, 13), (14, 13, 12), (12, 7, 3)]
- Start 4: [(11, 7, 4), (9, 8, 7), (1, 4, 8), (2, 5, 9), (6, 3, 1), (0, 1, 3), (13, 12, 11), (3, 7, 12), (11, 12, 13), (14, 9, 5), (5, 8, 12), (13, 12, 11), (10, 11, 12)]
We can also modify the search to return number of matches instead of stopping at the first one. This lets us estimate how difficult each starting position is, assuming that the more possible solutions exist, the easier it will be to find one.
To count wins, add self.wins = 0 as a line in __init__ and change the solve method to
def solve(self):
for move in self.valid_moves():
self.make_move(move)
if len(self.pegs) == 1:
self.wins += 1
self.solve()
self.undo()
- Start 0: 12060
- Start 1: 14880
- Start 2: 14880
- Start 3: 79202
- Start 4: 1550
The numbers suggest that to make it easy, start with the middle peg on a side missing. Or if you want to make it hard for a friend, start with a middle peg missing.
Full code available here.
To get notified as soon as new posts go up, sign up for my email list.