How many different ways can you solve the cracker barrel peg game? And is there an optimal starting arrangement of pegs?

Question

The cracker barrel peg game is a strategical table game that is mockingly cocky with its confidence that the player won't win. Let me explain...

Here is the game set up:

The game itself is a triangular block with 15 holes in it. These holes are in parallel rows; starting with 1 hole at the top, then 2, then 3, and so on until there are 5 holes at the bottom. The player is given 14 pegs which they can arrange in any way they want at the start of the game as long as there is one hole left empty.

Here is a picture for reference:

The rules are simple:

1. 14 of the 15 holes must have a peg in them to start.
2. Only one peg can be moved at a time.
3. In order to make a move, the peg of choice must jump over another peg and into an empty space.
4. Once the peg of choice is placed into its new hole, the peg that was jumped over must be removed from the triangular block.
5. Keep jumping pegs until you can no longer make any moves.
6. You can only jump one peg at a time.
7. You can not jump over empty holes.
8. You can not move pegs into adjacent empty holes unless a separate peg was jumped.
9. Once all moves are made... if only one peg is left, then you have won!

This is how the game is cocky...

• "Leave only one- you're a genius"
• "Leave two and you're purty smart"
• "Leave three and you're just plain dumb"
• "Leave four or mor'n you're just plain 'EG-NO-RA-MOOSE'"

These are comments actually written on the game board, which can be seen in the picture above.

Going into this game without a strategy will more often than not leave you with three or four pegs left.

I know of one way to beat the game which I found online:

• Move peg 4 to position 1.

• Move peg 6 to position 4.

• Move peg 1 to position 6.

• Move peg 7 to position 2.

• Move peg 13 to position 4.

• Move peg 2 to position 7.

• Move peg 10 to position 8.

• Move peg 7 to position 9.

• Move peg 15 to position 13.

• Move peg 12 into position 14.

• Move peg 6 to position 13.

• Move peg 14 to position 12.

• Move peg 11 to position 13.

Here is the link: https://blog.crackerbarrel.com/2021/08/13/how-to-solve-the-cracker-barrel-peg-game/

They list one more way to solve, but there can't possibly be only two ways to win this game. Please let me know how many ways there are to win and how I should arrange my pins at the start for optimal winning chances! :)

Answer 1

I was fascinated by this same question and made a simple computer program to find out the answer:

To answer your question, yes there are more than two ways to win the game.

There are actually 37,260 ways to solve it. You can browse through all of these solutions and see them played out here.

As for your other question about how to arrange the pins for optimal winning chances. Well, according to the rules on the game, you have to start with one peg missing in the corner. This gives you a 5.23% chance of winning (37,260/568,630 solutions). If you did want to break the rules and get an unfair advantage, you could start with the empty peg in the middle of a side and you would have a 7.42% chance of winning (82,258/1,149,568 solutions.) Just don't start the game with a peg missing in the middle, because then you have will have a very hard time, with a 1.12% chance of winning (1,550/137,846 solutions.)

You can try all the different setups with that program linked above. It's interesting to see how the number of solutions increases massively and exponentially as the board grows.

This problem has been thoroughly studied, and there is a thorough explanation of the solutions and computation of the Cracker Barrel variety here. I personally solved the problem in a much simpler, brute force approach that generated every possible way to play the game, and then saw how many of them won.

function solve(gs: GameState): GameState[] {
    // the current board is the last in the list of boards
    // that have been played
    const current = gs[gs.length - 1];
    // find out what possible moves there are by searching the current board
    const moves = allPossibleMoves(current);
    return moves.length === 0
        // if there's no possible moves:
        // you reached the end of this game path.
        // Return the current game state as there are no other
        // possible ways the game could be played out
        ? [gs]
        // if there are maves to be made:
        // create a new path with each possible move,
        // and continue playing down all the new paths
        : moves.map(m => (
            [...gs, applyMove(current, m)]
        )).flatMap(solve);
}

Answer 2

I think you can write a computer program to solve this, with backtracking to find all possible solutions.

The pseudocode would be:

N = 2 # or whatever number of pins left you consider a solution
solutions = []

def solve(position, moves):
  if no_legal_move(position):
    if count(position) <= N:
      solutions.append(moves)
    else:
      for move in legal_moves(p):
        solve(make_move(p, move), moves + [move])

def main():
  # There should only be 15 starting positions, as there are only 15 initial holes you can have
  for starting positions p in P:
    solve(p), [p])

I think this is more of a CS question.

In terms of complexity, it looks like you can have at most 2 possible moves per stage, so there aren't that many set of moves to go through, since 2^14 is a relatively small numbers for computers to go through.