Cracker Barrel

Cracker Barrel

August 19, 2014

While I was out of town last week, I ate dinner one evening at Cracker Barrel, which provides a triangle puzzle at each table so you can amuse yourself while you are waiting for your food. When my daughter challenged me to solve the problem, I failed, but I promised her that I would write a program to solve it.

As shown in the picture at right, the puzzle is a triangle with 15 holes and 14 pegs; one hole is initially vacant. The game is played by making 13 jumps; each jump removes one peg from the triangle, so at the end of 13 jumps there is one peg remaining. A jump takes a peg from a starting hole, over an occupied hole, to an empty finishing hole, removing the intermediate peg.

Your task is to write a program that solves the Cracker Barrel puzzle; find all possible solutions that start with a corner hole vacant and end with the remaining peg in the original vacant corner. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

20 Responses to “Cracker Barrel”

1. August 19, 2014 at 4:27 PM

   That’s amusing. About a month and a half ago, I came across another site that had the same challenge, so I worked it out then:

   Cracker Barrel Peg Game – framework and basic solver
   Cracker Barrel Peg Game, Part 2 – which solutions are most solvable
   Cracker Barrel Peg Game, Part 3 – interactive command line game

   Although I will admit I don’t have anything that will end in a specific win state. It should be only a single line to add though.

   (All three in Racket.)

2. August 19, 2014 at 10:45 PM

   I remember writing a solver for that puzzle long ago. I was still living with my parents, and I was writing in C, so that dates it around 1981-84. Of course, the code is long gone.

3. August 20, 2014 at 3:29 AM

   use strict; use warnings; my $possible_moves = [ [ [1,3],[2,5] ], [ [3,6],[4,8] ], [ [4,7],[5,9] ], [ [1,0],[4,5],[6,10],[7,12] ], [ [7,11],[8,13] ], [ [2,0],[4,3],[8,12],[9,14] ], [ [3,1],[7,8] ], [ [4,2],[8,9] ], [ [4,1],[7,6] ], [ [5,2],[8,7] ], [ [6,3],[11,12] ], [ [7,4],[12,13] ], [ [7,3],[8,5],[11,10],[13,14] ], [ [8,4],[12,11] ], [ [9,5],[13,12] ], ]; solve_grid( q(011111111111111), [] ); sub solve_grid { my ( $grid, $moves ) = @_; if( @{$moves} == 13 && $grid eq q(100000000000000) ) { print “@{$moves}n”; return; } foreach my $i (0..14) { next unless substr $grid, $i, 1; foreach my $m (@{$possible_moves->[$i]}) { next if substr $grid, $m->[1], 1; next unless substr $grid, $m->[0], 1; my $g = $grid; substr $g, $i, 1, 0; substr $g, $m->[0],1, 0; substr $g, $m->[1],1, 1; solve_grid( $g, [@{$moves},”$i->$m->[1]”] ); } } return; }

4. August 20, 2014 at 3:53 AM

   I think this is slightly slower – but slight more compact code…

   use strict; use warnings; use feature qw(say); my $possible_moves = [ [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,2,0], [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], ]; solve_grid( q(011111111111111), q() ); sub solve_grid { my ( $grid, $moves ) = @_; return say $moves if $grid eq q(100000000000000); foreach (@{$possible_moves}) { my $g = $grid; next if ! substr( $g, $_->[0],1, 0 ) || ! substr( $g, $_->[1],1, 0 ) || substr( $g, $_->[2],1, 1 ); solve_grid( $g, $moves.”$_->[0]->$_->[2] ” ); } return; }

5. August 20, 2014 at 12:27 PM

   In Python.

   BOARD_INIT = [0] + [1] * 14 MOVE_MASKS = [(0, 1, 3), (0, 2, 5), (1, 3, 6), (1, 4, 8), (2, 4, 7), (2, 5, 9), (3, 4, 5), (3, 6, 10), (3, 7, 12), (4, 7, 11), (4, 8, 13), (5, 8, 12), (5, 9, 14), (6, 7, 8), (7, 8, 9), (10 ,11, 12), (11, 12, 13), (12, 13, 14)] def find_moves(board): “””move: tuple with (from, over, to)””” for m1, m2, m3 in MOVE_MASKS: if board[m2]: if board[m1] and not board[m3]: yield m1, m2, m3 elif board[m3] and not board[m1]: yield m3, m2, m1 def do_move(move, board): board = list(board) m1, m2, m3 = move board[m1], board[m2], board[m3] = 0, 0, 1 return board def solve(board=BOARD_INIT, movs=[]): “””generate all movesequences that result in one peg””” if sum(board) == 1: yield movs else: for m in find_moves(board): for g in solve(do_move(m, board), movs + [m]): yield g print sum(1 for moves in solve() if moves[-1][-1] == 0) # 6816 print sum(1 for moves in solve()) # 29760