Triangular Peg Solitaire Unlimited

Peg solitaire on a 15-hole 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 15-hole 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 15-hole 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 33-hole cross-shaped 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 i-sweep.

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 i-sweep 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

1. B can be reduced to a single peg (the finishing location) using peg solitaire jumps.
2. The complement of B can be reduced to a single peg (the starting location) using peg solitaire jumps.

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.

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((n-1)/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 forward-backward theorem, maximal sweep patterns cannot appear in solitaire games on odd size 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 9-sweep 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 9-sweep 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 9-sweep:

1. Vacate c5, play to finish at a1 with the last move a 9-sweep (figure 3).
2. Vacate c5, play to finish at a4 with the last move a 9-sweep.
3. Vacate c5, play to finish at a4 with the second to the last move a 9-sweep.

On Triangle(8), the 18-sweep can also be reached. There are also three problems on this board that can contain the 18-sweep:

1. Vacate c5, play to finish at a1 with the last move an 18-sweep (figure 4).
2. Vacate b6 or e6, play to finish at c8 with the last move an 18-sweep.
3. Vacate c5, play to finish at b6 with the second to the last move an 18-sweep.

Figure 4 — A 15-move solution to problem #1 on Triangle(8) (finishing with an 18-sweep) 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 30-sweep has come up empty (although a solution was found which ends with a 29-sweep). Triangle(12) does not appear to have a maximal 45-sweep solution either. I haven't checked all possible configurations of this 45-sweep, 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.

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 78-hole Triangle(12) board. This solution finishes with a 42-sweep when run forward, and is shown in figure 5:

Figure 5 — Constructing a solitaire solution that finishes with the 42-sweep (Inductive Component A) (a) Forward: the finishing 42-sweep (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 U-shaped 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 300-hole 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 y-axis 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 U-shaped 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 191-sweep (figure 8):

Figure 8 — Forward: the finishing 191-sweep on Triangle(24) This sweep pattern is the maximal 198-sweep 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 4i-1 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.

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 33-hole cross-shaped 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 a1-complement, 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 33-hole 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 non-complement problems. Among the complement problems, only one can be accomplished in 13 moves, the a7-complement (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 13-move solution is unique in the sense that any other 13-move solution to the a7-complement must contain the exact same set of jumps, although not necessarily in the same order. I have found several other 13-move solutions to non-complement problems on the Triangle(8) board, and it is possible (although unlikely) that there is a non-complement problem that can be solved in 12-moves.

Figure 9 — The minimal 13-move solution to the a7-complement 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

1. 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.
2. 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 R-1 moves.

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 7-sweep averaged over all moves. Of course, averaging anywhere near this would be quite remarkable—note that the 13-move 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 4-sweep 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.

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 0-19-286145-X (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!]