Welcome to my Peg Board Puzzle Solution Page
I became intrigued with the 5x5 triangular peg board puzzle game while dining at a Cracker Barrel restaurant. The puzzle is often referred to as the I.Q. test. I once saw a 13 year old British girl solve the puzzle on a jet plane in about 10 minutes. (She started the game with an unusual starting position which I've found to provide the most possible winning solutions :-)
Not being able to consistently solve the puzzle myself, I decided to try my hand at programming a solution. This page provides all possible solutions, some analysis, and the source code to the program I wrote to solve the puzzle.
(Recent additions: new addendum, plus new, fresh implementation in Java.)
INTRODUCTION
The basic board is a triangle of pegs. In my simulation, I used the numeric 1 to show a peg in a hole and a numeric 0 to show an empty hole. For example, one possible starting board might look like this:
0
1 1
1 1 1
1 1 1 1
1 1 1 1 1
The top hole is empty, and all the other holes are filled. A single move consists of a single pin jumping a neighbor into an empty slot, capturing the jumped neighbor, and thus removing that pin from the board. This is much like the game checkers. For the above board layout, one possible play would result in the following board layout:
1
0 1
0 1 1
1 1 1 1
1 1 1 1 1
Moves continue until no more moves are possible. The goal of the game is to remove all but the last peg. This is considered a winning game. If more than one pin is left and no more moves are possible, then this is a final, non-winning game. A solution is a winning game.
CONVENTIONS
The program I wrote takes a starting pin that will be vacant and then proceeds to solve the puzzle for all possible solutions. The pins are numbered by row and column starting with zero (sorry, most computer programs begin numbering with zero instead of one). Thus board positions are numbered as follows:
0,0
1,0 1,1
2,0 2,1 2,2
3,0 3,1 3,2 3,3
4,0 4,1 4,2 4,3 4,4
Owing to symmetry many starting board positions are equivalent. For example, an empty pin in 0,0 is the same as a starting position with an empty pin at 4,0 or at 4,4. Therefore, all possible starting positions are contained in the top half of the board, namely 0,0; 1,0; 2,0; and 2,1. All other starting positions are duplicate of these by either rotating or flipping the board. This fact will be important later if you wish to download a complete solution. You will have to decide what starting position solution set to download.
ANALYSIS
But first some analysis. I ran all possible starting positions through my program and learned a few interesting facts.
0
1 1
1 1 1
1 1 1 1
1 1 1 1 1 / 29760
1
0 1
1 1 1
1 1 1 1
1 1 1 1 1 / 14880
1
1 1
0 1 1
1 1 1 1
1 1 1 1 1 / 85258
1
1 1
1 0 1
1 1 1 1
1 1 1 1 1 / 1550
Notice that the starting board with an empty pin at position 2,0 provides the maximum number of possible winning games. This is the starting position chosen by the young British girl. She unknowingly (or perhaps she did) picked a starting position providing the maximum chance of finding a solution.
The end game, that is the game with only one peg, is quite interesting. I looked at all possible end games for the 0,0 starting board. There are only four positions where that single peg is left. This table lists the end games for the 0,0 starting board along with the number of games that lead to that solution.
Ending Board / Number of Winning Games0
0 0
0 0 0
0 0 0 0
0 0 1 0 0 / 16128
0
0 0
0 0 0
0 0 0 1
0 0 0 0 0 / 3408
0
0 0
0 0 0
1 0 0 0
0 0 0 0 0 / 3408
1
0 0
0 0 0
0 0 0 0
0 0 0 0 0 / 6816
SOLUTION
The interesting solutions are those that leave the final pin in the original empty hole. One winning solution out of the 6816 solutions that leave the pin in the original hole is listed in the table below:
0
1 1
1 1 1
1 1 1 1
1 1 1 1 1
1
1 0
1 1 0
1 1 1 1
1 1 1 1 1
1
1 0
0 0 1
1 1 1 1
1 1 1 1 1
1
1 0
0 1 1
1 1 0 1
1 1 1 0 1
1
1 0
0 1 1
1 1 0 1
1 0 0 1 1
1
1 0
0 1 1
1 1 0 1
1 0 1 0 0
1
1 0
1 1 1
0 1 0 1
0 0 1 0 0
1
0 0
0 1 1
1 1 0 1
0 0 1 0 0
1
0 0
1 1 1
1 0 0 1
0 0 0 0 0
1
0 1
1 1 0
1 0 0 0
0 0 0 0 0
0
0 0
1 1 1
1 0 0 0
0 0 0 0 0
0
1 0
0 1 1
0 0 0 0
0 0 0 0 0
0
1 0
1 0 0
0 0 0 0
0 0 0 0 0
1
0 0
0 0 0
0 0 0 0
0 0 0 0 0
COMPLETE SOLUTIONS
The complete solutions for the various starting positions are listed below. The files are zipped to compress the text. Some are vary large when unzipped. You can only download the zip file.
0
1 1
1 1 1
1 1 1 1
1 1 1 1 1 / PegBoard00.zip / 358,873 / PegBoard00.txt / 21,992,640
1
0 1
1 1 1
1 1 1 1
1 1 1 1 1 / PegBoard10.zip / 177,568 / PegBoard10.txt / 10,996,320
1
1 1
0 1 1
1 1 1 1
1 1 1 1 1 / PegBoard20.zip / 1,015,645 / PegBoard20.txt / 63,005,662
1
1 1
1 0 1
1 1 1 1
1 1 1 1 1 / PegBoard21.zip / 16,878 / PegBoard21.txt / 1,145,450
SOURCE FILES
The program which generated these solutions is written in C++ using STL components. It was developed under FreeBSD 4.4 using GNU compiler 2.95.3. It has also been compiled and run under RedHat Linux 7.1 running on DEC Alpha with GNU compiler 2.96.
Here is the source file: pegboard.cpp.
NEW!
In response to a comment that I had perhaps not found all possible solutions, I decided to write a new version of the program from scratch. I wrote a full solution solver in Java without referring to the original C++ implementation. I tested the new solver and it create the same number of solutions per starting position as the original C++ program. The funny thing is that the Java version runs twice as fast as the C++ version. I think I used better algorithms to find possible moves so it is more efficient. Have fun with it.
Here is the Java source file: PegBoard.zip.
RELATED LINKS
Danceguy has a cool Java applet version of the game online at http://mywebpages.comcast.net/danceguy/PegGame.html
Team Mad Overload has an extensive discussion and analysis at http://www.madoverlord.com/projects/crackerbarrel.t
Don Hartzler has his own page and long time experience with programming this game http://www.medjh.com/triang/.
The Cracker Barrel site has the history of the game, some hints, and a couple of online versions of the game at http://www.crackerbarrel.com/games-kids.cfm?doc_id=217. One note, their "advanced" online game actually yields the most winning number of games. Should we tell them? :-)
The Cracker Barrel site also sells the board game online. You can find it HERE!.
ADDENDUM
1. I was asked what is the worst losing game, i.e., what is the game that leaves the most number of pegs remaining. So I tweaked up my simulation to output the losing boards, and found the worst game. It leaves 10 pegs remaining starting with the center peg removed.
Lost Game Leaving the Most Pins1
1 1
1 0 1
1 1 1 1
1 1 1 1 1
1
1 1
1 1 1
1 0 1 1
1 0 1 1 1
1
1 0
1 0 1
1 1 1 1
1 0 1 1 1
1
1 0
1 1 1
1 1 0 1
1 0 1 0 1
1
1 1
1 0 1
1 0 0 1
1 0 1 0 1
2.
3. Also, I was asked about solutions to a 4x4 puzzle, a board with only 10 holes vs 15. I reran the simulation and it seems not all starting positions have solutions. The full solution set for 4x4 puzzle is here.
4. Kent Loberternos asked me via email for a solution that starts with 14 pegs and then terminates with 8 pegs and no further moves. I ran this simulation for all unique starting positions and there are exactly three solutions! The full solution set is here.
5. Got a note from Daniel C. Alsmeyer, PhD, on work he has done. He writes:
Greetings from a kindred spirit. I recently became "re-engaged" with the "Cracker Barrel" peg jump game. One of my hobbies is to make wood puzzles and I decided to make a few of these. I typically give these things away to my family and friends as Christmas (or other occasion) gifts. Since most folks don't like to be completely stumped by a problem (and love having a "cheat sheet" answer) I try to include a solution to the puzzle. Well, on this one I wasted away a few hours and kept drawing a blank, so I decided to write a quick program to solve the thing. Oddly, in my manual attempts I kept trying to find a solution from the (2,1) starting position (which has the fewest solutions and worst percentage chance of finding one!!). After completing the brute force coded solution I became slightly despondent when I learned of all the potential solutions!! For some reason I decided to search the web after I had achieved the long list of solutions. This is when I discovered your site. It seems you wrote a program that solved the puzzle in a similar manner. I thought you'd be interested to know that I achieved the same basic results as you. I had also thought up similar challenges as those you describe (leaving the final peg in the initial vacancy, what's the worst you can do, etc.). I note that you reduce the problem to the four redundant starting peg solutions. I might argue that most of the starting positions have a symmetry that also really reduces the number of "unique" solutions (i.e. (0,0) has a mirror image symmetry). One also finds that jump order is not taken into account and so truly "unique" solutions are significantly over counted. I actually counted solutions for all 15 beginning positions and declared 12 solutions for the "leave 8" problem. I set my program up to evaluate all avenues and to count the number of instances of each. Thus I tallied all possible games (one peg left, two pegs left, three pegs left, etc.). In this manner I decided that there were almost 440,000 correct ways of solving the puzzle (all redundancies included) with total possible avenues of some 22,000,000. Basically, with dumb luck, you'd expect to achieve a solution 2% of the time. I was also fascinated with the challenge of leaving the final peg in the initial vacancy. You indicate 6816 solutions for this, however that is only for the initial vacancy at (0,0). You will find 720 solutions for the (1,0) set of redundant initial vacancies and 51,452 for the (2,0). Interestingly the (2,1) set can not be solved in this manner. I did an analysis of ending peg positions and found it to have a symmetry in number to the initial vacancy solutions. In retrospect this makes sense in that one could be jumping holes as opposed to pegs and one should find the solutions mirror.
6. As in any endeavor exposed on the Internet for all to see and comment on, there will always be haters. I received email from an alleged 20 year old female, a certain Courtney Rowe, who claims that my solution set is incomplete in that she found a solution on her phone that I don't have listed. I politely asked her several times for a listing of her solution to check my results. She never responded back. Here is here email to me (text as quoted):
Your complete solutions section isn't complete! I'm a 20 yr old female and I have the game on my phone and I was able to solve this puzzle in 37 seconds... (mind u that was the first time i solved it).... different from any of ur solutions. my record for solving this puzzle is 9sec and until today i've never even seen a solution for this game let alone see anyone solve it... If u r going to have a "complete soulutions" section then i suggest that u have it complete before u put it up online so it doesn't make u look like a idiot when others can prove u wrong...my suggestion would be to change ur "complete solutions" to something more like "Solutions I've found" or something to that nature.... Have a nice day! :)
Any comments, questions, suggestions should be directed to me.