(This has been moved from my original web site, www.danobrien.ws/PegBoard.html, to here.)
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.
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.
Starting Board
|
Number of Winning Games
|
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 Games
|
0
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
|
Note: Jim (SN...@XYZ.com) noted in email that all the winning boards that starts in the 2,1 position also leave the pin in 4,2! I hadn't noticed this in all my examinations of the puzzle results. As the saying goes "None of us is as smart as all of us!". Thanks, Jim!
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:
Winning Game Leaving the Last Pin in the
Starting Empty Slot
|
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.
Starting Board
|
Zip File
|
Size (bytes)
|
Unzipped File
|
Size (bytes)
|
0
1 1 1 1 1 1 1 1 1 1 1 1 1 1 |
358,873
|
PegBoard00.txt
|
21,992,640
|
|
1
0 1 1 1 1 1 1 1 1 1 1 1 1 1 |
177,568
|
PegBoard10.txt
|
10,996,320
|
|
1
1 1 0 1 1 1 1 1 1 1 1 1 1 1 |
1,015,645
|
PegBoard20.txt
|
63,005,662
|
|
1
1 1 1 0 1 1 1 1 1 1 1 1 1 1 |
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 also sells the board game online. You can find it HERE!
ADDENDUM
- 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.
- 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.
Lost Game Leaving the Most Pins1
1 1
1 0 1
1 1 1 1
1 1 1 1 11
1 1
1 1 1
1 0 1 1
1 0 1 1 11
1 0
1 0 1
1 1 1 1
1 0 1 1 11
1 0
1 1 1
1 1 0 1
1 0 1 0 11
1 1
1 0 1
1 0 0 1
1 0 1 0 1 - 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.
- 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. - 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! :) - rgomez@i<EDIT>.com sent me the following email:
Congratulations on your work, I would only like to point one tiny missinformation, complementing what Daniel C Alsmeyer said, there are around 440,000 possible solutions including all redundancies (actually 438,984 according to the numbers you presented and the 15 possible initial positions (also redundant); If Daniel is right about the 22million possible outcomes, we would first need to know how many possible outcomes there are for each initial position in order to be certain that the 2,0 initial position that the brit girl used has the highest probabilities of being solved. Numbers look that they will probe u right about this, but I think it would be interesting to run your program to find out. And yes u did mentioned that 2,0 has the highest number of solutions not the highest percentage but I think its interesting just to find out!
===
So, I tweaked the java solution to print the number of winning boards and losing boards with percentages of the total. The percentages are very close, but the highest winning percentage (7.4%) is the one with the most winning games: 2,0
Start hole: 0,0 Winning boards: 29760 (5.2%) Losing Boards: 538870 (94.8%)
Start hole: 1,0 Winning boards: 14880 (5.1%) Losing Boards: 279663 (94.9%)
Start hole: 2,0 Winning boards: 85258 (7.4%) Losing Boards: 1064310 (92.6%)
Start hole: 2,1 Winning boards: 1550 (1.1%) Losing Boards: 136296 (98.9%) - Achim D. (JDAF..@XYZ.com) sent me the following email:
My daughter Joy, was about to fail 6th grade math, when her teacher gave her one last chance to come up with a project that would include all the forms of math they used that year and turn it in on time. She came up with the Triangle Puzzle (she also enjoyed playing the game but we had never won or found a solution)... Well, she in her simplistic way said, "Dad, if we solve the triangle puzzle, she'll have to pass my. It says right on the puzzle you are a genius if you leave just one." I smiled, because I usually left three or four. But her teacher saw intelligence in her way of doing many other things, just a lazy bone and procrastination. Even w/o study or turning in homework she would make C on most math tests.
Anyway... We made the puzzle using protractor and compass (geometry), measuring out the angles...
Then she began the attempts at problem solving... Obviously many wrong solutions as you noted in your web site... Then her first critical problem solving though process kicked in.
She asked dad there are just too many wrong answers, we can't remember them all, we need a way of writing down the moves. When you play chess, don't you write down the moves using algebraic notation (she heard Steve a friend and I talking about this)... I said, well, Steve does, but I use coordinate positioning....
Then she said, well, why don't we number each hole, and then record starting and ending position for each move... OK (she had just created a language to communicate and pass on information) -- the basis of all intelligence that is passed on.
Still there were many many wrong solutions written down.
Then she came up with an idea, "Why don't we start from the solution and work our way back?" I said Hmmmm, let's give it a try. Well it didn't work exactly, just sort of. In that when we worked our way back we recognized a mid game position that we had already recorded... We went back through all the recorded positions put the two together and wallaa... A solution, more importantly... A way of repeating and recording the solutions. My mom, like you began playing and recording solutions... Many pages...
We found out that there are really only 4 unique starting positions, all others are symply variations...
1... Center side (3 variations)
2... Off center side (6 variations)
3... Corner (3 variations)
4... Center (3 variations)
I'll attach our direction sheet we now have passed on to all we give this puzzle to. By the way she passed 6th grade math and is a teacher now.
Also her teacher then began to us this puzzle as a project in her class.
My highest compliment was being at a school in the area when another math teacher had been speaking, and he had the puzzle in a baggie (I immediately recognized it as one of ours) and asked where he got it and what he was using it for. He had been asked to speak about math in a conference and had used Joy's puzzle solution as a way of solving all math problems...
Language and solution back the two principles...
I was impressed.
-
I received the following from a fellow PegBoard enthusiast, steven.r.sides@gmail.com.
Grandpa's Peg Jumping Game
January 11, 2011
by Steve Sides
I wrote a program for my computer that analyzes Grandpa's peg jumping game. I found 2,150,587 solutions. There are really about 7.34 million, but a lot of those are duplicates, so I don't count them. You play the game by removing one peg. Then you jump pegs, checkers style, until you can't make any more jumps. The goal is to have only one peg left when you're done. Of the 2.15 million solutions, 131,448, or 6 % end up with only one peg. To make it harder, you could remember which peg you took out first, and try to make the last peg end up in that position. There are 58,988 ways to do that.
To analyze the game, I numbered the positions like this.
1 Then I wrote 2-9, for example, to mean jump the peg in position 2 over the peg in position 5 to the empty space at position 9. As far as I know, my program tried all the possibilities, but there's no way I can manually check them all.
2 3
4 5 6
7 8 9 10
11 12 13 14 15
If you give up trying for one peg left at the end; if you find it too frustrating, you might want to go for broke and leave 10 pegs. But that is even harder. There are only two ways to do that. Here's one of them. Remove the peg in position 8 and do these jumps.
3-8, 12-5, 10-8, 5-12
If you still want to go for broke, you could leave 8 pegs at the end. There are three ways to do that. (There are actually more, but they are rotations or mirror images of the 3 I'm counting.) Start by removing a peg in position 11 and make these jumps.
4-11, 6-4, 14-5, 2-9, 13-6, 11-13
If you jump rather aimlessly, you'll probably end up with three pegs at the end. There are 966,789 ways to do that. There are 991,019 ways to end up with either 2 or 4 pegs. Leaving 5, 6, or 7 pegs is somewhat harder with only 61,326 ways to get one of those. I don't believe there is any way to end up with 9 pegs. You can arrange 9 pegs, so that none can be jumped, but there's is no way to create that formation by jumping. If I'm wrong, please show me how to do it.
While we're on the subject of impossible, it's interesting that if you start by removing pegs, 5, 8, or 9, and if you end up with one peg, that peg will be in position 13, 6, or 4, respectively. In other words if you start with position 8 empty, the last peg will always be in position 6. It can't be anywhere else. There's no other way to do it. As I said before, if I'm wrong, please show me.
----------------
I decided to write the program without any outside influence. I wrote the program, analyzed my results, then found your website. I've attached my Python program. It gets the same results as yours. The Python program writes .CSV files which I pulled into MS-Access for analysis.
Best regards,
Steve
NOTE: the SQL statements I used to analyze the results:
For example, I gave 11 as the argument to listroads3.py and redirected std out to listroads11.txt. I imported the .CSV file into MS-Access and ran these queries.
/* Get the total number of solutions for each number of pegs left. */ select NUM_PEGS_LEFT,count(*) as TOTAL from Listroads11 group by NUM_PEGS_LEFT;
/* OneLeft: Get a list of PEGS_LEFT where NUM_PEGS_LEFT = 1 */ select Listroads11.NUM_PEGS_LEFT, Listroads11.PEGS_LEFT from Listroads11 where (((Listroads11.NUM_PEGS_LEFT)=1));
/* OneLeftTotals: Count the number of ways to leave one peg in the various positions. */ select PEGS_LEFT,count(*) as TOTAL from OneLeft group by PEGS_LEFT; -
I received this note from Jann Schott:
Hello! I was doing a search regarding the peg board puzzle (triangle shape) and came across your website. When I was in 8th grade (1977!), I received one of these puzzles in my Christmas stocking.
I'd play it periodically and then one day I actually "WON!" Not only did I "WIN" but I managed to end with one peg in the original starting hole.
This is the Solution that is "My claim to fame."
Using Steve Sides' model:1
2 3
4 5 6
7 8 9 10
11 12 13 14 15
I start with #13 empty. 6-13, 15-6, 13-15, 3-10, 15-6, 4-13, 1-4, 7-2, 2-9, 12-14, 6-13, 14-12, 11-13.
Enjoy!
Jann Schott,
Peoria, AZ -
Brian Adkins sent me email about solving the puzzle using Haskell. I never heard of the language, but his
solution is small and elegent:
I found your site when I was searching for description of the Cracker Barrel golf tee puzzle. I implemented a solution in Haskell that you're welcome to point to:
http://lojic.com/blog/2011/03/10/cracker-barrel-peg-board-puzzle-in-haskell/
I'm just learning Haskell, but it seemed to allow a pretty concise solution. I simply had it print the first solution in which the last tee is in the original empty hole instead of enumerating all solutions. I think enumerating all would only add a few lines of code.
Thanks,
Brian Adkins Lojic Technologies, LLC http://lojic.com/ -
Vincent Toups sent me this email about solving the puzzle using emacslisp. Amazing.
I've implemented the peg puzzle as a way of demonstrating some ideas from functional programming. My solution returns a lazy list of all possible solutions, including instructions for generating each one. It is in emacs lisp, which is kind of wacky. I wrote an entire blog post/tutorial about it: http://dorophone.blogspot.com/2011/04/deep-emacs-lisp-part-2.html
-Vincent Toups - Sam Barnum sent me his Java GUI application that runs the game interactively presenting options for the next move. Very nice presentation. He permitted me to add it to the download collection here. Download ZIP file. Run it by simply "java -jar pegboard.jar".
- Jared Proffitt created a MAC version of the game. I haven't tried it: http://jproffitt.com/PegGame.zip
- Dr. Roger Butenuth has a blog post about multitasking, data structures, and performance in solving this game. Very intestesting read. http://blog.codecentric.de/en/2012/11/java-forkjoin-improve-performance/
-
Paul Sanders sent me this note:
I was very interested in the game one day at a cracker barrel, and began on writing a code.. I used mathematica, and my solutions were exactly the same as yours. Maybe a mathematica version wouldn't hurt... yo dawg.nb
Thanks,
Paul Sanders -
Juan Mendez sent me this note:
I liked your site. Don’t know if you are still maintaining and adding links, but in case you do, here is an app for iPhone, iPads, and Macs, in case you want to list as a resource:
https://itunes.apple.com/us/app/pegs/id795966104
https://itunes.apple.com/us/app/pegs/id799510644
Best regards,
Juan C. Mendez
