Diamond Solitaire by 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 jump—one peg jumping over another, and a move—one 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 [1], we considered the triangular board of side n, called Triangle(n). We saw that for n odd, the board Triangle(n) supports an even more remarkable sweep that is maximal and also has the property that every hole in the board is affected by the sweep in that it is either jumped over or is the starting or ending hole of some jump in the sweep. Such remarkable sweeps need a special name—we call them super-sweeps. While any board has a maximal sweep, only a very few support a super-sweep.

Figure 1 — Maximal sweeps on the standard boards, only the second is a super-sweep. (a) A maximal 16-sweep on the 33-hole cross-shaped board. (b) A maximal 9-sweep on the 15-hole triangular board, Triangle(5).

In figure 1a, the central hole is not touched or jumped over by the sweep, thus while this sweep is the longest possible it is not a super-sweep, and a super-sweep is not possible on this board. It's not hard to see that super-sweeps are never possible on square lattice boards, except for certain trivial or degenerate cases (like a 1-dimensional board). Non-trivial super-sweeps are only possible on a triangular lattice, an example is figure 1b.

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 [1], 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 [2].

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 [1]: the super-sweep pattern of figure 1b can be reached in a problem on Triangle(6). This 9-sweep is no longer a super-sweep with respect to Triangle(6), but it is still a maximal sweep. Loosely speaking, a super-sweep may still be reachable in a peg solitaire problem on a board of one larger size.

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 figure 2b rather than on top of the board as in figure 1. In the language of graph theory the super-sweep is an Euler path on this graph, i.e. a path that traverses every edge exactly once. One of the most basic theorems of graph theory states that an Euler path is possible if and only if there are either zero or two nodes of odd degree. Looking at figure 2b, we see that there are four nodes of odd degree, hence an Euler path is not possible, and the answer to the question above is no. The board in figure 2 does not support a super-sweep.

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:

1. Triangles, and only equilateral triangles are possible on a triangular lattice. Because every node in the super-sweep graph has even degree, the super-sweep always begins and ends at the same board location.
2. Parallelograms, which have alternating 60° and 120° corners as you go around the circumference. The super-sweep must begin at one 120° corner and end at the other.
3. Trapezoids, which have two 60° corners followed by two 120° corners. The super-sweep must begin at one 120° corner and end at the other. These boards can also be considered as equilateral triangles with one corner cut off.

A rhombus is a special case of a parallelogram where all four sides have the same length n, we'll call this board Rhombus(n). By rotating them 60°, they become diamond-shaped and could also be called Diamond boards. In the remainder of this paper, we'll go into some of the remarkable properties of these boards. Figure 3 shows the first few Rhombus board super-sweeps.

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 (3n+1)(n–1)/4. Since the total number of holes in the board is n², this sweep removes nearly 3/4 of the pegs on the full board with a single move. For n = 3, 5, 7, 9, 11, 13, ..., the sequence of sweep lengths is 5, 16, 33, 56, 85, 120, ..., called the "Rhombic matchstick sequence" [3] because it is the number of matchsticks needed to construct a rhombus (with (n–1)/2 matchsticks on a side).

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 [4], because we can easily take back moves and record move sequences.

The board Rhombus(6) is a null-class board. For a definition of this term, see [2] or [5], the important concept is that only on null class boards can complement problems be solvable. Rhombus(6) is the smallest rhombus board on which a complement problem is solvable, and in fact all complement problems are easily solvable.

Figure 4 — Rhombus(6) hole coordinates. Potential finishing locations for a problem including a maximal sweep (16-sweep) are shown in blue. Notation: moves are denoted by the starting and ending coordinates of the jumps, separated by dashes.

The longest sweep geometrically possible on Rhombus(6) has length 16 (as in figure 3). Can 16-sweeps occur in peg solitaire problems on this board? Here we aren't limiting the 16-sweep to be the last move, but leave open the possibility that it could happen at any move. We note that there are only a few places where the 16-sweep can begin and end. It can go from a1 to e5, b2 to f6, b1 to f5, or any symmetric variant of these. The 16-sweep can be the final move, or it can be the second to the last move, for example the 16-sweep can go from a1 to e5, followed by f6-d4, or e6-e4. The 16-sweep can even be the 3rd to the last move, from a1 to e5, followed by e6-e4 and f5-d3.

In figure 4, all potential finishing locations for solutions containing a 16-sweep are shown in blue. Not all are feasible, the finishing 16-sweep from b1 to f5 is in fact impossible to reach from any starting vacancy, as discovered by exhaustive computer search. However all other configurations of the 16-sweep can be reached. In fact, starting from any vacancy on the board, there is a solution with a maximal sweep (16-sweep) that finishes with one peg. This board is the only one we know of, on a square or triangular lattice, with this amazing property.

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:

1. e5 complement: solve with the last move a 16-sweep.
2. d4 complement: solve with the second to last move a 16-sweep.
3. e4 complement: solve with the second to last move a 16-sweep.
4. d3 complement: solve with the third to last move a 16-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 16-sweep. All four problems make good challenges to solve by hand; they are easy to solve using a computer (provided you don't try to solve them by playing forward). In figure 5 we show a solution to problem #4. This solution is interesting in that after the third move, the board position is symmetric about the yellow line. After that moves are done in pairs, or are themselves symmetric, preserving the symmetry up until the last two moves.

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 [1], 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 Rhombus(6) and other boards see my web site [4].

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 Triangle(8) and Rhombus(6) both have 36 holes. Because of this, it is quite interesting to compare the properties of these two peg solitaire boards. Figure 7 shows the minimum length solution of a complement problem by color for each of these boards. Note that Rhombus(6) in general supports slightly shorter solutions, with none requiring 15 moves. Determining the coloring for figure 7 for both boards required a lot of CPU time, over 1 week on a 1 GHz PC.

Figure 7 — The length of the shortest solution on Triangle(8) and Rhombus(6).
	Color Length of the shortest solution to the complement problem Red 13 Moves Blue 14 Moves  Yellow  15 Moves
Colors indicate the length of the shortest solution to a complement problem starting and finishing at that location. The Rhombus(6) board has been rotated to its "diamond" configuration to show the symmetry.

In GPJ #36 [1], we found that maximal sweeps on Triangle(6) and Triangle(8) could occur in peg solitaire games on these boards. Although a formal proof has not been found, computational results suggest that maximal sweeps cannot be reached on any larger triangular boards.

We have just shown that a maximal sweep can be reached by a peg solitaire problem on Rhombus(6), but what about larger rhombus boards? One might suspect that maximal sweeps would eventually become unreachable, as with the triangular boards. Somewhat remarkably, however, this is not the case.

Theorem: For any i > 0, there exists a solution to a peg solitaire problem on Rhombus(6i) where the last move is a maximal sweep of length (9i–1)(3i–1).

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.

The case i = 1, or Rhombus(6), has already been solved (problem #1 in the previous section). We will use induction to prove the general case, starting with i = 2. The solution proceeds through three Phases (A, B and C). We apply the moves of Phase A once, then B (i–2) times, followed by Phase C once.

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 Rhombus(12) shown in figure 9, the long multi-jump moves must be extended accordingly. We are left with a very similar board pattern as the one we started with, just reduced in size. Note, however, that the final board position is no longer symmetric.

Figure 10 — The moves of Phase B. The moves here are shown on Rhombus(15) to save space. Phase B will actually be applied to boards at least as large as Rhombus(18).

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 9i–1 moves to clear the sweep pattern of figure 8. To find the solution ending in the maximal sweep, we begin from a vacancy at the upper right corner, and execute the jumps of Phases A, B and C in exactly the reverse order. Thus we execute the jumps in Phase C reversed, followed by (i–2) Phase B's, and then Phase A, all in reverse order. The long sweeps become individual jumps, and the solution ending in the maximal sweep has significantly more than 9i–1 moves.

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 Rhombus(12), we show the complete solution that reduces the complement of the sweep pattern to one peg. In this case we need only execute Phases A and C, and in figure 12 the two phases have been interleaved and are no longer visually separate. This reduces the number of diagrams to show the solution, but the inductive nature of the solution becomes much harder to see. It is unfortunate that a Chinese Checkers board is too small to play this solution on. If you can find a large enough board, it is interesting to play the moves in this solution in exactly the reverse order, and watch as the sweep position magically appears. The final sweep in the reversed solution has length 85.

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 Rhombus(6) and Triangle(8), which both have 36 holes, each square triangular number corresponds to a rhombus and triangular board having the same number of holes. If the side of the rhombus board is divisible by 6, and the side of the triangular board by 12, then both have long sweep finishes by the above analysis and GPJ #36 [1].

After the 36-hole boards, the next time this occurs is with Rhombus(204) and Triangle(288), which both have 41,616 holes. By our inductive arguments, we can construct solutions to peg solitaire problems on these boards that finish with sweeps of length 30,805 and 30,793, respectively. The next larger such boards are Rhombus(235,416) and Triangle(332,928), boards with over 55 billion holes, that can finish with sweeps over 41 billion in length.

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 [1] 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 [8]. 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 Rhombus(6) were obtained by exhaustive computer search, the long sweep finishes on Rhombus(6i) were found by hand. The computer was still of significant help, but only in providing an interface to play the game on the large boards required.

There remain many unanswered questions regarding rhombus and triangular boards. Can maximal sweeps be reached on peg solitaire problems on Rhombus(2i)? I have been able to answer this question in the affirmative for 2≤i≤9. It would also be nice to prove that maximal sweeps are not reachable in peg solitaire problems on triangular boards larger than Triangle(8) (or find a counterexample).

References:
[1] George Bell, Triangular Peg Solitaire Unlimited: Issue #36 of The Games and Puzzles Journal, Nov-Dec 2004.
[2] John H. Conway, Elwyn R. Berlekamp, Richard K. Guy, Winning Ways for Your Mathematical Plays, Volume 4, AK Peters, 2004 (second edition).
[3] N. J. A. Sloane, The On-Line Encyclopedia of Integer Sequences. Rhombic matchstick numbers are sequence A045944
[4] 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.
[5] John D. Beasley, The Ins & Outs of Peg Solitaire, Oxford Univ. Press, 1992 (paperback edition), ISBN 0-19-286145-X.
[6] Eric W. Weisstein. "Square Triangular Number." From MathWorld--A Wolfram Web Resource. http://mathworld.wolfram.com/SquareTriangularNumber.html
[7] N. J. A. Sloane, The On-Line Encyclopedia of Integer Sequences. Square Triangular Numbers are sequence A001110
[8] 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).]