Cracker Barrel's peg board problem
Going down a rabbit hole
Summary
Well this has gotten a bit out of hand. The project began with a simple question of how to solve that dang pegboard problem, and fell down a rabbit hole. That's presumably because the problem is more complex than I thought.
Attempting a solution
I tried about 20 times and failed, not finding any good patterns or strategies. I did notice the symmetries of the board, such that there are really only four starting places: 1, 3, 5, and 6.
The reversal "trick"
I made what I thought was a major breakthrough in reasoning about the problem in my first 30 minutes, when I realized I could play the whole game backwards. That is, we usually start with one peg missing and eliminate pegs by taking one and hopping it over another to eliminate it, an operation that takes a contiguous "XXO" and turns it into an "OOX". Instead, we can start with only one peg present and replace a contiguous "OOX" with "XXO". It's easy to see that reversing any solution like this will give us a solution to the original problem. You can also replace each OOX-XXO operation with an XXO-OOX operation and get a solution as well, illuminating a symmetry. This symmetry should mean that there are just as many solutions that start at 5 and end at 13 as there are solutions that start at 13 and end at 5. It also means that if you can solve it starting at one peg, you can solve it by ending at the peg as well, and vice versa.
Simulation
The next step when you can't solve a puzzle like this is to brute force it. In about an hour I had a working simulation that could simply try everything and report back on what works. So now I have all the solutions. Who knows where this actually got me though! You can find the code I used to generate the solutions at the end here.
Googling a solution
First result from Google is some bloke that seems to recommend just memorize the winning combinations to impress people. What's impressive about that?
George Bell seems to have been working on his solution for some time. He is able to solve arbitrarily large such triangles, he optimizes for the number of "moves". He recalls a "pagoda function" of the board which must be positive for any solvable configuration (the SAX number), and cannot decrease (citing some Hentzel and Hentzel 1986 which published in The Journal of Recreational Mathematics), and notes some practical rules of thumb based on this which increase the odds of a layperson completing the puzzle jump dramatically.
A player can avoid jumps of the first two types by remembering the following rule of thumb: avoid jumping into a corner or out of the interior. Many people stymied by this puzzle can find a solution if they follow this rule of thumb. (p. 7)
His simulations show that your best chance is to follow this rule of thumb and start with one of the pegs in the center on an edge missing. This gives any random go a 1/7 chance of being successful.
I also found out that this game is more general (play them all here), and some of them are much harder than this dinky (lol) triangle puzzle.
My solutions
Code is here
Enumerating them
This section just counts my solutions. This is partially a sanity check, partially of interest to which are the "hardest" and "easiest" to solve. Also how can I figure these solutions out more generally?
- 1 1 = 6816 = 2^5 × 3 × 71
- 1 7 = 3408 = 2^4 × 3 × 71
- 1 10 = 3408
- 1 13 = 16128 = 2^8 × 3^2 × 7
- 3 3 = 720 = 2^4 × 3^2 × 5
- 3 4 = 8064 = 2^7 × 3^2 × 7
- 3 12 = 2688 = 2^7 × 3 × 7
- 3 15 = 3408
- 5 13 = 1550 = 2 × 5^2 × 31
- 6 2 = 8064
- 6 6 = 51452 = 2^2 × 19 × 677
- 6 8 = 1550
- 6 11 = 16128
- 6 14 = 8064
Notes We have some matching numbers, all of which can be understood by the reversal trick described above:
- (1 7) = (3 15) = (1 10)
- (1 13) = (3 11)
- (3 4) = (6 2) = (6 14)
- (5 13) = (6 8)
I'm wondering if these strange looking prime factorizations have anything to do with symmetries. Check out the 6 6 transition! It has prime factors of 677 and 19, how strange.
I did a search in the sequence database and found some interesting sequences which contain all the interesting prime factors above. I doubt this means anything though. The sequences are all a bit wacky.
Starting at position 1
- dead_end: 538870
- recurse: 1293179
- winner: 29760
Ending at position 13
....0.... ....1.... ....1.... ....1.... ....1....
...1.1... ...0.1... ...0.1... ...1.1... ...0.1...
..1.1.1.. ..0.1.1.. ..1.1.1.. ..1.0.1.. ..0.0.1..
.1.1.1.1. .1.1.1.1. .0.1.1.1. .0.1.0.1. .1.1.0.1.
1.1.1.1.1 1.1.1.1.1 0.1.1.1.1 0.1.1.1.1 0.1.1.1.1
....1.... ....1.... ....1.... ....0.... ....0....
...0.1... ...0.0... ...0.1... ...0.0... ...0.0...
..0.1.1.. ..0.0.1.. ..0.0.0.. ..0.0.1.. ..0.0.1..
.1.0.0.1. .1.1.0.1. .1.1.0.0. .1.1.0.0. .0.0.1.0.
0.0.1.1.1 0.0.1.1.1 0.0.1.1.1 0.0.1.1.1 0.0.1.1.1
....0.... ....0.... ....0.... ....0....
...0.0... ...0.0... ...0.0... ...0.0...
..0.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.1.0.0.1 0.1.1.0.1 0.0.0.1.1 0.0.1.0.0
Ending at position 1
....0.... ....1.... ....1.... ....1.... ....0....
...1.1... ...0.1... ...0.1... ...1.1... ...0.1...
..1.1.1.. ..0.1.1.. ..1.1.1.. ..0.1.1.. ..1.1.1..
.1.1.1.1. .1.1.1.1. .1.0.1.1. .0.0.1.1. .0.0.1.1.
1.1.1.1.1 1.1.1.1.1 1.1.0.1.1 1.1.0.1.1 1.1.0.1.1
....0.... ....0.... ....0.... ....0.... ....0....
...0.0... ...0.1... ...0.1... ...0.1... ...0.1...
..1.0.1.. ..1.0.0.. ..1.0.0.. ..1.0.0.. ..0.0.0..
.0.1.1.1. .0.1.1.0. .0.1.1.0. .0.1.1.0. .0.0.1.0.
1.1.0.1.1 1.1.0.1.1 0.0.1.1.1 0.1.0.0.1 0.1.1.0.1
....0.... ....0.... ....0.... ....1....
...0.1... ...0.1... ...0.1... ...0.0...
..0.0.0.. ..0.0.0.. ..0.0.1.. ..0.0.0..
.0.0.1.0. .0.0.1.0. .0.0.0.0. .0.0.0.0.
0.0.0.1.1 0.0.1.0.0 0.0.0.0.0 0.0.0.0.0
Ending at position 10
....0.... ....1.... ....1.... ....1.... ....0....
...1.1... ...0.1... ...0.1... ...1.1... ...0.1...
..1.1.1.. ..0.1.1.. ..1.1.1.. ..0.1.1.. ..1.1.1..
.1.1.1.1. .1.1.1.1. .1.0.1.1. .0.0.1.1. .0.0.1.1.
1.1.1.1.1 1.1.1.1.1 1.1.0.1.1 1.1.0.1.1 1.1.0.1.1
....0.... ....0.... ....0.... ....0.... ....0....
...0.0... ...0.1... ...0.1... ...0.1... ...0.1...
..1.0.1.. ..1.0.0.. ..1.0.0.. ..1.0.0.. ..0.0.0..
.0.1.1.1. .0.1.1.0. .0.1.1.0. .0.1.1.0. .0.0.1.0.
1.1.0.1.1 1.1.0.1.1 0.0.1.1.1 0.1.0.0.1 0.1.1.0.1
....0.... ....0.... ....0.... ....0....
...0.1... ...0.1... ...0.1... ...0.0...
..0.0.0.. ..0.0.0.. ..0.0.1.. ..0.0.0..
.0.0.1.0. .0.0.1.0. .0.0.0.0. .0.0.0.1.
0.0.0.1.1 0.0.1.0.0 0.0.0.0.0 0.0.0.0.0
Ending at position 7
....0.... ....1.... ....1.... ....1.... ....1....
...1.1... ...0.1... ...0.1... ...1.1... ...1.0...
..1.1.1.. ..0.1.1.. ..1.1.1.. ..0.1.1.. ..0.0.1..
.1.1.1.1. .1.1.1.1. .1.0.1.1. .0.0.1.1. .0.1.1.1.
1.1.1.1.1 1.1.1.1.1 1.1.0.1.1 1.1.0.1.1 1.1.0.1.1
....1.... ....0.... ....0.... ....0.... ....0....
...1.1... ...1.0... ...1.0... ...1.0... ...1.0...
..0.0.0.. ..0.0.1.. ..0.0.1.. ..0.0.1.. ..0.0.0..
.0.1.1.0. .0.1.1.0. .0.1.1.0. .0.1.1.0. .0.1.0.0.
1.1.0.1.1 1.1.0.1.1 0.0.1.1.1 0.1.0.0.1 0.1.1.0.1
....0.... ....0.... ....0.... ....0....
...1.0... ...1.0... ...1.0... ...0.0...
..0.0.0.. ..0.0.0.. ..1.0.0.. ..0.0.0..
.0.1.0.0. .0.1.0.0. .0.0.0.0. .1.0.0.0.
0.0.0.1.1 0.0.1.0.0 0.0.0.0.0 0.0.0.0.0
Starting at position 3
- dead_end: 279663
- recurse: 671085
- winner: 14880
Ending at position 12
....1.... ....1.... ....1.... ....1.... ....1....
...1.0... ...1.1... ...1.1... ...1.0... ...1.0...
..1.1.1.. ..1.1.0.. ..1.1.1.. ..1.1.0.. ..1.1.1..
.1.1.1.1. .1.1.1.0. .1.1.0.0. .1.1.0.1. .1.1.0.0.
1.1.1.1.1 1.1.1.1.1 1.1.0.1.1 1.1.0.1.1 1.1.0.1.0
....1.... ....1.... ....0.... ....0.... ....0....
...0.0... ...1.0... ...0.0... ...0.0... ...0.0...
..1.0.1.. ..0.0.1.. ..1.0.1.. ..1.0.1.. ..1.0.1..
.1.1.1.0. .0.1.1.0. .0.1.1.0. .0.1.1.0. .0.1.1.0.
1.1.0.1.0 1.1.0.1.0 1.1.0.1.0 0.0.1.1.0 0.1.0.0.0
....0.... ....0.... ....0.... ....0....
...0.0... ...0.0... ...0.0... ...0.0...
..1.0.0.. ..1.0.0.. ..0.0.0.. ..0.0.0..
.0.1.0.0. .0.1.0.0. .0.0.0.0. .0.0.0.0.
0.1.1.0.0 0.0.0.1.0 0.0.1.1.0 0.1.0.0.0
Ending at position 15
....1.... ....1.... ....1.... ....1.... ....1....
...1.0... ...1.1... ...1.1... ...1.0... ...1.0...
..1.1.1.. ..1.1.0.. ..1.1.1.. ..1.1.0.. ..1.1.1..
.1.1.1.1. .1.1.1.0. .1.1.0.0. .1.1.0.1. .1.1.0.0.
1.1.1.1.1 1.1.1.1.1 1.1.0.1.1 1.1.0.1.1 1.1.0.1.0
....1.... ....1.... ....0.... ....0.... ....0....
...0.0... ...1.0... ...0.0... ...0.0... ...0.0...
..1.0.1.. ..0.0.1.. ..1.0.1.. ..1.0.1.. ..1.0.1..
.1.1.1.0. .0.1.1.0. .0.1.1.0. .0.1.1.0. .0.1.1.0.
1.1.0.1.0 1.1.0.1.0 1.1.0.1.0 0.0.1.1.0 0.1.0.0.0
....0.... ....0.... ....0.... ....0....
...0.0... ...0.0... ...0.0... ...0.0...
..1.0.0.. ..1.0.0.. ..0.0.0.. ..0.0.0..
.0.1.0.0. .0.1.0.0. .0.0.0.0. .0.0.0.0.
0.1.1.0.0 0.0.0.1.0 0.0.1.1.0 0.0.0.0.1
Ending at position 4
....1.... ....1.... ....1.... ....1.... ....1....
...1.0... ...1.1... ...1.1... ...1.0... ...1.0...
..1.1.1.. ..1.1.0.. ..1.1.1.. ..1.1.0.. ..1.1.1..
.1.1.1.1. .1.1.1.0. .1.1.0.0. .1.1.0.1. .1.1.0.0.
1.1.1.1.1 1.1.1.1.1 1.1.0.1.1 1.1.0.1.1 1.1.0.1.0
....1.... ....1.... ....0.... ....0.... ....0....
...0.0... ...1.0... ...0.0... ...0.0... ...0.0...
..1.0.1.. ..0.0.1.. ..1.0.1.. ..1.0.1.. ..1.0.1..
.1.1.1.0. .0.1.1.0. .0.1.1.0. .0.1.1.0. .0.1.1.0.
1.1.0.1.0 1.1.0.1.0 1.1.0.1.0 0.0.1.1.0 0.1.0.0.0
....0.... ....0.... ....0.... ....0....
...0.0... ...0.0... ...0.0... ...0.0...
..0.0.1.. ..0.0.1.. ..0.1.1.. ..1.0.0..
.0.0.1.0. .0.0.1.0. .0.0.0.0. .0.0.0.0.
0.1.1.0.0 0.0.0.1.0 0.0.0.0.0 0.0.0.0.0
Ending at position 3
....1.... ....1.... ....1.... ....1.... ....1....
...1.0... ...1.1... ...1.1... ...1.0... ...0.0...
..1.1.1.. ..1.1.0.. ..1.1.1.. ..1.1.0.. ..1.0.0..
.1.1.1.1. .1.1.1.0. .1.1.0.0. .1.1.0.1. .1.1.1.1.
1.1.1.1.1 1.1.1.1.1 1.1.0.1.1 1.1.0.1.1 1.1.0.1.1
....1.... ....0.... ....0.... ....0.... ....0....
...1.0... ...0.0... ...0.0... ...0.0... ...0.0...
..0.0.0.. ..1.0.0.. ..1.0.0.. ..1.0.0.. ..0.0.0..
.0.1.1.1. .0.1.1.1. .0.1.1.1. .0.1.1.1. .0.0.1.1.
1.1.0.1.1 1.1.0.1.1 0.0.1.1.1 0.1.0.0.1 0.1.1.0.1
....0.... ....0.... ....0.... ....0....
...0.0... ...0.0... ...0.0... ...0.1...
..0.0.0.. ..0.0.0.. ..0.0.1.. ..0.0.0..
.0.0.1.1. .0.0.1.1. .0.0.0.1. .0.0.0.0.
0.0.0.1.1 0.0.1.0.0 0.0.0.0.0 0.0.0.0.0
Starting at position 5
- dead_end: 136296
- recurse: 323873
- winner: 1550
Ending at position 13
....1.... ....1.... ....1.... ....1.... ....1....
...1.1... ...1.1... ...1.1... ...1.0... ...1.0...
..1.0.1.. ..1.1.1.. ..1.1.1.. ..1.1.0.. ..1.1.1..
.1.1.1.1. .1.0.1.1. .1.1.0.0. .1.1.0.1. .1.1.0.0.
1.1.1.1.1 1.0.1.1.1 1.0.1.1.1 1.0.1.1.1 1.0.1.1.0
....1.... ....1.... ....0.... ....0.... ....0....
...0.0... ...1.0... ...0.0... ...0.0... ...0.0...
..1.0.1.. ..0.0.1.. ..1.0.1.. ..1.0.1.. ..1.0.0..
.1.1.1.0. .0.1.1.0. .0.1.1.0. .0.1.1.0. .0.1.0.0.
1.0.1.1.0 1.0.1.1.0 1.0.1.1.0 1.1.0.0.0 1.1.1.0.0
....0.... ....0.... ....0.... ....0....
...0.0... ...0.0... ...0.0... ...0.0...
..1.0.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.
1.0.0.1.0 1.0.1.1.0 1.1.0.0.0 0.0.1.0.0
Starting at position 6
- dead_end: 1064310
- recurse: 2592133
- winner: 85258
Ending at position 6
....1.... ....1.... ....1.... ....1.... ....0....
...1.1... ...1.1... ...0.1... ...1.1... ...0.1...
..1.1.0.. ..1.1.1.. ..1.0.1.. ..0.0.1.. ..1.0.1..
.1.1.1.1. .1.1.0.1. .1.1.1.1. .0.1.1.1. .0.1.1.1.
1.1.1.1.1 1.1.0.1.1 1.1.0.1.1 1.1.0.1.1 1.1.0.1.1
....0.... ....0.... ....0.... ....0.... ....0....
...0.1... ...0.0... ...0.1... ...0.1... ...0.1...
..1.1.1.. ..1.0.1.. ..1.0.0.. ..0.0.0.. ..0.0.0..
.0.0.1.1. .0.1.1.1. .0.1.1.0. .0.0.1.0. .0.0.1.0.
1.0.0.1.1 1.0.0.1.1 1.0.0.1.1 1.0.1.1.1 1.1.0.0.1
....0.... ....0.... ....0.... ....0....
...0.1... ...0.1... ...0.0... ...0.0...
..0.0.0.. ..0.0.1.. ..0.0.0.. ..0.0.1..
.0.0.1.0. .0.0.0.0. .0.0.0.1. .0.0.0.0.
0.0.1.0.1 0.0.0.0.1 0.0.0.0.1 0.0.0.0.0
Ending at position 11
....1.... ....1.... ....1.... ....1.... ....1....
...1.1... ...1.1... ...1.1... ...0.1... ...0.1...
..1.1.0.. ..1.1.1.. ..1.1.1.. ..0.1.1.. ..1.1.1..
.1.1.1.1. .1.1.0.1. .0.0.1.1. .1.0.1.1. .0.0.1.1.
1.1.1.1.1 1.1.0.1.1 1.1.0.1.1 1.1.0.1.1 0.1.0.1.1
....1.... ....1.... ....0.... ....0.... ....0....
...0.0... ...0.1... ...0.0... ...0.0... ...0.0...
..1.0.1.. ..1.0.0.. ..1.0.1.. ..1.0.1.. ..1.0.1..
.0.1.1.1. .0.1.1.0. .0.1.1.0. .0.1.1.0. .0.1.1.0.
0.1.0.1.1 0.1.0.1.1 0.1.0.1.1 0.1.1.0.0 0.0.0.1.0
....0.... ....0.... ....0.... ....0....
...0.0... ...0.0... ...0.0... ...0.0...
..1.0.0.. ..1.0.0.. ..0.0.0.. ..0.0.0..
.0.1.0.0. .0.1.0.0. .0.0.0.0. .0.0.0.0.
0.0.1.1.0 0.1.0.0.0 0.1.1.0.0 1.0.0.0.0
Ending at position 14
....1.... ....1.... ....1.... ....1.... ....1....
...1.1... ...1.1... ...1.1... ...0.1... ...0.1...
..1.1.0.. ..1.1.1.. ..1.1.1.. ..0.1.1.. ..1.1.1..
.1.1.1.1. .1.1.0.1. .0.0.1.1. .1.0.1.1. .0.0.1.1.
1.1.1.1.1 1.1.0.1.1 1.1.0.1.1 1.1.0.1.1 0.1.0.1.1
....1.... ....1.... ....0.... ....0.... ....0....
...0.0... ...0.1... ...0.0... ...0.0... ...0.0...
..1.0.1.. ..1.0.0.. ..1.0.1.. ..1.0.1.. ..1.0.1..
.0.1.1.1. .0.1.1.0. .0.1.1.0. .0.1.1.0. .0.1.1.0.
0.1.0.1.1 0.1.0.1.1 0.1.0.1.1 0.1.1.0.0 0.0.0.1.0
....0.... ....0.... ....0.... ....0....
...0.0... ...0.0... ...0.0... ...0.0...
..1.0.0.. ..1.0.0.. ..0.0.0.. ..0.0.0..
.0.1.0.0. .0.1.0.0. .0.0.0.0. .0.0.0.0.
0.0.1.1.0 0.1.0.0.0 0.1.1.0.0 0.0.0.1.0
Ending at position 2
....1.... ....1.... ....1.... ....1.... ....1....
...1.1... ...1.1... ...1.1... ...0.1... ...0.0...
..1.1.0.. ..1.1.1.. ..1.1.1.. ..0.1.1.. ..0.0.1..
.1.1.1.1. .1.1.0.1. .0.0.1.1. .1.0.1.1. .1.1.1.1.
1.1.1.1.1 1.1.0.1.1 1.1.0.1.1 1.1.0.1.1 1.1.0.1.1
....1.... ....0.... ....0.... ....0.... ....0....
...0.1... ...0.0... ...0.0... ...0.0... ...0.0...
..0.0.0.. ..0.0.1.. ..0.0.1.. ..0.0.1.. ..0.0.0..
.1.1.1.0. .1.1.1.0. .1.1.1.0. .1.1.1.0. .1.1.0.0.
1.1.0.1.1 1.1.0.1.1 0.0.1.1.1 0.1.0.0.1 0.1.1.0.1
....0.... ....0.... ....0.... ....0....
...0.0... ...0.0... ...0.0... ...1.0...
..0.0.0.. ..0.0.0.. ..1.0.0.. ..0.0.0..
.1.1.0.0. .1.1.0.0. .1.0.0.0. .0.0.0.0.
0.0.0.1.1 0.0.1.0.0 0.0.0.0.0 0.0.0.0.0
Ending at position 8
....1.... ....0.... ....0.... ....0.... ....0....
...1.1... ...1.0... ...1.1... ...1.1... ...1.0...
..1.1.0.. ..1.1.1.. ..1.1.0.. ..1.1.1.. ..1.1.0..
.1.1.1.1. .1.1.1.1. .1.1.1.0. .1.1.0.0. .1.1.0.1.
1.1.1.1.1 1.1.1.1.1 1.1.1.1.1 1.1.0.1.1 1.1.0.1.1
....0.... ....0.... ....0.... ....0.... ....0....
...1.0... ...1.0... ...0.0... ...0.1... ...0.1...
..0.0.1.. ..1.0.1.. ..0.0.1.. ..0.0.0.. ..0.0.0..
.1.1.0.1. .0.1.0.1. .1.1.0.1. .1.1.0.0. .0.0.1.0.
1.1.0.1.1 0.1.0.1.1 0.1.0.1.1 0.1.0.1.1 0.1.0.1.1
....0.... ....0.... ....0.... ....0....
...0.1... ...0.1... ...0.1... ...0.0...
..0.0.0.. ..0.0.0.. ..0.1.0.. ..0.0.0..
.0.0.1.0. .0.0.1.0. .0.0.0.0. .0.1.0.0.
0.1.1.0.0 0.0.0.1.0 0.0.0.0.0 0.0.0.0.0