Peg Solitaire

... Or, How To Lose Your Marbles

As a messenger for my Dad's advertising agency, when not ferrying artwork and ad copy from office to office over the streets of downtown Pittsburgh, I spent a lot of time trying my luck with a woodcrafted peg solitaire game ... a game which I never won over a two-year period.

Peg Solitaire, familiar to many as the "Hi-Q" board game by Pressman Toy, Inc., is a board of 32 pegs (33 holes) arranged in a cross (see the diagram to the right). At the start of the game, all but the middle hole has a peg. On each move you jump one peg over another to a vacant hole (up, down, left, or right ... no diagonal moves are allowed). The peg you jump over is removed from the board. A "win" occurs when you end the game with one peg left in the middle hole.

A winning game of Peg Solitaire on the English board.

Time goes by and when I received a really nice Solitaire game this past Christmas (from Bombay Company, the board uses large multi-colored marbles instead of pegs), I felt ready to tackle it again. My profound sense of mathematics being what it is, my first approach was a depth-first algorithm like the one used in the Scramble Squares problem.

... which was a fairly colossal waste of time. The resulting C program generated solutions ... thousands of them thanks to the boundless symmetry of the board ... but it became apparent that it was unlikely to stop running in my lifetime. The problem seemed so ... well ... bounded. On any given turn there are only a few available moves, and a peg or marble disappears with each turn, so it should quickly simplify, right? Right? Wrong. If there are about three possible moves on any given turn (it's often more ... sometimes as high as nine) then there are 331 combinations, and we've been through all that math before ... more than 617 trillion combinations to process.

Changing the objective from "find ALL of the solutions" to "find ANY solution" invited a new approach based on a simple genetic algorithm (GA) . Starting from a population of 100 random walks through the game, and creating new attempts in each generation from random variations in any of the top ten scores from the previous generation, a "winning" game is almost always discovered within 2,000 generations.

A winning game of Peg Solitaire on the French board.

Closer inspection of the new game from the Bombay Company revealed a different problem ... the board wasn't the same as the standard Hi-Q board! Four extra pegs (marbles) had been added at the internal vertices.

After some feverish Googling, I learned that the Bombay set is based on the French or Continental version of the game. After adapting the GA to deal with the change in the shape of the board, I discovered that the best I could ever do was to end with two marbles if I started with the middle space empty.

Further research revealed everything from speculation that the French game had, at one time, allowed diagonal moves, to actual mathematical proofs that a single peg in the middle was an impossible result when starting with the middle peg empty on a Continental board. For a reasonable substitute, I discovered that it was possible to start with the upper left slot empty and end with a single peg in the lower right slot. When provided with this task, the GA finds the one peg solution in about 1,600 generations, although it takes over 5,000 generations to get the desired solution. (Less than a minute of processing time in any case.)

For the GA, the data structure for the board at any given stage of the game uses a 49 character string ('-' for cells in the 7x7 grid not in use, '1' for cells with pegs, and '0' for cells that could hold a peg, but currently do not.

But staring at long strings of dashes, ones, and zeros is not appealing, so I created this perl script to translate the sequence of moves represented by the strings of '-' and '1' and '0' into a graphical representation of the board. A shaded circle represents a peg or marble, and an unshaded circle is a slot that could take a peg, but currently has none. The black arrow indicates the peg to be moved and points in the direction the jump will take place (in the script I use compass directions of East, North, West, or South.)

The perl script uses the PerlMagick module from ImageMagick to create the images and the animation. ImageMagick is an open source graphics toolkit, that is surprisingly powerful but suffers from user-hostile documentation.

The same perl script is adapted to provide the tables that follow, detailing the steps of the two winning games animated above.

Move 4 from the winning game on the English board shown above .
Game A: English Board
Game starts with all but the center hole filled, and ends with one peg remaining in the middle hole.
Move #
Start Row
Start Column
Move Direction
1
2
4
South
2
3
2
East
3
5
2
North
4
5
4
West
5
7
4
North
6
5
1
East
7
4
4
West
8
4
1
East
9
5
4
West
10
3
1
East
11
7
3
North
12
3
4
West
13
5
2
East
14
5
5
West
15
7
5
North
16
3
6
West
17
1
3
South
18
4
3
North
19
1
5
West
20
5
6
West
21
5
3
East
22
5
5
North
23
3
4
East
24
3
7
West
25
1
3
South
26
3
2
East
27
3
4
East
28
5
7
North
29
3
7
West
30
2
5
South
31
4
6
West


Game B: French (Continental) Board
Game starts with all but the upper left hole filled, and ends with one peg remaining in the bottom right hole.
Move #
Start Row
Start Column
Move Direction
1
3
3
North
2
2
5
West
3
1
3
South
4
1
5
West
5
4
3
North
6
6
3
North
7
4
5
North
8
5
1
East
9
4
3
South
10
3
7
West
11
2
6
West
12
5
7
North
13
5
6
North
14
3
1
East
15
5
4
East
16
3
4
West
17
1
3
South
18
3
2
East
19
3
5
West
20
3
7
West
21
7
4
North
22
7
5
North
23
6
2
East
24
5
4
North
25
6
6
North
26
4
1
East
27
4
3
North
28
3
4
North
29
2
2
East
30
1
4
South
31
3
4
East
32
3
6
South
33
5
6
West
34
5
4
South
35
7
3
East

 

 


 
Copyright 2006 Mark Van Dine, All Rights Reserved