On each table at the Cracker Barrel [1], there's this peg game [2]—a triangular piece of wood with 15 holes, 14 of which are filled with a golf tee. The object of the puzzle is to remove the golf tees by jumping one tee over another and removing the tee jumped over (much like making jumps in checkers) and end up with one tee.
I was never able to do that. Sure, I could reliably get three tees left. Occasionally two. But never one (and the one time I did that I did it backwards, starting with one tee and working the puzzle out backwards).
I even came across a computerized version [3] where I could waste my time only getting three pegs.
Sigh.
I remakred to wlofie a few months ago about writing a program to play the game and find a solution to the problem, and a few weeks ago I finally got around to writing the program.
I don't consider it cheating because one has to have an understanding of the problem to instruct a computer to solve the problem. And it's an interesting problem to find a representation that can be modelled in the computer. A typical representation would be to use a two dimentional array to represent the board but in thinking about it, the programming required to implement a move got rather hairy quickly.
It turns out that of the fifteen spaces, twelve only have two possible moves, and three four moves and here I was looking at a mountain of code to express this with a 2D array.
I quickly abandoned that and went for a more abstract representation of the board. In the new representation, it's a linear array of spots, labeled A–O, with each spot having a list of valid moves, which spot one jumps over and the destination. Each spot also has an flag denoting the presence or absence of a peg. From there, it was relatively easy to write the code [4] to play the game.
Also interesting to note is that, discouting rotations and reflections of the puzzle board, there are only four distinct solutions required.
Table: Peg Game Board—Bold spots represent unique position **A** **B** C **D** **E** F G H I J K L M N O
And the solutions?
Well … I'm not giving the answers away here …
[1] http://www.crackerbarrel.com/
[2] http://www.crackerbarrel.com/games-kids.cfm?doc_id=42
[3] http://www.ripleys.com/games/iq.html