A recent posting to the Trifunc group invited the members to solve the Cracker Barrel puzzle.

Brian Adkins, the author of the challenge, posted a solution in Haskell. Here is my Clojure solution.

The game is played on a triangular board with 15 holes, labeled 0 through 14. Initially, 14 of the holes contain pegs, one hole is empty. The goal is to eliminate pegs by jumping over them. For a full explanation of the game, see the links cited above. My numbering scheme for the game board is similar to the one shown here, except that I number from 0 to 14 rather than from 1 to 15.

I represent moves by triples I call neighborhoods. Each neighborhood (for example [0 2 5]) designates the coordinates of three contiguous holes. Corresponding to the triple of coordinates is a triple of booleans denoting the presence/absence of pegs in the holes. If the triple of booleans is either [true true false] or [false true true], then a capture is possible, and the triple of integers unambiguously determines a legal move.

Though the **solve** and **solve-all** functions are mutually recursive, I did not bother to use a trampoline. Blowing the stack is not a danger here. The stack depth is proportional to the length of the game, and the maximum length for a game is thirteen moves.

Great to see a solution in another language David. You may want to post a note to TriFunc so that others can see it. The only reason I noticed it was due to a pingback on my blog post.

March 20, 2011 @ 1:59 pm