Peg Solitaire

Pef Solitaire written in C using Raylib.

Dependencies

Make sure Raylib is installed. For example, on Arch:

sudo pacman -S raylib

Build

To compile the code:

./build.sh

Run

To run the game:

./solitaire

• Left click a peg to select it, then left click the hole into which the selected peg is to be moved.
• A peg can only move horizontally or vertically.
• A moved peg must jump over a single directly adjacent peg.
• The jumped peg is removed from the board.
• The aim is to finish with only one peg remaining. And for a perfect game, finish with the final peg in the centre of the board.

You can reset the board to the initial state by presssing R.

There is an auto-solve mode which can be activated at any point by pressing S. This will shift the program into a thinking phase, where an attempt is made to find a solution using a depth-first search. The length of time required to complete this task is dependent on the starting board state, but it typically takes a few seconds. Once a solution is found, the game will transition to a soliving phase, where the solution is automatically played out, one step at a time, until completion.

A couple of techniques are used to improve the performance of the auto-solver:

• A cache of "dead-ends" is maintained. This ensures the auto-solver doesn't waste time trying to find a solution from a board state that is already known to be a dead-end.
• The cache stores a "canonical" version of each dead-end board state. The canonical version is defined as the smallest bit representation of all eight "symmetrically identical" versions of the dead-end state. This approach increases the number of distinct states that can be stored in the cache. It works, because if the current board state is a dead-end, a rotated or mirrored version of the board is also a dead-end.

The optimisations are needed as there over 577 quintillion distinct possible jumps from the initial board state!

God luck!