Southern Food and Graph Theory: Part 1

For the last few posts, I've been mentioning a "big project" that's taking a long time to finish. I've come to the realization that if I don't break this project up into multiple parts, I will never finish it. I don't know how many parts there will be in this series, but this initial post will cover the premise and any context I think will be relevant.

Cracker Barrel

Cracker Barrel is a chain of restaurants concentrated mostly in the South-East and Midwestern United States. If you've never been to one, don't worry, their involvement here is incidental at best.

When you eat at Cracker Barrel, you will most likely find a triangular piece of wood laying on the table. This triangle will have 15 holes drilled into it, and 14 of the holes will have a golf tee stuck in them. This piece of wood is a particular kind of Peg Solitaire.

The holes are arranged in a triangular grid of sorts. Adjacent pegs can jump over one another, so long as there is an empty space for the jumping peg to land in. A single move consists of jumping one peg (the jumper) over another (the jumped) and then removing the "jumped" peg from the board. The goal is to be left with a single peg on the board.

Interesting Questions

The Cracker Barrel version of the game includes the additional statements:

Clearly, Cracker Barrel doesn't think highly of you if you leave 3 or more pegs. But, can we assign a sort of objective "difficulty score" to each of these outcomes? In other words, can we quantify the relative difficulty of ending up with 2, 3, or 4 pegs compared to winning the game?

Furthermore, what's the worst you can possibly score? It's not difficult to end up with 4 or even 5 pegs just by playing. But what's the most number of pegs you can leave on the board without there being any valid moves?

The Cracker Barrel version of the game does not stipulate which slot in the board should be empty at the start of the game. Naturally we would want to know which starting state will give us the easiest time winning the game.

Are there unreachable board states? If so, how many are there? And what about larger boards? If you make the board larger does it make it easier or harder to win the game?

Tools of the Trade

To answer these questions, we'll use my favorite trick: model the problem as a graph. Once we have a suitable graph, we can run some computations to answer all of our burning questions about Cracker Barrel's peg solitaire!