Grover's Take on Things

Have you ever eaten at one of the Cracker Barrel Restaurants that dot our Interstate Highway system?

If so, you’ve no doubt spent at least a few minutes contemplating (maybe even trying) the peg puzzle game that is found on every table. For the longest time, I never actually won a game on one of those things, leaving me to feel woefully intellectually deficient. Phooey.

KEEP READING. I got very curious about the puzzle, and over the last few weeks I put my computer programming skills to work and have uncovered some very interesting things about it, which I’ve shared below.

Before My Findings, Here are the Rules. The rules are simple enough. You are asked merely to “jump each peg and remove it” from the board, staying in a straight line for your move. Obviously, you must have a single empty slot at the start of each game (else, where would your first jump land?), and you may select whichever slot you desire to be empty. (This, as it turns out, will be crucial for a greater chance of winning.)

In the game board shown here, there are actually only 2 possible first moves. You may pick up the peg in slot D, jump over E, place the peg in J, and remove the peg from slot E. Or, you may pick the peg in slot B, jump O, and place it in slot J, removing the peg from slot O. Either way, there are now 2 empty slots — either D and E or B and O.

To win the game, you must continue to make similar moves until there is only 1 peg remaining on the board. Simple, eh? Well, not so fast. The rules of the game are simple, but a winning strategy is anything but simplistic. Maybe you need to know a little more about the game.

A Little More About the Game. I started by wondering if there was some sort of pattern or “secret knowledge” that would help solve the peg problem. So I wrote a computer program that generates every possible unique game (that is, every sequential set of legal moves), then plays each game, and finds out how many of them lead to a “win.” (If you’re interested in the logic I used to generate every move and to analyze every game, I’ve added a slightly more technical postscript to the bottom of this post.)

Here’s what I found about trying to end the game with one single peg on the board after 13 moves:

• There are 7,335,390 possible, unique games.
• Of those, 438,984 produce wins. That means 6% of all possible games result in a win.
  (Yes, I have a complete, move-by-move list of all 438,984 winning games. If you are interested in seeing that list, send me your email address and I’ll post a .TXT file back to you. But be careful what you ask for; it’s a 27.7-meg file!)
• Which initial empty slot should you select? Choosing the middle slot on one of the outside line of slots, (C, H, or M, as labeled in the graphic above) greatly increases your chance of winning. 58% of all possible wins started with one of those three slots empty. 20% of all possible wins started with an empty slot in one of the corners, A, F, or K.
• The least effective choice for the first empty is one of the interior slots (E, J, or O). These positions account for only 1% of all wins — so it’s possible, but highly unlikely. Are you challenged to try to find one or more of the 4,650 winning games that start in one of those interior empty slots?

By the way, my program took a mere 2 minutes 15 seconds to create, play, and analyze all 7+ million games on my six-year-old Dell laptop. That works out to 54,084 games played per second and 3,237 wins per second. That surely beats sitting there and pulling up and pushing in pegs for 7 millions games!

Other Ways to Win? Ending with only one peg on the board is the “official” way to win the puzzle. But who says we can’t define our own ways? While researching online what others thought of the puzzle, I came across one man’s post which said: “Leaving one peg is easy. I’m looking for the solution to leaving one peg in all three corners. Anyone know how?”

Well, never let it be said I shied away from a challenge. I only had to make two changes to the program I had already written in order to get his answer. (First, change the number of moves from 13, which leaves 1 peg, to 11, which leaves 3 pegs. Then, change what constitutes a “win” — from 1 peg anywhere on the board to 3 pegs, 1 in each corner.)

I began with the “3-Corner Win” challenge (number 1 below). Afterwards, I invented some more of my own alternate “win scenarios” (illustrated by the other grids) just to see what possibilities each might present. Since all of these “new ways to win” end with 3 pegs on the game board, each of them has the same number of possible, unique games — 6,765,402.

Here’s what I found out about these alternative games. (Each item in the numbered list refers to the corresponding numbered peg board graphic shown below.)

1. 3-CORNER WIN. This is the challenge put forward by the peg game enthusiast above — one that results in “leaving one peg in all three corners.” I was sad to have to report to him that the computer proved there are no ways to play the game and end with 3 pegs in that configuration.

2. 3-MIDDLE WIN. Here, the goal is to leave a peg in each of the three middle or interior slots. As in the 3-Corner game, there are no ways to win.
   3-MIDDLE-EMPTY WIN. However, if we change this definition of a “win” slightly, we are rewarded with a much simpler game. What if, instead of wanting to finish with all three of the interior slots filled, we play trying to leave all three interior slots empty, with three pegs anywhere else on the board? Of the 6,765,402 possible games, a whopping 4,055,706 will produce a win! That’s just a whisker under 60%!
   Where should our initial empty slot be in order to insure the greatest likelihood of success? Once again, selecting the middle slot on one of the outside line of slots is best, as 28% of all winning games started that way. The next most successful pick would be one of the three corner slots. They account for 14% of winning games. By far the least successful are any of the three interior slots.

3. 3-OUTSIDE-LINE WIN. Here’s the first of a series of definitions for a “win” which actually provide three possibilities for a win. The goal here is to leave 3 consecutive slots filled on the outside of the grid, not including one of the corners. Graphic 3 above shows one of the possibilities. A win could either be there, or across the top, or down the right side. It doesn’t make any difference, however, because once again there are no ways to win.

4. 3-CORNER-CLUSTER WIN. As before, there are three possibilities for meeting the objectives of this “win.” The goal is to leave a peg in the 3 slots clustering at the tip of each corner. Shown is the upper left corner, but one could win in the upper right corner or the lower corner. Too bad if you had your heart set on doing this one, as, (say it with me) there are no ways to win.

5. 3-LINE-BISECTER WIN. Cheer up! We’ve found another winner, though it will give you a true challenge. In this one, you want to finish with a straight line of 3 pegs, starting at a corner and going straight across to the middle slot of the opposite line. Since there are 3 corners, there are three possible ways to win this. Out of the 6,765,402 individual games, there are an even 30,000 winning games. That’s a measly 0.4%. Do you think you can find one of those 0.4%? (In the technical notes at the bottom of this post, I have given you the move-by-move solution for 1 of those 30,000 winning games, which I pulled randomly from the list.)

6. 3-CORNER-LINE WIN. This final “win” definition calls for three pegs in a row at the base of one of the corners. The illustration above shows the upper right corner, but it could equally be the upper left corner or the bottom corner. For one last time, I am forced to tell you that there are (wait for it) no ways to win.

If you have any other possible “win” configurations — any pattern / any number of pegs left — that you would like me to submit to my computer program to see if there really are any wins possible, just write it in a comment. I’ll get back to you with an answer.

Good luck with your Peg Puzzlements!

If you’re just itching to get a winning 13-move game, leaving only 1 peg on the board, here’s your booster seat. These are the instructions Cracker Barrel provides when you buy one of their wooden Peg Game boards — or the “Old Fashioned Peg Game,” as they call it.

Remember, there are 438,983 other ways to win. (Cracker Barrel understates it by saying there are “many more ways to work this game.”) So start now, and maybe by Thanksgiving you’ll find ’em all.

 
Below is a screen shot of my computer program after completing the testing the 3-Corner win scenario. (Click on the image to see a larger version, for easier reading.)
 

 

Each Peg Puzzle game you play starts with choosing an initial empty slot. Based on that, I began with empty slot A, calculated what the legal moves were from that point, and had the computer “make” each of those moves. That was “move 1” of all the empty-slot-A games. Next, the computer branched out from the “move 1’s” and calculated and made all the possible “move 2’s” from there. Then the “move 3’s,” “move 4’s,” etc., for whatever total number of moves was required for the problem I was solving. If a “win” leaves 1 peg remaining, that requires 13 moves. If 3 pegs are needed for a “win,” that requires only 11 moves. (Of course, many games end before the maximum number of moves is met because there are no more legal moves.) This succession of move 1’s, then move 2’s, 3’s, etc., creates an expanding branching or tree effect for each initial empty slot location. When the program completes the entire full set of moves and games that began with empty slot A, it moves on to slot B, then slot C, etc. and completes the same tree-making process for each. When the computer runs through all required initial empty slots, it has generated and played every possible game. The program then reports to me how many possible games there are and, more important, how many wins arise from those games.

The program I wrote does 3 major things: (1) it generates and counts all possible, unique games (i.e., series of legal moves) for the board, based on where the initial empty slot is placed; (2) it plays each game strictly by the rules to its logical conclusion; and (3) it counts the number of wins achieved (however “win” is defined) and records each winning game’s moves. All other numbers, statistics, and conclusions are derived from these three processes. The backbone of all of this comprises several algorithms I created, including one to test the game board, whatever its current configuration of pegs and empty slots, and identify how many legal moves there are and what those moves are.

You may have wondered about the seemingly haphazard way I assigned letters to the slots on the game board. (See graphic at the top of this page.) Because the game board forms an equilateral triangle (all three sides equal in length), you can turn it 120 degrees to the left or to the right, and you are looking at an identical grid of slots. Using that fact, it was easy to divide the 15 slots into 3 groups that also mirror one another, no matter which way you turn the board. This is shown by the areas colored in yellow, blue, and green in the graphic at the left. Let’s consider the move where you pick up the peg in A, jump the peg in B, place it in the empty slot C, and then remove peg B. Turn the game board 120 degrees counterclockwise. Note that the move pick up F, jump G, place in H, and remove G is identical to your previous move. It will be the same for the slots K-L-M. What this fact means for testing games of the Peg Puzzle is that you only have to test one-third of the initial empty slots. (For convenience, I choose to test initial empty slots A-E.) So in almost all cases, I merely have to find all the possible games that have slots A, B, C, D, and E as initially empty, find out how many winning games we get from those games, and multiply by 3 to determine results for the entire board.

This is the sample winning game I promised from the “3-LINE-BISECTER WIN” (number 5) section above. If you want to test it, to see how it gets to the desired “win,” here’s what you do. Label the slots on your peg puzzle board the same way shown in the graphic at the top of this post (A through O) — it won’t work otherwise. Then, put the 14 pegs in, leaving the C slot empty. Each group of 3 letters below is a move, and you play it this way: the first move is FDC, which means take the F peg, jump the D peg, and place it in the C slot. Remove the D peg. Keep going with each 3-letter group through the end.

Using the set of moves I’ve given you above, the final 3 pegs are in slots C, J, and K, the same as shown in the graphic. Of course, you could win with either of the other “Line Bisector” possibilities: A-O-H or F-E-M. Can you find the remaining 29,999 winning games? 🙂