Solving Peg Solitaire as Seen on Smartest Guy in the Room

I recently started watching History channel’s show Smartest Guy in the Room. The basic premise of the show is there’s three kind of regular guys with regular jobs, but each of them have high IQs. Each episode one of the three designs two challenges in an attempt to stump the other two. If the challenge designer stumps them, he gets the title of “Smartest Guy in the Room”. If one of the two solve the challenges, then they get the title for that episode.

It’s a really fun show and in some respects reminds me of Myth Busters. The show breaks down the science or theory of each challenge, often diving into how the brain processes certain types of information. They also feature quite a few challenges that you can do at home. I like to pause the screen and try to solve the puzzles before the solution is revealed. They even did a paper airplane making competition! Not to brag, but I did win a paper airplane making contest in grade 7.

In Episode 10, How to Miss a Hole in One, besides showing off his impressive mini-golf skills, Randy Rice challenges the guys to a life size version of Peg Solitaire. I’ve seen this game many times, but never actually played it. The version that is featured in the show is a triangle with 15 pegs. You start the game by removing one peg, any peg you choose, then you continue to jump over other pegs to remove them. The goal is to remove all pegs but one. There’s situations where you will get stuck because you can only jump into an empty space and you can’t jump an existing space.

An example start configuration is shown below, along with two moves. The middle peg has been removed to start the game. In the second image, we’ve jumped the light gray peg into the red hole in an upper left move, and then light gray to red hole in the final image in a horizontal move.

When Randy was explaining the rules of the game, he posed this question to the at home audience: the first decision you have to make, is it better to remove your first peg from the edges, the corners, or the center? What would your strategy be?

Is it better to remove your first peg from the edges, the corners, or the center?

This question is what really peaked my interest in this game and is the subject of today’s blog post. To me, this statement implied that there could be a certain peg removal at the very start of the game that would make it impossible to win. Now, this game has been around since the 1600s, so I was sure someone has already figured this out, but what fun would that be?

I decided to test whether this is the case by writing a computer program to solve all possible versions of the game.

So how do we do that?

Solving Peg Solitaire

Most games of this nature can be modeled as a graph where each state of the board is a node in a graph and there’s an edge between two nodes (states) if there’s a legal move that would transpose the game board state into another. This is demonstrated in the image below with a partial graph of 4 different moves. In fact, since we are always removing pieces, this graph actually forms a tree. The depth of the tree corresponds to how many peg removals have taken place.

Many many problems can be modeled like this, path finding in games, pattern recognition problems, movements on a chess board, game AI, and so on all use this basic idea.

Now to compute this tree and traverse it to find various winning conditions raises another question, how big is this problem? Can it be computed within a reasonable amount of time?

Well, it’s pretty simple to get an estimate for how many possible states there could be. Since there’s 15 pegs, and each peg has one of two states, exists or doesn’t exist, if all board configurations were actually possible within the rules of the game, that leaves 2¹⁵, or 32,768 possible nodes in our graph, which is certainly within the bounds of what we can compute with a computer. This is an upper bound, as it’s not possible to actually reach all 2¹⁵ board states.

Ok, now we have our graph idea and we know we can hold every possible state in memory, how can be actually build and walk this graph?

We can do this with a breadth-first search (BFS) algorithm, stopping when we reach a winning state. The basic idea is shown below.

while(queue is not empty) {
   currentBoard = pop queue item;

   if(currentBoard is winning condition) yay, we solved it!
   else if(we've seen currentBoard before ignore this case)
   else {
      add all legal moves from currentBoard to our queue
   }
}

Once I completed the code, I ran through all possible peg starting conditions to test whether you can always solve the game regardless of your start point.

The answer?

Yes, you can always solve the game regardless of what peg you choose to remove first.

This felt a little anti-climactic to me when I realized this, so I did some reading about the game online and it turns out there’s another way to think about moves in the game that makes things more interesting.

More Advanced Peg Solitaire

It turns out that if in a given game state, you can move multiple pegs independent of each other, then that counts as a single move. For example, in the board below, we can jump both red pegs into the empty holes, and that counts as a single move.

I modified my original algorithm to compute the number of moves based on this information. This makes it so we can no longer use a basic breadth-first search and instead we need to make sure we are prioritizing states with less moves. This calls for an A* search algorithm, which is very similar to a breadth-first search (I’ll spare you the details).

I once again tried all possible starting conditions, and reported the minimum number of moves to win the game. This time, I got some variance in my answers.

The Solution to the More Advanced Peg Solitaire

It turns out that the minimum number of moves varies between 9 and 12, depending on which peg you first remove. If you start with a middle side peg, then you can win in 9 moves, if you instead start with the middle peg, then it will take you 12 moves!

I did some more reading and it turns out this was reported in 2008 in the Journal of Integer Sequences, so I am 8 years too late :-).

Yet an EVEN More Advanced Peg Solitaire

During my reading, I also discovered another more complex version of this game where the goal is to end the game with the final peg in the hole of the first peg you removed. So whichever peg you decide to remove first, your last peg needs to end up there.

Again, I decided to test all possible start conditions and see what story it would tell. The only code modification needed was to adjust our win state to make sure the final peg is in the same location as the first peg removal.

The Solution to the EVEN More Advanced Peg Solitaire

Turns out that if you play the game this way and you start by removing any of the inner three pegs, you cannot win. The minimum number of moves to win is still 9 if you start with a middle side peg.

Well, if you made it this far, you likely now know more about solutions to versions of the 15 peg triangle version of Peg Solitaire than you care to admit :-). I left out most of the nitty gritty details of the code I wrote, but if you’re interested in the gory details, leave me a comment or hit me up on Twitter @seanfalconer.