Why Some Peg Solitaire Puzzles Are Unsolvable

Some peg solitaire puzzles are unsolvable because every jump preserves a hidden colouring pattern on the board, so a starting position that sits in the wrong class can never shrink to a single peg. The best-known victim is the plus-shaped 37-hole board: fill every hole except the centre, and no sequence of jumps will ever leave just one peg ^[1].

This article explains that hidden pattern in plain language, then looks at what a study of peg solitaire puzzle design found about symmetric puzzles, unique solutions and the boards people play on ^[1].

Where does peg solitaire come from?

Peg solitaire is a one-player board puzzle. Pegs sit in holes, and a move is a jump: one peg hops over a neighbour in a straight line into an empty hole, and the neighbour is removed. The usual goal is to end with one peg, often in a chosen hole.

The puzzle dates from the late 17th century, and its arrival set off an early craze for puzzles ^[1]. More than three centuries later it is still a subject of mathematical research, as the paper discussed below shows ^[1].

The main source for this article is a paper on designing peg solitaire puzzles, published on 9 June 2017 in a journal of recreational mathematics ^[1]. Among other things, it counted solvable puzzles on several boards ^[1].

Which boards does the research cover?

The paper's results cover four boards that share the same jump rule but differ in shape ^[1].

The smaller plus-shaped board is the one most people know. Its classic challenge, the central game, starts with every hole full except the centre and ends with one peg in the centre. That game can be solved.

Why can the 37-hole board not be solved from the centre?

On the plus-shaped 37-hole board, the same challenge is impossible ^[1]. The reason is a property called the position class. When that board is full apart from its middle hole, it lands in exactly the position class of a board with no pegs on it ^[1]. The 37-hole hexagon board has the same problem ^[1].

An empty board obviously cannot become a board with one peg, because jumps never create pegs. A position in the same class as the empty board is stuck with the same class for good, so it cannot finish with one peg either. To see why classes behave like this, it helps to build one yourself.

How does a colouring argument work?

Imagine painting the holes of the board with three colours, say red, yellow and blue. Paint the bottom row red, yellow, blue, red, yellow, blue and so on from the left. Paint the next row up shifted by one place, starting with yellow, and the row above that starting with blue. The colours now run in stripes along one diagonal direction.

Now look at any jump. It always involves three holes in a straight line, side by side: the peg that jumps, the peg that is jumped over, and the empty landing hole. With this painting, any three neighbouring holes in a row or a column carry all three colours, one each.

After the jump, two of those holes have lost a peg and one has gained a peg. So the number of pegs on each colour changes by exactly one. Every colour count switches between odd and even at the same moment.

That gives a rule that no jump can break. Write down, for each colour, whether its peg count is odd or even. A jump flips all three at once. So the pattern of which colours agree with each other stays fixed for the whole game.

Repeat the painting with the stripes running along the other diagonal, and you get a second rule of the same kind. Together, the two rules sort every possible position into one of sixteen groups. These groups are the position classes. A short program that checked thousands of random positions and every legal jump from them confirmed that no jump ever moves a position into a different class.

What does that mean for a single peg?

A single peg leaves one colour odd and the other two even, in both paintings. An empty board leaves every colour even. Those two patterns are different, and flipping all three colours at once never turns one into the other. So a single peg and an empty board always sit in different classes.

On that larger plus-shaped board, a check of every hole confirmed that no single peg, wherever it stands, shares a class with the empty board. That is why the full board minus the centre, which does share that class, can never be finished ^[1].

On the smaller plus-shaped board, the same check shows the central game starting position shares its class with a lone peg in the centre, so the colouring does not rule it out. And indeed the central game can be solved.

Is being in the right class enough?

No. The colouring argument only proves that some puzzles are impossible. It cannot prove that a puzzle is possible. A position can sit in the right class and still be unsolvable, for example when a few pegs are stranded far apart. To know for sure, you need an actual solution or an exhaustive search, which is exactly what the counts in the paper provide ^[1].

Where else do colouring arguments appear?

Colouring and parity arguments are one of the most useful tools in puzzle mathematics, because they settle a question without checking every possible sequence of moves.

A closed knight's tour is a route in which a knight visits every square of a board exactly once and returns to where it started ^[2]. In graph language, it is a Hamiltonian cycle ^[2].

On an ordinary chessboard, a knight always lands on the opposite colour. A route that alternates colours and comes back to its start must use the two colours equally often. A board with an odd number of squares cannot split evenly, so it cannot have a closed tour. This matches a result from 1991: a rectangular board has a closed knight's tour except when both sides are odd, or in a short list of narrow cases ^[2].

A paper published on 9 May 2007 took the question into three dimensions, inside a cube ^[2]. In a cube a knight may have as many as 24 moves to choose from, compared with at most 8 on a flat board ^[2]. Even so, the two-colour parity argument still forbids a closed tour whenever the cube's side is odd ^[2].

For cubes whose side is 4 or more, a closed tour exists exactly when that side is even ^[2]. That includes the smallest such cube, with side 4, even though a flat board of side 4 has no knight's tour of any kind ^[2].

Peg solitaire uses three colours instead of two, but the logic is the same: find a quantity that every move changes in a predictable way, then compare the start with the goal.

What did the research find about symmetric puzzles?

Symmetric starting positions look neat on a board, so they make natural puzzles. The paper sorted symmetric positions into symmetry types and proved two results about them ^[1].

Theorem 1. Take the 33-hole board or the plus-shaped 37-hole board, and a symmetric start of one of the kinds the paper numbers 1 to 5 ^[1]. If that start can be solved at all, it belongs to the position class the paper labels A, and some solution ends with the last peg in the middle ^[1]. So a designer who finds such a solvable start gets a central finish as a bonus ^[1].

Theorem 2. Now follow any solution of the classic 33-hole central game ^[1]. None of the positions it passes through on the way has one of those numbered symmetries, and the most symmetry that can turn up midway is one mirror line ^[1].

How many symmetric puzzles can be solved?

The paper counted every solvable symmetric starting position on three of the boards ^[1].

These numbers show how much room there is for new puzzles. Even after limiting yourself to symmetric positions, each board offers somewhere between about ninety-five thousand and a hundred and sixty thousand solvable challenges ^[1].

Why are puzzles with a unique first jump so hard?

Symmetric puzzles have a weakness as brain teasers: a symmetric position usually offers several mirror-image first moves that are equally good, so the solver has many ways in. The paper took a different route: it hunted for starts in which every first jump but one leads to a dead end ^[1].

Those puzzles turned out to be much harder than symmetric ones ^[1]. A wrong first move cannot be repaired later, so the solver has to see far ahead from the very start.

A few of them go further and have a single complete solution from start to finish ^[1]. That is rare in peg solitaire, where a solvable position usually allows more than one way to finish ^[1]. For a puzzle designer, a unique solution is valuable, because it means there is exactly one idea to discover.

Is there a link between the start and the finish?

There is a pleasing symmetry in time as well as space. Swap every peg for a hole and every hole for a peg. The central game start on the smaller plus-shaped board, full except for the centre, becomes a single peg in the centre, which is the finish.

Because of this swap, a solution of the central game played in reverse order, last jump first, is also a solution of the central game. A short simulation of a complete solution confirmed this.

What can a solver take away from all this?

• Check the class first. Before spending an hour on a new board or a new starting hole, a colouring check can tell you if the puzzle is impossible.
• A right class is not a promise. It only removes one kind of impossibility.
• Symmetric puzzles are a good warm-up. On the 33-hole board and the plus-shaped 37-hole board, solvable symmetric starts of the types covered by Theorem 1 can always finish in the centre ^[1].
• Unique-first-jump puzzles are the expert level. The paper found them much harder than symmetric puzzles ^[1].

The wider lesson is that a simple rule can hide a firm limit. Spotting what never changes under a move is often faster than trying every move.

If you like reasoning about what alternates and what stays the same, try this logic riddle about gears turning one another: