Triangle Peg-Board Game

Some area restaurants have these peg-board games to keep you occupied while waiting for your food. The classic version of this game is a triangle shape which holds maybe 12 pegs, I think…not sure off-hand. One hole is left open, and you must jump over a neighboring peg into an open hole to remove the jumped peg. My wife has solved it several times without really watching what she’s doing. I think I solved it only once. If you know this game to which I refer, do you know the secret to solving it? - Jinx

I learned it once and then it was so long before I went back to one to these restaurants that I forgot. I’m sure there is more than one solution. And by the way, why not say it is The Cracker Barrel?

Because before a restaurant prentending to be “down home” used it, those “peg games” were/are pretty common among Mom and Pop Diners through the South and West.
-PSM

Could there be more than one approach to the solution of leaving one peg standing? I’ve wondered about this myself, and if there were a mathematical way to prove it. If there is one solution, it just feels like you should have to leave one of the more centrally-located holes open…just a WAG.

And, no, actually…it wasn’t The Cracker Barrel chain, afterall, but I guess they have 'em, too. You got the picture… - Jinx

Friendly’s has that game around here

Here’s a solution from one site. You have to scroll down a little to find the triangle version of the game. Only one solution is listed, but I don’t know if that precludes variants.

Also, here is another site which seems to have an on-line version of this game, if you want to practice the solution to wow your wife next time around.

I don’t have a proof, but this looks a lot like the Hamiltonian path problem (given a set of points and a set of connections between those points, is there a way to visit every point exactly once?). If a generalized version of the game is sufficiently similar to the Hamiltonian path problem (not gonna explain that one unless I have to), it’s very hard to find a solution. My guess is that the uniqueness of the solution depends on where the hole is at the beginning of the game.

OK, I was correct in that the generalized version of the problem is hard to solve, although I haven’t had a chance to look at any papers regarding this. If you’re curious, do a google on “generalized hi-q np-complete” and check the first few results.

I still don’t know that the solution is unique, but I’d be willing to bet that it is unique if it exists. The factor besides the position of the hole at the beginning is where you want the remaining peg to end up.

I just downloaded the game from ShibbOleth’s link; at the start of the game, you choose which piece to remove. It also has a button that tells you at that point whether the game is solvable from that position. According to the game, the game is solvable from any position (makes you wonder why they put the button there in the first place). Anway, since there are really only four different starting positions, we know there are at least four distinct solutions, (assuming the game is correct about this, which I don’t know).

Since there are very few moves at any given turn, it should be pretty simple to write a program to check all possible games.

D’oh, I just realized the button on the game works throughout the game, not just for the starting position; that’s what they put the button there for! :o

Anyway, either writing some code or playing with this game, it shouldn’t be difficult to find all solutions (I’m not saying I’m gonna do it, though ;))

I played the Java version listed by ShibbOleth, took the corner piece off and won on first try. So…

  1. When I got down to two pieces, I could jump in either of two ways, ergo no unique solutions for this starting point. In fact, since the generalized version is NP-Complete, there must be an exponential number of solutions for most solvable cases. (For the True Geeks out there.)

  2. As to the OP, Jinx. Some heuristics: keep the remaining pieces clustered together. Focus on clearing out the corners early, avoid having most in a line.

There is some stuff about this category of games in the rec.puzzles FAQ. Look up Hi-Q and Think-and-Jump.

Last year, I thought up and wrote a computer program that solves this game. Using simple game tree traversing, I found many solutions.

(I started with each of the 15 different holes being open at the beginning of the game.)

Many solutions arrived at were mirror images or rotations of each other, but there were just as many functionally different solutions.

Unfortunately, I did this on my work computer, which is now unaccessable to me. :frowning: But I’m sure I could recreate it if I get a few free hours.

<gunther-toody>Oo! Oo!</gunther-toody>

I found some version of the program I was talking about. If I remember what it’s telling me, there are 1550 solutions to the peg game starting with the middle hole of the 3[sup]rd[/sup] row being empty.