The Boston Diaries

The ongoing saga of a programmer who doesn't live in Boston, nor does he even like Boston, but yet named his weblog/journal “The Boston Diaries.”

Go figure.

Friday, March 18, 2005

That darned Peg Game

On each table at the Cracker Barrel, there's this peg game—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 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 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.

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 …

Obligatory Picture

[The future's so bright, I gotta wear shades]

Obligatory Contact Info

Obligatory Feeds

Obligatory Links

Obligatory Miscellaneous

You have my permission to link freely to any entry here. Go ahead, I won't bite. I promise.

The dates are the permanent links to that day's entries (or entry, if there is only one entry). The titles are the permanent links to that entry only. The format for the links are simple: Start with the base link for this site: https://boston.conman.org/, then add the date you are interested in, say 2000/08/01, so that would make the final URL:

https://boston.conman.org/2000/08/01

You can also specify the entire month by leaving off the day portion. You can even select an arbitrary portion of time.

You may also note subtle shading of the links and that's intentional: the “closer” the link is (relative to the page) the “brighter” it appears. It's an experiment in using color shading to denote the distance a link is from here. If you don't notice it, don't worry; it's not all that important.

It is assumed that every brand name, slogan, corporate name, symbol, design element, et cetera mentioned in these pages is a protected and/or trademarked entity, the sole property of its owner(s), and acknowledgement of this status is implied.

Copyright © 1999-2024 by Sean Conner. All Rights Reserved.