Recently I was given a puzzle like the kind that Cracker Barrel sells: You have a triangular board of holes filled with pegs (except for one). You then jump one peg over another into an empty space, removing the peg that was jumped. The goal is to perform the proper sequence of jumps such that you're left with one peg.

Cracker Barrel puzzle

I fiddled with it for a little while but didn't find a solution. In the end, I decided it would be fun to write a little C program to solve it for me!

Broadly speaking, the program generates a tree of possible board positions where a node's children are those board positions one peg jump away. As soon as a board is generated consisting of a single peg, we have success.

I made two struct types, a Board which contains an int array representing whether each space had a peg or not as well as a pointer to the parent position. The idea is once you have a winning board, you can follow the chain of parents back to the starting position to see the proper sequence of jumps. I also made a Node struct, which the program uses to keep track of board positions it still needs to examine. A Node has a pointer to its own Board, as well as a pointer to the next Node in the list.

The rough algorithm is as follows: