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/
Search the Dr. Math Library:
Ask Dr. MathTM
© 1994-2013 The Math Forum