The Peg Solitaire and its unbeatable games

In the previous post we considered a simple domino game where we needed to cover a board with dominos. We wanted to find a way such that if a board couldn’t be covered, then we could prove it easily, and this led us to the definition of the game invariants. These are “elements” that do not change as the game progresses, so if the initial and final state have different invariants, then we could not reach from one to the other.

In this post, we will deal with a new game – the Peg Solitaire – and see if and how we can find such invariants for this game.

The Peg Solitaire is quite an old game, which according to wikipedia was probably played by Louis XIV at the year 1697. The two main variants are the English version and the European version.

In this game we usually start with a board full with pegs except for one place. Then, at each turn, we need to choose 3 subsequent places where the first two have pegs and the third one doesn’t, and we can use the first peg, to jump over and “eat” the second peg, in order to reach the third empty place. Or, in a more formal way, if $X$ symbolizes a peg and $O$ a hole, then we can move from $XXO$ to $OOX$ (these can appear in the up, down, left or right directions).

The goal of this game is remove more and more pegs and eventually remain with a single peg, where the location of the initial hole and the final peg is determined by the variant of the game. In the English version, the initial hole and the final peg are usually at the same place (and in particular, you start with a hole in the middle and try to end with a peg in the middle). In the European version, the last peg should be in the place which is 180 degrees rotation of the initial hole. So for example, if the initial hole is on the bottom right, then the last peg should be on the top left. Our question now is, given a variant of this game, which can be one of the variants above, or more generally any given board with given initial and final state of pegs, can this game be won, and if not, is there an easy way to show it?

In the domino game in the previous post, our lives were much easier – we could add a domino piece in every place that had two subsequent “holes”. Also, we could easily analyze it for rectangular games, which gave us some intuition about how to continue to general games. Here the game is more complicated, and when dealing with a complicated problem, you should always look for the simplest variant of it which you can solve, and hope to get some intuition for the more general problem.

The one dimension Peg Solitaire

Let us start by thinking about a board with a single line, and ask which initial states of pegs can we solve in the sense that we can transform it using our rule above to a state with a single peg.

Even in this one dimensional board, and even with a single initial state, this is not a trivial manner. Just to see some examples of solvable games, instead of starting with an initial state and eating pegs, lets start with the final one peg state and create new ones by reversing the eating rule, namely the new rules are $XOO \to OXX$ and $OOX \to XXO$ . Also, for simplicity, we will consider two boards which are the same up to a translation to the right or left equivalent. So for example, from $OOXOO$ we can go both to $OOOXX$ and $XXOOO$ , and both of these are equivalent (by moving 3 places at the same direction). With this equivalence, the only solvable boards with at most 5 pegs are:

$OOXOO$

$OOXXOO$

$OOXOXXOO \;;\; OOXXOXOO$

$OOXOXOXXOO \;;\; OOXXOOXXOO \;;\; OOXXOXOXOO$

$OOXXOOXOXXOO \;;\; OOXOXOXOXXOO \;;\; OOXXOXOXOXOO \;;\; OOXXOXOOXXOO$
$OOXXXXOXOO \;;\; OOXOXXXXOO$

It already becomes quite complicated for 5 pegs, and it is not clear how to describe the solvable states. For example, while $OOXXOOXOXXOO$ is solvable, the state $OOXXOXOXXOO$ is not.

The hard question now is where to look for properties like we have in the dominos (parity, and the white\black counting) which are easier to compute, and are enough to show that some board are unsolvable.

If we try to use the same language for the dominos, then there we had the rule $OO\to XX$ . As it only affected two cells, we used the 2-periodic coloring (white and black) or equivalently the 2-periodic labeling with $\pm 1$ . In our case, the rules are $XOO\to OXX$ and $OOX \to XXO$ , so we should try to look for a 3-periodic coloring\labeling:

As can be seen in the pictures above, when we performed the step $OOX\to XXO$ , the red color loses one peg while the blue and green gain one peg each. This is not exactly the black and white situation that we had with the dominos, but we can say something about this coloring – the parities of the three colors change together. In the example above, we started with the (red,green,blue) parity of (even,even,odd) and moved to (odd,odd,even). Any step that we will take will move between these two triplets. In particular, we can never end up using our rules with a one peg on the red color, since its parity triplet is (odd, even, even), and the same with green peg, but we don’t get any information on finishing with a green peg.

As another example, the parity of

is (even,even,even). So no matter which steps we use we will always have either (even,even,even) or (odd,odd,odd), so we will never get to a line with a single peg!

Peg Solitaire labeling

In the dominos, we could interpret the white and black coloring property by labeling the cells with $\pm 1$ alternatively, and then the property translates to the zero sum over the covered cells (since each domino piece total sum is zero). This is the invariant of the game, since it doesn’t change as the game progresses. Can we do something similar here?

If we try to label by $(x, y, z)$ three consecutive cells, then keeping the sum invariant under the rule $XOO\to OXX$ means that $x = y + z$ , and this equation has of course many solutions. But while in the domino case we can only add a domino piece on given two consecutive cells, here we can use this rule, or its symmetry $OOX\to XXO$ . This second rule tells us that we also want that $x + y = z$ . Subtracting these two equations we get that $2\cdot y = 0$ , so that $y$ must be zero. Like in the domino case, we would hope to have a 3-periodic labeling, so it would look something like $... , x , y , z , x , y , z , x , ...$ . The same argument that we saw for the cells labeled by $(x,y,z)$ , can be done for the cells labeled by $(y, z, w)$ , hence $z$ must be zero also and similarly $x=0$ so that all the labels are zero. This is a valid labeling, and the sum of labels covered by the pegs never changes, but it also doesn’t give us any information – it is always zero!

Luckily for us, in this case, we have a way out. We wanted before that $2\cdot y=0$ and decided to take $y=0$ . However, we can instead take $2=0$ , or alternatively work in the field with 2 elements. Over this field $-1 = 1$ , so both of the equations above are equal to $x+y+z=0$ and they have exactly 4 solutions. The trivial solution $(x,y,z)=(0,0,0)$ that doesn’t help us, and the three solutions $(1,1,0), (0,1,1)$ and $(1,0,1)$ . These define for us three labeling (with elements in $\mathbb{F}_2$ ) which are basically the same up to a shift translation:

We can now use each one of these labeling to attach a number to each state by summing all the labels where there is a peg. Because we are working over the field $\mathbb{F}_2$ , this sum is either $0$ or $1$ . For simplicity, instead of working with 3 labelings, we can instead work with one labeling, but with values in $\mathbb{F}_2^3$ as follows:

For any peg state $M$ , let us denote by $\psi(M)$ the sum over this labeling. So if we have two pegs on red, one on green and none on blue, then

$\psi(M)= 2\cdot (0,1,1) + 1\cdot (1,0,1) + 0\cdot (1,1,0) = (1,0,1)$ .

We can now conclude, similar to the domino case, the following.

CLAIM: For every two states $M_1, M_2$ , if we can reach from $M_1$ to $M_2$ by using the rules $OOX\to XXO$ and $XOO\to OXX$ (and backwards), then $\psi(M_1)=\psi(M_2)$ .

For example, a board with 2 reds, 1 green and 0 blue pegs as mentioned above has the total sum $(1,0,1)$ which is the same as a board with a single green peg, so there is possibly a way to move from the first board to the second. However, a single peg on a red cell has total sum $(0,1,1)$ so we can never get to such a board (and similarly for one blue peg).

Finally, before going back to the original Peg Solitaire, you should notice that in our labeling in $\mathbb{F}_2^3$ , the third coordinate is always the sum of the first two coordinates (since we only see these values $(0,1,1), (1,1,0), (1,0,1)$ ). This means that if we know the first two coordinates we always know the third, so in a sense we can ignore it, and just consider the labeling:

If you learned some group theory, you are probably familiar with these values together with the addition modulo 2. These are exactly the three non trivial elements in the Klein four group.

The 2-dimensional Peg Solitaires

Now that we have done all the hard work for the one dimensional case, it is not that hard to extend it to the two-dimensional case. Starting with our labeling for each row, and trying to synchronize the different rows, we get the following labelings (or the same but with flipped diagonals):

You should now check that the sum over the initial state with one hole in the middle in the English version gives the value $(0,1)$ and in the European version the value $(0,0)$ (hint for doing the sum – any three consecutive cells sum to zero). The English version’s initial state has the same total sum as the state with a single peg in the middle, so it might be solvable (and it actually is solvable). However, in the European version, the value of each one peg state is not zero, so not only we cannot start from the European initial state and finish with a single peg in the middle, we cannot finish with a single peg anywhere!

More generally, any initial state of the European board with a single hole on a red cell will have a total sum of $(0,0)$ so it cannot be transformed to a board with a single peg. We can also flip the coloring (look at top-left to bottom-right diagonal) to get more impossible games. From what is left, we also get the if the initial hole is on a blue cell, then the final peg must be on a green cell (and vice versa).

Some final additive thoughts

Both in this Peg Solitaire game and in the domino game in the previous post, we managed to find game invariants which are very simple to work with and compute. More over, they were described as summation over labelings, which let us use even more tools and results (for example, us the structure of integers, integers modulo 2 and the abelian Klein group).

These sets and their additions are very simple, and we should always hope and look for such interpretation of the problems and the tools that we work with. However, even when we can’t use simple addition, there are still more ways to find game invariants, which we will see in future posts.