The Games and Puzzles
Journal — Issue 36, NovemberDecember 2004

Back to: GPJ Index Page —
Sections on this page: —
Introduction —
Maximal Sweeps on Odd Triangular Boards —
Maximal Sweeps on Even Triangular Boards —
Long Sweeps on Arbitrarily Large Boards —
Short Solutions —
End
Triangular Peg Solitaire Unlimited
by George Bell  December 2004
Introduction
Peg solitaire on a 15hole triangular board is an old puzzle but it remains popular.
In the United States, one can find these puzzles at tables in
"Cracker Barrel" restaurants.
The 15hole puzzle is also amenable to exhaustive computer search
and this is a common programming assignment for computer science classes.
Here we consider peg solitaire on an (equilateral) triangular board with
n holes on each side.
This board will be referred to as Triangle(n)
and can be conveniently presented on an array
of hexagons (figure 1).
The Triangle(n) board
has T(n)=n(n+1)/2 holes,
where T(n) is the n'th triangular number.
The notation used to identify the holes in the board is shown in figure 1—it differs
from that given in Beasley [Ref. 1] and is based on the system for square lattice boards.
A nice property of this notation is that the top corner hole is always "a1".
Figure 1 — The general triangular board with hole coordinates

The rules of the game are simple: start from a board with a peg in every hole but one,
then jump one peg over another into an empty hole, removing the jumped peg
from the board. The goal is to choose a sequence of jumps to finish with one peg.
This general problem of going from a board position with one peg missing to
a board position with one peg will be referred to as a peg solitaire problem.
The special case where the missing peg and final peg are in the same board location
is referred to as the complement problem.
GPJ Issue #28
considered peg solitaire on boards based on a square lattice.
Triangular peg solitaire differs in that the holes are based on a triangular
lattice, with a maximum of 6 jumps available into any hole (rather than 4).
However the theory of the game (in particular the fundamental classes)
is very similar see [Ref. 1],
or [Ref. 3] for details.
Any solution to a problem on the 15hole triangular board consists
of exactly 13 jumps because we start with 14 pegs and
finish with 1.
However, when the same peg jumps one or more pegs, we call this
one move.
Given a particular peg solitaire problem,
one can ask what is the solution with the least number of moves?
While this question has historically played an important role in
peg solitaire on the standard 33hole crossshaped board,
it has barely been considered for triangular boards.
The following terminology is used in referring to moves involving multiple
jumps: when a peg removes i pegs in a single move, we refer to it
as a sweep, or more specifically, an isweep.
After attempting a peg solitaire problem,
many people get the idea to try to solve it
backwards from the final peg.
What is not so obvious is that this is exactly the same
as the original game, where the concepts of "hole" and "peg" are interchanged.
In fact the solution to any peg solitaire problem really contains two solutions:
the original ("forward" solution) plus this "backward" solution,
where the individual jumps are executed in the same direction, but in reverse order,
and the starting vacancy and finishing location are swapped.
An important observation is that when an isweep is reversed,
we must reverse the individual jumps, and it becomes i single
jump moves.
In other words, sweeps in forward solutions cannot be sweeps in
reversed solutions (and vice versa).
Backward play is hard to comprehend, because our brain does not easily
interchange the concepts of "hole" and "peg".
It is easier to understand "backward play" by realizing that it is the
same as forward play from the complement of the current board position
(the complement of a board position is where we replace every hole by a peg, and vice versa).
This leads to a theorem used extensively in the remainder of this paper.
Suppose we have a board position B and we wonder if it could occur
in the middle of a solitaire game.
Forward/Backward Theorem: Board position B can appear during a solution to
a peg solitaire problem if and only if both
 B can be reduced to a single peg (the finishing location)
using peg solitaire jumps.
 The complement of B can be reduced to a single peg (the starting location)
using peg solitaire jumps.
A proof of this theorem just boils down to the equivalence of
playing the game forward or backward.
It may seem obvious, but is key to understanding
how to reach complex sweep positions.
A practical problem that arises is finding a triangular board to play on.
Fifteen hole Triangle(5) boards are quite common, but cannot be easily extended
to larger triangular boards.
The best board I have found is a Chinese Checkers set, which allows one to
play on boards as large as Triangle(13).
To help follow the arguments below, I recommend
playing out the solutions on a Chinese Checkers set.
This is particularly helpful to see solutions played forward and backward.
Maximal Sweeps on Odd Triangular Boards
Triangular boards support the longest sweeps
of any peg solitaire board.
This is because from any board location the total number
of possible jumps is even.
If the board size n is odd, there exist sweeps that jump into
or over every single location on the board.
Such sweeps are maximal in the sense that they are
the longest sweep geometrically possible on the board.
The figure below shows examples of the first three maximal sweeps
Figure 2 — Maximal Sweeps on
Triangle(3), Triangle(5) and Triangle(7)
Note: these sweeps are shown starting and ending at a1.
The sweeps can obviously begin and end at other board locations.

The length of this sweep is
3T((n1)/2)=3(n²1)/8.
Related geometrical tours on a triangular lattice have appeared in
GPJ #20 under
"Trapezoidal Tours".
As these sweep patterns become larger and larger, how can we
be sure a peg can traverse the entire pattern?
If we consider the pattern of the sweep as a graph,
one of the most elementary theorems in graph theory, due to Euler,
ensures that such a traversal is always possible when there are at most two
nodes of odd degree. Since maximal sweeps have all nodes of even degree,
they can always be traversed,
and the starting and ending board locations must be the same.
This theorem also guarantees that the more complex sweep patterns seen later
can be traversed.
Note that the sweep length divided by the board size approaches 3/4 as
the board size increases.
If this sweep is the final move to a solitaire game it removes nearly 3/4 of the pegs
that we started with in one move!
But can these maximal
sweeps be realized during a solitaire game?
If we take the complement of the sweep pattern, not a single jump is possible.
Thus, by the forwardbackward theorem, maximal sweep patterns cannot appear in
solitaire games on odd size boards.
Maximal Sweeps on Even Triangular Boards
The same maximal sweep on an odd triangular board is also maximal on the even board
one size larger, because the added row cannot be reached to extend the sweep.
However, the added row can make it possible to reach the sweep position during
a peg solitaire game.
On the Triangle(6) and Triangle(8) boards this can be worked out by hand,
figure 3 shows this process on Triangle(6):
Figure 3 — Constructing a solitaire solution that finishes with the 9sweep to a1
(a) Backward: playing from the complement of the sweep pattern to c5.
(b) Forward: The final solution from the c5 vacancy ending with a 9sweep to a1.

The forward solution in figure 3b has only 9 moves.
In the final section of this paper, we
prove that it's impossible to solve this problem in fewer than 9 moves.
Thus, besides containing a maximal length sweep, the solution of figure 3b solves
the problem in the minimum number of moves.
There are three problems on Triangle(6) that can contain a 9sweep:
 Vacate c5, play to finish at a1 with the last move a 9sweep (figure 3).
 Vacate c5, play to finish at a4 with the last move a 9sweep.
 Vacate c5, play to finish at a4 with the second to the last move a 9sweep.
The reader is invited to solve problems 2 and 3.
As in figure 3, the trick is to figure out what the final sweep must look like,
and then solve backwards (playing forward from the complement of the sweep position).
Then exactly reverse the jumps in your "backward" solution and you will
reproduce the sweep position.
On Triangle(8), the 18sweep can also be reached.
There are also three problems on this board that can contain the 18sweep:
 Vacate c5, play to finish at a1 with the last move an 18sweep (figure 4).
 Vacate b6 or e6, play to finish at c8 with the last move an 18sweep.
 Vacate c5, play to finish at b6 with the second to the last move an 18sweep.
These problems are more difficult than those on Triangle(6),
but are still quite reasonable to work out by hand.
Figure 4 shows the solution to the first problem, played forward.
This solution was discovered, as usual, by attempting to play backward from
the complement of the sweep position.
This solution contains 15moves, but it is possible to solve this problem
in 14 moves (without the 18sweep), so this solution does not have
the minimum number of moves.
Figure 4 — A 15move solution to problem #1 on Triangle(8) (finishing with an 18sweep)
Note: more than one move is sometimes shown between board snapshots.

On Triangle(10), a computational search for a peg solitaire solution containing a
maximal 30sweep has come up empty
(although a solution was found which ends with a 29sweep).
Triangle(12) does not appear to have a maximal 45sweep solution either.
I haven't checked all possible configurations of this 45sweep, but my program
has shown the most obvious candidates can't be reached from a single vacancy start.
Currently, it appears that the Triangle(8) board is the largest triangular
board for which a solution to a peg solitaire problem can contain a maximal sweep.
Long Sweeps on Arbitrarily Large Boards
Although maximal sweeps appear not to be attainable in peg solitaire problems
on large triangular boards,
it turns out sweeps of only slightly reduced length are possible.
A very special solution was discovered by hand on the 78hole Triangle(12) board.
This solution finishes with a 42sweep when run forward, and is shown in figure 5:
Figure 5 — Constructing a solitaire solution that finishes with the 42sweep
(Inductive Component A)
(a) Forward: the finishing 42sweep (starting at a1 and ending at a3)
(b) Backward: showing how to reduce the complement of the sweep pattern to one peg
Note: more than one move is sometimes shown between board snapshots.

This solution is remarkable because it can be extended to even larger triangular boards.
We can extend the final sweep to cover the bottom of Triangle(14) and the
complement can still be reduced to a single peg.
We do this by keeping moves along the bottom row the same,
while extending other moves vertically.
In particular moves 1&2 end at the same board locations but begin
from the bottom row of the board. The Ushaped moves 9 & 10 become vertically
elongated, but have the same starting and ending board locations.
Finally additional moves need to be added after move 11 to
reduce the remaining pattern of pegs to a single survivor
(which does not end up at the same location as in figure 5b).
We can continue stepping the board size up by 2 and still reduce the
complement to a single peg up to Triangle(20).
However if we try this on Triangle(22), we find we can no
longer reduce the remaining pattern to a single peg.
As the board is extended, the middle of the lower portion of the board
becomes similar to the original problem on Triangle(12).
This key insight suggests we may be able to perform an inductive step,
and extend the board indefinitely.
This is in fact possible, and will be described below.
In effect we can construct solutions to peg solitaire problems on
triangular boards of arbitrarily large size.
Not only that, these solutions finish with arbitrarily long sweep moves!
Figure 6 — Fitting the inductive components together to make a long finishing sweep on Triangle(24)

To complete the inductive step, we add another solution for
Triangle(12) underneath the first one to obtain a
solution on the 300hole Triangle(24) board.
Figure 6 shows the overall geometry of the solution; we use
"component A" (figure 5b) in the upper part of the board and
"component B" (figure 7) in the lower part of the board.
In the reversed solution, the remaining (white) areas of the board
are cleared by extensions of the moves to clear A, and the final move
snakes down vertically through both A and B to the bottom of the board.
The final sweep pattern will be close to the maximal sweep,
but component A contains a "defect" in this sweep pattern, and so
must component B. Figuring out exactly where to place this defect
in component B is critical to making everything work out.
At first I tried putting the defect symmetrically over the yaxis
of the board, but this never seems to work out.
What did work was to put it slightly off center.
While component A can be considered a solution itself on Triangle(12),
component B is inherently tied to the board above it, for there must be
moves which link the two boards.
Figure 7 shows how to solve component B, which looks very similar to component A.
Note, however, that the Ushaped moves actually go in the opposite direction from
before.
The entire solution is constructed to enable the final move to pass
vertically down the board.
Figure 7 — Inductive Component B
Backward: showing how to reduce the complement of the sweep pattern to one peg
The top two holes (green) are part of the board above.
Note: more than one move is sometimes shown between board snapshots.

The final sweep pattern always starts at a1 and finishes at a3.
The initial vacancy, or final peg for the reversed solution is
always directly under a3 on the lowest row that has a hole in
vertical alignment with a3 (on Triangle(24), this starting vacancy is at k23).
The entire solution on Triangle(24), when executed in the forward direction,
has a final move which is a 191sweep (figure 8):
Figure 8 — Forward: the finishing 191sweep on Triangle(24)
This sweep pattern is the maximal 198sweep with 2 "defects".

By stacking additional copies of component B under the diagram of Figure 6,
we can extend this process indefinitely.
The net result is that on Triangle(12i),
we can construct a solution to a solitaire problem
that finishes with a sweep of length
54i²  13i + 1
(this is 4i1 shorter than the the maximal sweep length).
The board itself has
72i² + 6i
holes, so asymptotically
this finishing sweep removes 3/4 of the pegs on the board.
The forward solution consists of
18i² + 19i  3
jumps, followed by the final sweep move.
By reordering a few jumps,
we can reduce the total number of moves in the forward solution slightly to
18i² + 15i  2.
The table below shows some statistics on these solutions as the board size increases:
i 
Board 
Board Size (# Holes) 
Final Sweep Length (# Jumps) 
% of Pegs Removed By Final Sweep 
Forward Solution Length (# Moves) 
1 
Triangle(12) 
78 
42 
55.3% 
31 
2 
Triangle(24) 
300 
191 
64.1% 
100 
3 
Triangle(36) 
666 
448 
67.5% 
205 
10 
Triangle(120) 
7,260 
5,271 
72.6% 
1,948 
Although this construction technique has given us solutions on boards with sides
a multiple of 12, it is not hard to extend it to Triangle(n)
for any even n>10.
The way to do this is using the same technique we used to extend component A
on Triangle(12) to Triangle(14), Triangle(16), etc.
Short Solutions
Given a board and a (solvable) peg solitaire problem,
what is the least number of moves that can solve it?
While this question has been important in the history of the standard 33hole
crossshaped board, it has not received much attention on triangular boards.
Informally, this question can be rephrased: "What is the solution which involves
touching the smallest number of pegs?"
In 1966, Harry O. Davis studied short solutions on the Triangle(5)
board analytically [Ref. 2].
He was able to find minimal solutions "for all starting locations"
and prove that his solutions were the shortest possible.
In particular, he found a 10 move solution to the a1complement,
and proved that the problem could not be solved in less than 10 moves.
I have now completed exhaustive computer calculations on all peg solitaire
problems on boards up to Triangle(7), and I have completed runs of
all complement problems on Triangle(8). The table below summarizes my results,
for more information with examples and complete lists of shortest solutions
see [Ref. 3].
Because these results come from complex computer calculations
(especially for the Triangle(8)), it remains a possibility (however remote) that due
to some bug my program has missed a shorter solution.
My program has been tested extensively on the English 33hole board, and the results
agree with that found by others. My results on Triangle(5)
agree with those of Harry O. Davis.
However, my results for larger boards await independent confirmation.
Board 
Total Holes 
Peg Solitaire Problems 
# Problems with Minimal Solution Length 
Total 
Solvable 
9  10  11  12  13  14  15 
Triangle(5) 
15 
17 
12 
2 
6 
4 
 
 
 
 
Triangle(6) 
21 
29 
29 
16 
11 
2 
 
 
 
 
Triangle(7) 
28 
27 
27 
 
 
 
19 
8 
 
 
Triangle(8) 
36 
80 
80 
 
 
 
 
1 * 
5 * 
2 * 
(*) Complement problems only

In the above table, we count only distinct peg solitaire problems that
cannot be reduced to another problem by means of rotation or reflection of the board.
For example, on the Triangle(5) board, the table indicates that there are 17 distinct peg
solitaire problems, but only 12 are solvable. Of these 12 solvable problems, 2
can be done in a minimum of 9 moves, 6 in 10 moves and 4 in 11 moves.
Surprisingly, over half the problems on the Triangle(6) board can be solved in 9 moves,
so on average, it's possible to solve problems on this board in fewer
moves than for Triangle(5)!
There are 80 different problems on Triangle(8), I have only
run the 8 complement problems plus a few noncomplement problems.
Among the complement problems, only one can be
accomplished in 13 moves, the a7complement (figure 9)
[due to board symmetry, this problem is equivalent
to the complement problem at 5 other board locations: a2, b2, b8, g7 or g8].
The computer run also determined that this 13move solution is unique
in the sense that any other 13move solution to the a7complement must contain
the exact same set of jumps, although not necessarily in the same order.
I have found several other 13move solutions to noncomplement problems
on the Triangle(8) board, and it is possible (although unlikely)
that there is a noncomplement problem that can be solved in 12moves.
Figure 9 — The minimal 13move solution to the a7complement on Triangle(8)
Note: more than one move is sometimes shown between board snapshots.

Lower and Upper Bounds on the Length of the Minimal Solution
It is quite difficult to compute minimal length solutions
for boards larger than Triangle(8).
However, we can obtain a lower bound on the length of a minimal solution by
dividing the board into "Merson Regions" (named after Robin Merson who
first used this concept in 1962).
The shape of a region is chosen
such that when it is completely filled with pegs,
there is no way to remove a peg in the region without a move that originates
in the region.
On the edge of the board the regions can be corners or two consecutive holes,
but in the interior we must use hexagons 2 holes
on a side (7 holes total).
Figure 10 shows three triangular boards divided into Merson Regions.
Figure 10 — Dividing Triangle(6), Triangle(8) and Triangle(10) into "Merson Regions"
(R is the number of regions)

Any region that starts out full must have at least one move starting from inside it.
Since the starting position has every hole filled by a peg except one,
all regions start full except
possibly the region that contains the starting location.
If we start in a corner, then this region starts out empty but is filled by
the first move, hence there still must be a move out of this corner region.
We can summarize these results as follows:
If R is the number of Merson Regions, then
 If the starting vacancy is a corner, or is not in any region
(white board locations in figure 10),
then any solution to the peg solitaire problem (no matter where it finishes)
has at least R moves.
 If the starting vacancy is in a region (but not a corner), then any solution to
the peg solitaire problem (no matter where it finishes)
has at least R1 moves.
For example, on Triangle(6), this proves that any solution to
"Vacate c5, finish at a1" will take at least 9 moves.
On Triangle(8), this analysis indicates that the a7complement
must take at least 12 moves.
It can be seen that the 13move solution in figure 9 contains one "extra" move
above this minimum, in that there are two moves out of the central
(blue) hexagon region.
Therefore 13 moves is not proven minimal by this method, although
exhaustive computer search indicates no 12move solution exists.
As the triangular board becomes very large, the number of interior hexagons
eventually dominates the number of regions, because this is the only
region count growing quadratically.
We can then "tile" the board with these hexagons without leaving any gaps
(except near the edge of the board).
Therefore no solution can ever be shorter than the number of
holes in the board divided by 7.
No matter how large the triangular board, we cannot hope to find
a solution which does better than a 7sweep averaged over all moves.
Of course, averaging anywhere near this would be quite
remarkable—note that the 13move solution in figure 9
removes an average of only 34/13 ~ 2.6 pegs per move.
Using the long sweep solution in the last section,
we can obtain an upper bound on the length
of the shortest solution of any problem on Triangle(12i).
This upper bound is a solution of length
18i² + 15i  2.
As i increases, this shows that there exist solutions that
average (asymptotically) a 4sweep for every move.
Therefore, combining the result of the last paragraph, we see
that the minimal length solution for large triangular boards must average
between slightly less than 4 and 7 pegs captured per move.
Of course, finding any such solution will be very difficult.
The author would like to thank JC Meyrignac for the initial version of the program
which, after conversion to triangular solitaire, generated most of the figures.
References:
[1] John D. Beasley,
The Ins & Outs of Peg Solitaire
, Oxford Univ. Press, 1985
(paperback Edition 1992, contains an additional page: Recent Developments)
ISBN 019286145X (paperback).
[2] Letter to Martin Gardner, 16 June 1966, now
preserved in the Bodleian Library.
Information communicated by J. D. Beasley.
[3]
George Bell's Triangular Peg Solitaire Page.
Note: should this web address change in the future, I suggest doing a search with keywords:
"George Bell" Triangular Peg Solitaire.
[This search certainly worked since the previous geocities site had in fact disappeared!]
Copyright © 2004 — G. P. Jelliss and contributing authors.
Partial results may be quoted provided proper acknowledgement of the source is given.
Back to: GPJ Index Page