|The Games and Puzzles Journal Issue 41, September-October 2005|
Diamond Solitaireby George Bell - September 2005
Peg solitaire is a one-person game usually played on a 33-hole cross-shaped board, or a 15-hole triangular board (figure 1). In the first case the pattern of holes (or board locations) come from a square lattice, while in the second case they come from a triangular lattice. The usual game begins with the board filled by pegs (or marbles) except for a single board location, left vacant. The player then jumps one peg over another into an empty hole, removing the jumped peg from the board. The goal is to choose a series of jumps that finish with one peg. The general problem of going from a board position with one peg missing to one peg will be called a peg solitaire problem. If the missing peg and final peg are in the same place, we call it a complement problem, because the starting and ending board positions are complements of one another (where every peg is replaced by an empty hole and vice versa).
Initially, we will consider peg solitaire on boards of rather arbitrary shape. The basic problem may seem hard enough, but we will add more conditions or constraints on the solution. The reason for this may not be immediately clear, but it has to do with the fact that adding constraints to a problem with many solutions can make it easier to find one, and the solutions themselves can be quite remarkable. The approach also brings out certain board shapes with interesting properties.
Suppose we add the constraint that the peg solitaire problem must finish in the most dramatic way possible: with one peg "sweeping off" all the remaining pegs, and finishing as the sole survivor. Here we need to distinguish between a jumpone peg jumping over another, and a moveone or more jumps by the same peg. Any single move that captures n pegs is a sweep of length n, or an n-sweep. In this terminology we want to finish a peg solitaire problem with the longest sweep possible.
A sweep that has the longest length geometrically possible
on a board is called a maximal sweep.
For most board shapes, maximal sweeps cannot be reached
in the solution to a peg solitaire problem.
In GPJ #36 , we considered the triangular board of side n,
Figure 1 Maximal sweeps on the standard boards, only the second is a super-sweep.
(a) A maximal
(b) A maximal 9-sweep on the 15-hole triangular board, Triangle(5).
Neither of the sweep patterns of figure 1 can be reached during a peg solitaire problem on that board. The easiest way to see this is to try to figure out how one could have arrived at the sweep board position, or equivalently try to play backwards from the sweep position. In GPJ #36 , we saw in the Forward/Backward Theorem that backward play is equivalent to forward play from the complement of the board position. This concept is referred to as the "time reversal trick" in Winning Ways For Your Mathematical Plays .
If we take the complement of either board position in figure 1, we find that no jump is possible. This proves that there is no "parent board position" from which the sweep position can arise, it cannot occur during the solution to a peg solitaire problem. If we take the complement of any super-sweep pattern, and a jump is possible, this means there would have to be two consecutive empty holes in the original super-sweep. Because it is a super-sweep, both of these holes must be the starting or ending locations of some jump in the sweep, which is impossible. Therefore a super-sweep can never occur in the solution to a peg solitaire problem.
If super-sweeps cannot occur in peg solitaire problems, the reader
may wonder why we are wasting our time with them.
The answer is provided by the triangular boards and GPS #36 :
the super-sweep pattern of
Let us consider peg solitaire boards on a triangular lattice where the board shape is a general polygon. Because it is on a triangular lattice the corners of the board are restricted to multiples of 60°. For which such boards is it possible to have a super-sweep? It is clear that the board edges must all have an odd length (in holes), because the super-sweep must pass through all the corners of the board (a corner hole cannot be jumped over, and consequently the super-sweep must jump into it). Consider, for example, the 8-sided polygon board of figure 2.
Figure 2 An 8-sided (non-convex) polygon board and the associated super-sweep graph.
(a) An unusual 24-hole board, set up in the board position of a hypothetical super-sweep (of length 15).
(b) The graph of the hypothetical super-sweep.
Can the peg at the upper left corner of the board make a
tour of the board, sweeping off all 15 other pegs?
We can answer this question by looking at the graph formed by
the sweep, shown separately in
Using the Euler path theorem we can eliminate many boards from having super-sweeps. Hexagonal or star-shaped boards have hexagonal symmetry, but cannot support super-sweeps because they have six nodes of odd degree. If we restrict ourselves to board shapes that are convex polygons (no 240° or 300° corners) things are particularly simple. Using elementary geometry we can prove the following: For a convex board on a triangular lattice, only three board shapes can have a super-sweep:
A rhombus is a special case of a parallelogram where all
four sides have the same length n,
we'll call this board
Figure 3 Super-sweeps on Rhombus(3), Rhombus(5) and Rhombus(7).
These sweeps have lengths of 5, 16, and 33, respectively, and end at the lower right corner.
The length of this sweep, for odd n, is
This 36-hole board has several unusual properties. It is also of a reasonable size for playing by hand, and for exhaustive computer searches. This board is equivalent to the 6x6 square board on a square lattice, with the addition of moves along one diagonal. It is therefore possible to play this board using a chess or go board, although this is not recommended because the symmetry of the board is hard to see. For playing by hand I recommend using part of a Chinese Checkers board. The ideal board for playing by hand is a computer , because we can easily take back moves and record move sequences.
Figure 4 |
Potential finishing locations for a problem including a maximal sweep (
Notation: moves are denoted by the starting and ending coordinates of the jumps, separated by dashes.
The longest sweep geometrically possible on
In figure 4, all potential finishing locations for solutions containing
It is also possible for solutions to complement problems to include maximal sweeps. This also is not known to occur for any other board (although some larger rhombus boards have this property). Here are four essentially different complement problems that can be solved using a maximal sweep:
These problems are most easily solved by attempting to play backward,
or equivalently by playing forward from the complement of the
board position before the
Figure 5 A symmetric solution to the d3 complement (problem #4).
This solution has 17 moves.
Note that more than one move is sometimes shown between board snapshots.
Any peg solitaire problem on this board begins with 35 pegs and finishes with one, so a solution consists of exactly 34 jumps. The number of moves, however, can be less than this, and an interesting question is to find the solution with the least number of moves. This is different from finding solutions with maximal sweeps, and answers are more difficult to obtain. The minimal solution length can usually be found only using exhaustive computer search, which can take many hours on this board, just for one problem.
If we take into account all possible starting and finishing locations for a peg solitaire problem on this board, we find there are 120 distinct problems. I have only solved the complement problems, for there are only 12 of them. Of these 12, I have found that 7 can be solved in a minimum of 13 moves, with the rest requiring 14 moves (see figure 7 for all results). A sample 13-move solution is shown in figure 6.
Figure 6 A 13-move solution to the c3-complement.
The last 4 moves originate from the 4 corners, an unusual property for a 13-move solution.
Note that more than one move is sometimes shown between board snapshots.
Using the "Merson region" analysis of GPJ #36 , it is possible to
prove that some 13-move solutions are the shortest possible.
In general, however, we rely on the exhaustive search to establish the minimum.
For much more information on minimal length solutions on
36 is the first integer (aside from the trivial case 1) that is simultaneously
a triangular number and a perfect square.
This is reflected in the fact that
Figure 7 The length of the shortest solution on
Colors indicate the length of the shortest solution to a
complement problem starting and finishing at that location.
In GPJ #36 , we found that maximal sweeps on
We have just shown that a maximal sweep can be reached by a peg solitaire
Theorem: For any |
To prove this, it suffices to show that the complement of some maximal sweep pattern can be reduced to one peg. The sweep pattern we choose begins at the upper left corner, and ends one hole up and left from the lower right corner. When we take the complement, this results in the board position of figure 8.
Figure 8 The complement of the sweep pattern on Rhombus(6i).
Note that the board position is symmetric about the yellow line.
Figure 9 The moves of Phase A.
Phase A, shown in figure 9, consists of 8 moves that clear out
the leftmost 6 columns of the board and the upper 4 rows,
except for the last (rightmost) column.
If the board is larger than the
Figure 10 The moves of Phase B.
The moves here are shown on
Phase B will actually be applied to boards at least as large as
Phase B, shown in figure 10, is 9 moves that reduce the sweep pattern by 6 rows and 6 columns. As before if the board is larger than shown the multi-jump moves are extended. After applying Phase B j times the leftmost 6j+6 columns will be empty, and the topmost 6j+4 rows will also be empty, except for a trail of pegs in the last column that will be taken by the final move.
Figure 11 The moves of Phase C.
Finally Phase C is executed to take the board down to a one peg
in the upper right corner.
The 9 moves of this phase are shown in figure 11.
Putting together all three phases,
it only takes
Only in Phase C is the fact that the side is divisible by 6 needed. For only on such boards can the final peg finish in the upper right hand corner.
Figure 12 Putting Phases A and C together for a solution on Rhombus(12).
In figure 12 on
An integer that is simultaneously a perfect square and
a triangular number is called a square triangular number [6, 7].
As was the case with
After the 36-hole boards, the next time this occurs is with
Peg solitaire on a triangular lattice is a fascinating game, and one that has not been studied to the extent that "normal" (square lattice) peg solitaire has. This paper, and GPJ #36  have shown that triangular lattice peg solitaire is well suited for inductive arguments. Inductive arguments have also been used to create an algorithm for triangular boards of any size that can reduce any (solvable) single vacancy down to one peg . I believe inductive arguments are possible for square lattice boards, but the reduction from 6 jump directions to 4 seems to make such arguments more difficult.
While the results on this page on
There remain many unanswered questions regarding rhombus and triangular boards.
Can maximal sweeps be reached on peg solitaire problems
 George Bell, Triangular Peg Solitaire Unlimited: Issue #36 of The Games and Puzzles Journal, Nov-Dec 2004.
 John H. Conway, Elwyn R. Berlekamp, Richard K. Guy, Winning Ways for Your Mathematical Plays, Volume 4, AK Peters, 2004 (second edition).
 N. J. A. Sloane, The On-Line Encyclopedia of Integer Sequences. Rhombic matchstick numbers are sequence A045944
 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.
 John D. Beasley, The Ins & Outs of Peg Solitaire, Oxford Univ. Press, 1992 (paperback edition), ISBN 0-19-286145-X.
 Eric W. Weisstein. "Square Triangular Number." From MathWorld--A Wolfram Web Resource. http://mathworld.wolfram.com/SquareTriangularNumber.html
 N. J. A. Sloane, The On-Line Encyclopedia of Integer Sequences. Square Triangular Numbers are sequence A001110
 George I. Bell, Solving Triangular Peg Solitaire, submitted to The Journal of Recreational Mathematics, Feb 2005.
[Note: George Bell's Triangular Peg Solitaire Page, The On-Line Encyclopedia of Integer Sequences and The Journal of Recreational Mathematics
migrated to new sites since the publication of this article and the links have accordingly been updated (June 2013).]