Peg Solitaire

Date: 04/19/2003 at 17:23:58
From: Nathan Reynolds
Subject: Peg Solitaire

There is a game called Peg Solitaire, Marble Game, etc. It is played 
on a board with a fixed number of holes and some pegs. The starting 
board looks like this:

    x x x
    x x x
x x x x x x x 
x x x o x x x
x x x x x x x 
    x x x
    x x x

There is a hole at the center. The object of the game is to jump pegs 
as in checkers, but horizontally or vertically instead of diagonally. 
For example, on the board above if the only top peg that can jump 
does so, the resulting board will appear.

    x x x
    x o x 
x x x o x x x
x x x x x x x
x x x x x x x
    x x x
    x x x

There is a solution to this game that can be found quickly by a 
computer.  

If have a particular board setup, how would I prove that a solution 
exists or does not? A computer could iterate through all of the 
possible combinations, but for larger boards this could take a long 
time if no solution exists.

I have written a computer program to do a depth-first search in the 
state space of the board. For the board setup above it finds the 
solution very quickly: 20,000 moves. For the following board setup, 
this program has looked at 400,000,000,000 (400 hundred billion) 
moves and it still doesn't have a solution. Obviously, it has looked 
at several board setups more than once.

The board setup...

    x x x
  x x x x x
x x x x x x x 
x x x o x x x
x x x x x x x
  x x x x x
    x x x

Now, the question is for any board, not just this one.

Date: 04/20/2003 at 08:14:11
From: Doctor Jacques
Subject: Re: Peg Solitaire

Hi Nathan,

Let us imagine we color the squares in three colors (red, green, 
blue) in such a way that squares of the same color line up in 
diagonals:


  R G B R G B...
  B R G B R G...
  G B R G B R...

and let g, r and b be the number of pegs on the corresponding colors.

Note that every move involves three adjacent squares of different 
colors. For example:

  +---+---+---+
  | R | G | B |
  +---+---+---+

Assume there are pegs in the R and G square, and that the B square is 
empty. We can jump the R peg over the G square, and put in in the B 
square.

Before the move, we had a peg in the R and G square, and no peg in 
the B square. After the move, we have the opposite situation.

This means that r and g have decreased by 1, and b has increased by 
1. The parity of each of the three variables has toggled: if r was 
even, it becomes odd, and so on.

At the end of the game, there is only one peg left. If it is on a red 
square, for example, we have r = 1, g = b = 0. In general, one of the 
variables is odd and the other two are even.

If now we trace the moves backward, as all three parities change for 
every move, the only possible combinations are (1 odd, 2 even) and 
(2 odd, one even).

So, if you are given a starting position, you should count the number 
of pegs on the three colors. If all three numbers are odd, or if all 
three numbers are even, there is no solution. However, the converse 
is not true (you can imagine 3 pegs on different colors and very far 
apart, so that no move is possible). If the three numbers do not have 
the same parity, you can still say that, IF there is a solution, the 
last peg will be on the color that has a different parity.

There is a much deeper analysis of that game in the following book:

  R. E. Berlekamp, J. H. Conway, R. K. Guy
  Winning ways for your mathematical plays

Does this help?  Write back if you'd like to talk about this more, or 
if you have any other questions.

- Doctor Jacques, The Math Forum
  http://mathforum.org/dr.math/