Peg Solitaire Invariants

The peg solitaire (Hi-Q) is a game defined by moves where one can move a peg orthogonally over an adjacent peg to an empty peg while removing the peg that’s jumped over.

One can ask many question about the game, about the possible states that can be reached from a given initial state or about the algorithms to solve the standard board (with all pegs except the center filled initially), the fastest way to reach the end state, the different paths to the end state, the expected number of pegs left if the moves are completely random or if we follow a class of strategies etc.

One way to define invariants is to label the positions by coordinates, colors, numbers etc. We use the following coordinates to define some invariants.

Defining the state of the board using powers of a symbol p , where existence of peg contributes p^{x+y} we can get an invariant under the moves if the symbol satisfies 1+p =p^2 . That is

\displaystyle A= \sum_{(x, y) \text{Peg Positions} } p^{x+y}

is invariant under the moves. To see this note that each move corresponds to replacing two pegs at (x, y) , (x+1, y) with a peg (x \pm 2, y) or replacing two pegs at (x, y) , (x, y+1) with a peg (x, y\pm 2) .

\displaystyle B= \sum_{(x, y) \text{Peg Positions} } p^{x-y}

is another invariant.

The left right symmetry puts us in a mod 2 setting, and the symbol p: 1+p=p^2 corresponds to an extension of the the finite field \mathbb F_2 to \mathbb F_4 .

The two invariants (A, B) can take arbitrary values as we vary over different possible arrangements of the pegs. But the invariance says that only one of these 16 values appears throughout the game.

All the 16 possibilities are attained as above.

If we start with all the pegs except at center, we will have (A, B)=(1, 1) , and the only possible end states with a single peg at (a, b) will have to satisfy p^{a+b} =1, p^{a-b}=1 \implies (a, b) \in \left\{ (0, 0) , (0, \pm 3), (\pm 3, 0) \right\}
In fact, all these positions can be obtained. (We know that we can reach the center, then stop before the last move and moving away from the center in the last move gets you to one of 0, \pm 3), (\pm 3, 0). By symmetry all them have to be reached.)

There are other ways to prove this fact. We can try to 3-color the board as shown below and count the parity of pegs in each colour.

So if start with a hole at the center, and 32 pegs, there are 10 red pegs, 11 blue and yellow pegs, and after 31 moves, we have an parity change are left with odd number of red pegs, and even (0) number of blue and yellow pegs. So the final peg has to be in the red position. By symmetry or using coloring along the other diagonals, we can argue that final peg has to be in the symmetric red positions which is exactly what we got from the previous argument.

Questions to think about:
What initial configurations can reach a given end state?
Is it possible to complement a configuration (that is change from a peg to hole, and hole to peg)?
What are all the invariants of the moves? Do we have invariants that determine if we can reach from one state to other?
What happens on a differently shaped Solitaire? On a arbitary graph?

One the ordinary 33 solitaire board, we can always start with a configuration with a hole a some position and reach the complement state. But on a French board we cannot get to a complement state. (We can see this from the coloring and parity argument again)


References:
1. http://alexandria.tue.nl/repository/freearticles/598441.pdf
2. J. Beasley, The Ins and Outs of Peg Solitaire, Oxford Univ. Press, Oxford, New York, 1992.


Posted in $.

Leave a comment