Peg Solitaire
Here we'll look at some of the mathematics behind a cheap, commercially available peg solitaire puzzle.
Setup
There are a few popular peg solitaire boards, but the current cheapest is the triangular board.
Here are some purchase options:
For a budget option, here are some paper boards you can print in a couple different styles. (Note: This contains additional board types mentioned in the Extra Challenges.) Something like two-color counters can be used as pegs, but you might want to opt for something a little more tactile and tall, like game pieces.
The rules for the game are simple. You start with some number of the holes filled with pegs and the rest unfilled. Your goal is to end with a single peg. The way pegs are eliminated is via jumps: one peg may jump over a neighboring peg and into an empty spot immediately on the other side, removing the jumped-over peg from the game. Pegs can only move within lines parallel to the sides of the triangle and cannot jump over more than one peg per jump.
Challenges
Here are some interesting configurations to try to solve. Can you find a way to end with one peg remaining? What positions can you end that peg in?
1. |
 |
|
2. |
 |
|
3. |
 |
|
4. |
 |
|
5. |
 |
|
6. |
 |
|
7. |
 |
|
8. |
 |
|
9. |
 |
|
10. |
 |
Some of the configurations below can end with a single peg and others cannot. Can you tell which are which?
11. |
 |
|
12. |
 |
|
13. |
 |
|
14. |
 |
|
15. |
 |
|
16. |
 |
|
17. |
 |
|
18. |
 |
|
19. |
 |
|
20. |
 |
Notes
-
A nice initial question is whether a puzzle must eventually reach a dead end or if you can continue moving pegs forever. Since each jump removes a peg from the game and we cannot end with zero pegs on the board (what could jump over it?), if we start with \(n\) pegs on the board there can be at most \(n-1\) jumps before no more moves are possible.
-
If we number the positions of the puzzle as below
then here are the positions you can end in with a single peg, when possible:
Puzzle End Positions 1 1, 7, 10, 13 2 13 3 1, 7, 10, 13 4 1, 7, 10 5 1, 7, 10, 13 6 1, 7, 10, 13 7 1, 7, 10, 13 8 2, 6, 11, 14 9 3, 4, 9, 12, 15 10 13 11 - 12 1, 5, 7, 10, 13 13 1, 5, 7, 10, 13 14 - 15 13 16 - 17 - 18 5 19 - 20 13 -
A lot of the positions above get recycled. Why those positions in particular? There is a lot of symmetry to the triangle, so you can create rotations and reflections of the original peg arrangement that lead to other end positions.
You might notice that our end positions are always subsets of one of the following sets:
\[ \{1,5,7,10,13\}, \{2,6,8,11,14\}, \{3,4,9,12,15\} \]If we color these sets green (G), yellow (Y), and blue (B), respectively, here is that coloring side-by-side with our numbering:
The coloring has the property that any three consecutive positions in a line have three different colors. Any time a peg jumps another peg into an empty space, the way that we can think of the net effect on the positions is that we lose a peg in one of each of two colors and gain a peg in the third color. If we start with an initial tally of the pegs counting the number in each color, we can ask how it could look after some moves. For example, hypothetical move sequence might start something like this:
\[ (5B,3G,4Y) \, \rightarrow \, (5B,3G,4Y) + (-B,-G,Y) \, = \, (4B,2G,5Y) \rightarrow \, ... \]If ever two of the coordinates are \(0\), then we must be at a dead end. (We might otherwise reach a dead end if the pegs of different colors are two far apart to jump one another.) Ability to steer this triple towards \((B,0,0)\), \((0,G,0)\), or \((0,0,Y)\) by cleverly adding \(1\) to one coordinate and subtracting \(1\) from the other two would be a necessary condition to be able to end with a single peg in a blue, green, or yellow position, respectively.
-
A far more sophisticated way to use the coloring above is to assign each color a nonzero value in \((\mathbb{Z}/2\mathbb{Z})^2\). For example, we could assign \(B = (1,0)\), \(G = (1,1)\), and \(Y = (0,1)\), and consider addition coordinate-wise \((\textrm{mod } 2)\) (i.e. \(0+0 \, \equiv \, 1+1 \, \equiv \, 0\) and \(0+1 \, \equiv \, 1+0 \, \equiv \, 1\). (For convenience, we'll write \(0 = (0,0)\).) The addition table for \(\{0,B,G,Y\}\) looks like
\(+\) \(0\) \(B\) \(G\) \(Y\) \(0\) \(0\) \(B\) \(G\) \(Y\) \(B\) \(B\) \(0\) \(Y\) \(G\) \(G\) \(G\) \(Y\) \(0\) \(B\) \(Y\) \(Y\) \(G\) \(B\) \(0\) Under this arithmetic,
\[ 2B \, \equiv \, 2G \, \equiv \, 2Y \, \equiv \, 0 \] or, in other words, \[ B \, \equiv \, -B, \quad G \, \equiv \, -G, \quad Y \, \equiv \, -Y. \]Furthermore,
\[ B+G+Y \, \equiv \, 0. \]This means
\[ B-G-Y \, \equiv \, -B+G-Y \, \equiv \, -B-G+Y \, \equiv \, 0 \] so we can add (or subtract) any of \[ B-G-Y, \quad -B+G-Y, \quad -B-G+Y \] to an expression of the form \(bB + gG + yY\) for integers \(b,g,y\) without changing the value \((\textrm{mod } 2)\). This nicely reflects the fact that subtracting two different colors and adding the third happens in a legal move.Our clunky move sequence above becomes the algebraic maneuver
\[ \begin{align*} 5B+3G+4Y & \, \equiv \, 5B+3G+4Y + (-B-G+Y) \\ & \, \equiv \, 4B+2G+5Y \end{align*} \]It's also the case that
\[ 2B \, \equiv \, 2G \, \equiv \, 2Y \, \equiv \, 0, \]so we have
\[ \begin{align*} 5B+3G+4Y & \, \equiv \, 5B+3G+4Y + (-B-G+Y) \\ & \, \equiv \, 4B+2G+5Y \\ & \, \equiv \, 4B+2G+5Y - (2B + 2B + 2G + 2Y + 2Y) \\ & \, \equiv \, Y \end{align*} \]This suggests that if we can end with a single peg after starting with \(5\) blue, \(3\) green, and \(4\) yellow, the last peg standing could plausibly be yellow.
By design of our algebra on \(B,G,Y\), each expression of the form \(bB + gG + yY\) will reduce uniquely to one of \(0 = (0,0)\), \(B = (1,0)\), \(G = (1,1)\), or \(Y = (1,0)\). If it reduces to \(0 = (0,0)\), there is no shot at ending with a single peg. If it reduces to any of the others, then if it is possible to end with a single peg (which it might not be!), that single peg necessarily has the associated color, since a sequence of legal moves would be reflected by the algebra.
As an example, consider Puzzle 6. We have pegs in positions \(1-10\). Since \(\{3,4,9\}\) are blue, \(\{1,5,7,10\}\) are green, and \(\{2,6,8\}\) are yellow, our algebraic expression for this initial configuration is
\[ 3B+4G+3Y \]Doing a little algebra,
\[ 3B+4G+3Y \, \equiv \, 3B+4G+3Y - 3(B+G+Y) \, \equiv \, G. \]If we can end with a single peg, it must end in a green position. The possible end positions turn out to be \(\{1, 7, 10, 13\}\), which are indeed all green.
Puzzle 16 has algebraic expression \(3B+1G+3Y \equiv 0\), so cannot end with a single peg.
Note that these algebraic expressions don't encode everything about the board -- just the relative quantities of pegs on each color. Different board configurations can have the same quantities of pegs but have pretty different solutions.
Extra Challenges
-
One question that people have traditionally explored is the minimum number of moves required to solve a puzzle. As noted above, if there are \(n\) pegs, then \(n-1\) jumps are required to end with one peg on the board. However, if consecutive jumps with a single peg are all counted as a single move, this makes the question much harder!
-
The perhaps best-known peg solitaire puzzle is the cross or English board.
It's a little spendier, but here are some options:
For whatever reason, I've never seen a comparably cheap European board.
Here's one of the cheaper options:
A lot of the same questions and analyses can be carried out on these boards. I've included them in my handout for use with counters or game pieces.
This post was sponsored by the Julia Robinson Mathematics Festival 
Comments
Post a Comment