Triangular Peg Solitaire
These pages were created and are maintained by
George Bell (gibell@comcast.net)
Last Modified March 12th, 2014
Copyright © 2006–2014 by George I. Bell
To square lattice
peg solitaire
To the peg
solitaire army
Leave only one you're genius,
... Leave four or more'n you're just plain "eg-no-ra-moose".

Cracker Barrel peg game instructions

Table of Contents:

Introduction

Triangular peg solitaire is a popular puzzle most commonly played on the 15-hole board shown on the left. In triangular peg solitaire the holes in the board are based on a lattice of equilateral triangles. The board shape itself need not be triangular although this is the most common shape. The 15-hole board is a triangle 5 holes on a side, and will be called the Triangle(5) board, while the 21-hole board is the Triangle(6) board. Most people for some reason stick with only the 15-hole board; below we will consider boards quite a bit larger than either of these. If you just want to know how to solve the 15-hole board, go to my page on tips and solutions for the Cracker Barrel Puzzle.

The origins of this game are even hazier than for regular (square lattice) peg solitaire. The earliest known reference is a US patent from 1891. This patent does not use the 15-hole triangular board, but it the first known use of a board on a triangular grid.

The game is played in a similar fashion to regular (square lattice) peg solitaire. Start from a position with one hole open and jump one peg over another, removing the peg that was jumped over. The goal is to finish at a board position with only one peg. Jumps are allowed along three directions parallel to the edges of the board. Each peg has a maximum of six neighbors, while in square solitaire there can be at most four. These are only minor differences, as we shall see, and the theory of the game is very similar. Many block moves and block removals (3-removal, 2-removal, 6-removal, and L-move [B1], [W3]) carry over to triangular solitaire and are equally useful. However, the 15-hole and 21-hole boards are so small only the first two of these are of much use.

Boards based on a triangular lattice can be depicted in several ways:

  1. On a grid of peg holes that form equilateral triangles (like the actual board shown above).
  2. A board composed of hexagons, the centers of which form a triangular lattice (as in the figures at the top of this page).
  3. On a square lattice with the understanding that "normal" (square lattice) moves plus those along one diagonal are allowed (see the first figure after preliminaries, left board).
  4. A board composed of staggered squares (see the diagram to the right). This is similar to method 3, except that each row is shifted so that a triangular board becomes left-right symmetric.
With the last two options it can be difficult to see the triangular symmetry of the problem. On this site I try to show solutions on a grid of hexagons so that the symmetry is evident. However in deriving the theory of position classes the last representation is useful.

Where can you buy a board? There are many companies that make 15-hole triangular boards, my favorite is made by Venture (shown in the above photo). It is much more difficult to find any of the larger boards, The best board I have found is a Chinese Checkers set! This allows you to play triangular boards up to Triangle(13), as well as hexagonal or stellar shaped boards. Alternatively, see my online triangular peg solitaire game.

On the 15-hole Triangle(5) board, all solutions have exactly 13 jumps, because we start with 14 pegs and one is lost with each jump. However, when the same peg jumps one or more pegs, we call this one move. A difficult question is, what is the solution with the least number of moves? This question may be rephrased more informally as: what is the solution that involves touching the smallest number of pegs? While this question has played an important role in the history of the 33-hole English Board, it seems not to have been considered for triangular solitaire.

The following terminology is used in referring to moves involving multiple jumps: when a peg removes n pegs in a single move, we refer to it as a sweep, or more specifically, an n-sweep. A sweep that begins and ends at the same board location is called a loop.

Preliminaries

Board Notation

It is common to number the holes consecutively, however we use a notation that is derived from that used for square lattice boards. The diagrams below show this notation on the Triangle(6) board.

a1
a2 b2
a3 b3 c3
a4 b4 c4 d4
a5 b5 c5 d5 e5
a6 b6 c6 d6 e6 f6
The Triangle(6) Board
shown on a rectangular grid
(with a diagonal move added).
The Triangle(6) Board
on a hexagonal grid
showing board notation.
Skew Cartesian
coordinates on
Triangle(6)

It is convenient that this notation does not change as the board size increases (i.e. the upper corner hole is always a1). In a computer, it is most convenient to use "Skew Cartesian coordinates". In skew coordinates, it is particularly simple to perform reflections and rotations of the board (see [P4]).

To refer to a jump we simply list the starting and ending board locations separated by a dash, i.e. "a3-a1". The loop move from a1 of length 3 is abbreviated "a1-a3-c3-a1".

Null-Class Boards

The general peg solitaire problem is to play from a full board with one peg missing to a board position where only one peg remains. These problems are called single vacancy to single survivor problems. The special problem where the initial vacancy and survivor are the same board location is called the (single vacancy) complement problem. How do we know which single vacancy to single survivor problems are potentially solvable? This is answered by exactly the same argument as in the square lattice case - we repeat this argument below for completeness.

Consider a diagonal labeling (and coloring) of the board holes as shown below. Note that the board location (x,y) in skew coordinates is labeled (x+y) (mod 3)+1, or the remainder when x+y is divided by 3, plus one.

1
2 3
3 1 2
1 2 3 1
2 3 1 2 3
3 1 2 3 1 2
The usual diagonal coloring
for a square lattice board ...
looks like this when
the board is viewed
on a hexagonal grid.

Given a board position B, let Ni(B) be the number of pegs in the cells marked i, and T(B) be the total number of pegs on the board. Now consider what happens to these functions after a solitaire jump is executed. The total number of pegs T always goes down by one, while one of N1, N2 or N3 increases by one while the other two decrease by one. Therefore the evenness or oddness of the differences T-Ni does not change as the game is played. This partitions the set of all possible boards into four position classes depending on the parity (even or oddness) of the three numbers: (T-N1,T-N2,T-N3). As you play solitaire you cannot leave the position class that you start in. [You might think there should be 23 or 8 position classes. However the numbers Ni are not independent, because T = N1+N2+N3, and this implies that either two of the three T-Ni are odd or they are all even].

Consider the board position with every peg filled. On the above board T=21 and Ni=7 for all i, and all three parities are Even. The empty board with no pegs also lies in the same position class: (Even,Even,Even). This is the defining property of a null-class board: any board position and its complement are always in the same position class (the complement of a board position is the board position where each peg is replaced by a hole and vice versa). On a null-class board if we begin a problem with a vacancy at a hole of one color, then the last peg can only be left at another location of the same color.

On the above Triangle(6) board we see that for each initial vacancy there are seven possible finishing locations (some of which may be equivalent by symmetry). Still, one can see that the number of possible problems on a triangular board is about twice as large compared to a board with a similar number of holes on a square grid.

Because there are only four position classes we can say more about boards that are not null-class. In particular, the board positions with one peg at any location 1, 2 or 3 are representatives of three of the four position classes. The empty board is a representative of the fourth position class. Unlike in peg solitaire on a square lattice, every position class contains members with zero or one pegs. Because of this fact, if a board is not null-class, then the full board must be in the same position class as some position with only one peg. Without loss of generality, let's assume that we have labeled the holes so that this is location 1 (pink).

We now know that if we start with any vacancy at location 1, then we are in the same position class as the empty board and can never reach a position with one peg. If we start at a vacancy at location 2 (orange), then we are in the position class 3 (yellow) and can finish with any single peg at a yellow hole. Similarly from a vacancy at any yellow hole, we can finish at any orange hole. This is quite a bit simpler than the situation for non null-class boards on a square lattice.

We may summarize all this by the following rules:

  1. Only on a null-class board is it possible to solve the complement problem.
  2. Consider a null-class board with an initial vacancy at (x0,y0). Then we can only finish with a single peg at board positions (x1,y1) where (x1-x0)-(y1-y0) is a multiple of 3. The coordinates here are Cartesian coordinates as in the left board above. In other words, if we start in a hole of a certain color, we can only finish in a hole of the same color.
  3. If the board is not null-class, then the full board is in the same position class as some class with a one peg representative, let us assume it is the pink class (1). Then it is impossible to start or finish any single vacancy to single survivor problem in a pink hole. If we start in an orange hole (2), we can in general finish in any yellow hole (3), and vice-versa.

From a practical standpoint, how do we determine whether a particular board is null-class or not? The most obvious technique is to label the board in the above fashion and count the number of 1's, 2's and 3's. If these three numbers have the same parity (all odd or all even) then the board is null-class, otherwise it is not.

A more clever technique is to apply local transformations to the full board that do not change the position class we are in, and try to reduce it to the empty board. A simple class of very useful transformations is to take the complement of any three consecutive board locations in a line, or take the complement of any three board locations that form a contiguous triangle (such as {a1,a2,b2}). A solitaire move itself is such a transformation, but there are others, such as removing three pegs in a row, replacing two pegs separated by a hole by a peg in the hole, or removing any triangle of 3 pegs. Using this technique we can discover which position class any pattern of pegs is in, and which finishing holes are possible. The diagrams show how these complement moves can reduce the full board to the empty board, demonstrating that these two boards are null-class.

Boards

Triangular Boards

A Triangle(5) board made in Japan, imported
by William A. Rogers (photo courtesy Richard Chabot)
The Triangle(n) board has T(n)=n(n+1)/2 holes, where T(n) is the n'th triangular number: 1, 3, 6, 10, 15, 21, 28, ... A triangular board is a null-class board unless n is of the form 3i+1, i.e. n=1, 4, 7, 10, ... Triangular boards that are not null-class are also characterized by having a unique central hole, and the total number of holes is not a multiple of 3. Therefore we conclude from the null-class work above that no central vacancy complement problem is solvable on any triangular board. This conclusion is also stated in Beasley [B1].

In fact if the triangular board is not null-class we can say a good deal more than this. In such cases, the full board is always in the same position class as a single peg at the center, and also a single peg at a corner. It is impossible to begin or end any single vacancy to single survivor problem at the central hole or any corner hole. If we begin with a vacancy NOT in the same position class as the center, then we can finish at any peg that is in the remaining position class. For example on Triangle(7) if we vacate a1, it is impossible to finish with one peg. If we vacate a2, then we can finish at b2, a3, c4, b5, e5, a6, d6, c7 or f7 (all these problems are in fact solvable).

Another (separate) classification of triangular boards can be made based on the pattern of peg jumps. We exclude very small boards n < 5 from what follows as they have locations for which no jump at all is possible. Triangular boards for which n is even have two categories of pegs: (1) those that can reach one (and only one) of the three corners or (2) those that cannot reach any corner or edge. If n is odd then there are also two categories of pegs: (1) those that can reach any of the three corners, (2) those that can reach an edge, but no corner. These peg classifications are simpler than those seen in solitaire on a square lattice (where there may be three categories of pegs). Therefore, in a general sense there is less complexity in triangular peg solitaire.

An interesting property of triangular boards is that they support the longest sweeps of any solitaire board. From any board location, the total number of jump directions is even, which suggests that it may be possible to construct a single loop move that covers the entire board. If n is odd, it is possible to create a sweep that jumps into or over every single location on the board! The length of this sweep is 3T((n-1)/2)=3(n2-1)/8. For example on the Triangle(5) board it is possible to create a 9-sweep. Since no move is possible starting from the complement of this position it cannot be reached from a single vacancy start. However, it may be possible to reach such a sweep from larger triangular boards. The title graphic in fact shows that such a sweep on Triangle(5) can be reached on Triangle(6). More about this below.

Consider now a null-class triangular board, that is n=5, 6, 8, 9, ... Suppose the board position is unchanged after the board is rotated 120 degrees. We can conclude that this board position cannot be reduced to a single peg. Why is this the case? Referring to the position class labeling above, it is not hard to see that for such a position, we must have N1=N2=N3, and hence the board position is in the position class of the empty board. This proves that on a null-class triangular board, no solution to a single vacancy to single survivor problem can go through a board position with 120 degree rotational symmetry. We shall see that solutions on triangular boards that are not null-class (i.e., n=7), or null-class hexagonal boards can go through positions with rotational symmetry.

The Triangle(4) Board   Play Now!

This 10-hole board is not null-class, but is the smallest triangular board on which a single vacancy to single survivor problem is actually solvable. The only problem which is solvable on this board has the form "Vacate a2, finish at b2" (or symmetric equivalents), and it is easy to find a solution which accomplishes this in 5 moves.

The Triangle(5) Board   Play Now!

Board Notation The SAX count
This 15-hole null-class board is probably the second most popular peg solitaire board game (after the 33 hole English board). You will find games made from wooden blocks and golf tees in Cracker Barrel Restaurants. This board is very easy to solve on a computer due to its small size. To skip all this mathematical analysis and see tips and solutions, go to my page on tips and solutions for the Cracker Barrel Puzzle.

Many single vacancy to single survivor problems on this board are equivalent by rotation or reflection of the board. It suffices to consider only the problems where we begin and end in the gray holes on the board notation diagram to the left: a1, b3, a4, d4 and c5. These gray holes are all in the same position class, which is why we have chosen them, and this convention is also used for larger triangular boards.

A powerful analytical tool on this board is the SAX count discovered by Irvin and Robert Hentzel in 1986 [P1]. Consider the real valued function on board states shown in the right-hand diagram above [to evaluate this function on a board state, total all the numbers where a peg is present]. A resource count is a function on board states whose value cannot increase during play. The function in the diagram fails to be a valid resource count, but it can only be increased by a move along the edge of the board which jumps over a "–1", i.e. a2-a4 or d4-b2. Such moves necessarily change the number of pegs in one of the three colored regions from 2 to 1.

We can modify the above function into a valid resource count by adding +1 for every colored region that contains 2 or more pegs: this is the "SAX count". The name comes from the definition S+A–X, where S is the number of edges (colored regions) with two or more pegs, A is the number of pegs at "+1" board locations, and X is the number of pegs at "-1" board locations. We have already shown that a decrease in X cannot increase the SAX count because it must be accompanied by a decrease in S. It is impossible for A to increase, and no move can increase S by more than 1. Any such increase in S must be accompanied by a decrease of 1 or 2 in A. Hence there is no move from any board position that can increase the SAX count: it is a valid resource count.

Using the SAX count, we can prove the b3-complement problem is unsolvable. For this problem, you should verify that the SAX count must go from -1 to +1, which is impossible since the SAX count cannot increase during play. In fact, starting from the b3 initial vacancy, one can only finish at a single peg which is in the same position class and also has SAX count -1, which is a1 or c5. Any jump that finishes at a1 reduces the SAX count by one, so a1 is not possible either. Thus the SAX count proves that if we vacate b3 the only possible finish is at c5. All single vacancy to single survivor problems on this board are in fact solvable, except for those problems that finish or originate at the central locations (b3,b4 and c4). Of these, the SAX count shows that only "vacate b3, finish c5" or vice versa (or symmetric equivalents) are solvable.

If we consider the a1-complement problem, how quickly can one reach a board position from which a solution is no longer possible? The SAX count shows that you can mess up in only two jumps! Although the a1-complement starts with SAX count +1, and finishes with -1, the first and last jumps each take away 1, so all other jumps cannot lose anything. Let's assume the first jump is a3-a1. The second jump c4-a2 loses 1 and it is therefore impossible to reach a solution after this jump is made (this analysis refers to the a1 finish, it still is possible to finish at c5). The second jump a5-a3 is also a dead end, for although a5-a3 doesn't lose anything, all third jumps from this position lose 1. Therefore the only choices for the second jump are c3-a3 and c5-a3, and both of these can lead to solutions. This analysis shows why the corner complement problem can seem difficult, because if you move randomly there is a 50/50 chance you won't be able to solve the complement problem after only two jumps.

All solutions to the a1-complement can be derived from the following two solutions:

Type 1: {a3-a1, c3-a3, b5-b3, d5-b5, a5-c5, e5-c3, b2-d4, c5-c3},
then {a4-a2, d4-b2}, followed by {a1-a3, a3-c3, c3-a1}
 
Type 2: {a3-a1, c5-a3, a5-c5, d5-b5, c3-c5, b5-d5, e5-c5, a1-c3},
then {d4-b2, a4-a2}, followed by {b2-b4, c5-a3, a3-a1}

A metal Triangle(5) board with
brass pegs (photo courtesy Richard Chabot)
Each set of jumps in braces takes the board from one position with symmetry about the y-axis to another such position. Each jump set can be replaced by its reflection across the y-axis, and the jumps do not need to be taken in the order given (for example the jumps could be done in reverse order and you would still have a solution). A Type 1 solution can be identified by the fact that it must contain [c3-a3 or a3-c3] and [b5-b3 or d5-b3] (these jumps are highlighted in green in the above figures). The two jumps enclosed in brackets are mirror images of each other, and a Type 1 solution must contain one of each, while a Type 2 solution never contains any of these jumps. The unique jumps for a Type 2 solution are [b2-b4 or a2-c4] and [a3-c5 or c3-c5].

If we take each set of jumps above, or its mirror image, and reorder the jumps however we like, we obtain all possible solutions to the a1-complement problem. If jump order is kept track of, there are 6,816 different solutions. However, every one of these is simply a modification of the above two solutions. Note that it is not true that any solution to the a1-complement must pass through an intermediate position with symmetry about the y-axis, as all shown above do (only that the jumps in any solution can be reordered so that it does).

One of the solutions above has been entered into The On-Line Encyclopedia of Integer Sequences as A120422 [W11]. The sequence in OEIS does not have jumps listed in the same order as either of the above solutions, can you figure out whether it is Type 1 or Type 2?

Keeping track of the SAX count during play is helpful, but it can be difficult to remember and calculate quickly. In many situations you want to avoid any loss in the SAX count, and the following general rules of thumb may help if you find yourself trapped in a Cracker Barrel Restaurant:

  1. Avoid jumping into a corner (a1, a5 or e5). Such a jump loses 1 in the SAX count. Of course, in some situations, it is the only jump available.
  2. Avoid any jump that begins from one of the three center holes (b3, b4 or c4). Such jumps lose 1 or 2 in the SAX count. It is quite rare for a solution to include such a move, although it is possible for some problems.

The slack in a problem is the difference in the SAX count between the initial and final board positions. The easiest problems are those with the greatest amount of slack, because there is less restriction on the moves that can lead to a solution. Starting and finishing at c5 is the easiest problem on the board because it has a slack of +2. The a1-complement also has a slack of +2, but as mentioned above the first and last move lose 1 each, so in between there is no slack. The effective slack is the slack that remains after these first and last moves are taken into account (the distinction is only important for problems that begin or end at a corner). Any problem with a negative effective slack is unsolvable, and any problem with zero effective slack can contain no jump that reduces the SAX count (except for the first or last move if it is a corner start or finish). The table below shows the effective slack for all single vacancy to single survivor problems on the board:
Vacate Finish At Effective Slack Relative Difficulty
c5 c5 2 Easy
c5 a1 1 Medium
a1 c5 1 Medium
c5 a4 1 Medium
a4 c5 1 Medium
a1 a1 0 Hard
a4 a1 0 Hard
a1 a4 0 Hard
a4 a4 0 Hard
d4 a4 0 Hard
c5 b3 0 Hardest
b3 c5 0 Hardest
b3 a1 -1 Impossible
a1 b3 -1 Impossible
b3 a4 -1 Impossible
a4 b3 -1 Impossible
b3 b3 -2 Impossible

To reach "genius" level, many boards challenge you to leave as many pegs as possible with no jumps remaining. It is not too difficult to figure out how to do this, working backwards from the final configuration. The hard part is figuring out what this final configuration looks like. Depending on which hole is initially vacant, you can finish stranding from 7 to 10 pegs [W7, W8]

A related question is how quickly can you reach a board state from which a single peg finish is no longer possible? The answer is that it is possible to do so on the very first move! If one considers starting with an initial vacancy at a4, the move c4-a4 takes one to a position with SAX count -2, and it is therefore impossible to reach any final state with one peg. All solutions beginning from the a4-vacancy must begin with the move a2-a4, and solutions to the a1-vacancy and (a4 or d4)-vacancy are equivalent in the sense that they differ only in the first move (this equivalence can be seen in the solution catalog).

If the game now seems easy to you, try finding a solution to the c5-complement that finishes with a 5-sweep. This is the longest sweep that can appear in any solution, and is only possible for the c5-complement. How do we know this? It can be shown using the Solution Catalog below, which lists the shortest possible solution for all problems on this board (shortest in terms of the number of moves). If a solution exists which contains a 6-sweep (or longer), then it would have 8 moves or less (remember, there are only 13 pegs total to be jumped, and a 6-sweep captures 6 of them in one move). Since the solution catalog contains no solution with less than 9 moves, it's not possible. Of course this depends on the solution catalog being correct, so technically it's a "computer proof" rather than a logical proof. A logical proof may also be possible, by showing that all sweeps of length 6 lose at least 3 in the SAX count.

A variant of this board sometimes seen is to add two extra holes beyond each corner in a symmetrical fashion. Such a modification of any null-class triangular board is also null-class. However, such a board is no longer gapless.

The Triangle(6) Board   Play Now!

This 21-hole null-class board is the smallest triangular board on which every single vacancy complement problem is solvable. All of the 29 single vacancy to single survivor problems are solvable on it, and can be found in the solution catalog. Unfortunately, the SAX count that was so useful on the Triangle(5) board does not appear to generalize to larger triangular boards.

A computer analysis of the a1-complement reveals that the first four jumps can be arbitrary, but it's possible to make a bad fifth jump and reach a board state from which a solution cannot be reached. For example the computer claims that the moves a3-a1, c3-a3, e5-c3, c5-e5, b4-d4 take you to a board position from which the a1-finish cannot be reached (although a solution is possible before the 5th move). Still, it is clear that there are many more solutions to the a1-complement on this board compared to Triangle(5) (of course there are also many more dead ends).

The largest number of pegs that can be left stranded in this puzzle is 12. In fact, no matter which hole is originally vacant, you can finish at a 12-peg position with no moves remaining. What do these positions look like?

One surprising fact is that all single vacancy to single survivor problems on this board can be solved in 9-11 moves, the same number of moves as the Triangle(5) board can be solved in! In fact, on average these problems can be solved in fewer jumps.

The longest sweep that can appear in any solution to a single vacancy to single survivor problem on this board has length 9=3T(2). There are three problems on this board for which the 9-sweep can occur, these are interesting to work out by hand:

  1. Vacate c5, play to finish at a1 with the last move a 9-sweep.
  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. The 9-sweep begins and ends at a5.
You can go nuts trying to solve these playing forward. The trick, of course, is to attempt to play backwards from the complement of the position before the long sweep. Working backwards these problems are actually fairly easy to solve, once you figure out what the 9-sweep must look like.

The solution to the first problem is shown at the top of this page (played backward and then forward, with some move reordering being performed). This solution (or one essentially the same) was discovered before 1975 by Harry Davis, and can be found in Martin Gardner's book Mathematical Carnival [B2].

The first problem can be solved in a minimum of 9 moves, which is the shortest possible for this single vacancy to single survivor problem. The other two problems can be solved in a minimum of 10 moves, but a 9-move solution to the problem can be found if the 9-sweep requirement is dropped (see the solution catalog for these).

The Triangle(7) Board   Play Now!

This is the first interesting triangular board that is not null-class. It has 28 holes and although no complement problem is solvable on it, there are 27 single vacancy to single survivor problems solvable on it.

Any solvable single vacancy problem on this board can be reduced to a single peg in 12 moves, but no fewer. To view these solutions, see the solution catalog.

After making only 9 jumps, it is possible to reach a board position with 18 pegs remaining, but with no jumps possible. Can you figure out the starting position and jumps for this "worst possible game"? [Hint]

This is also the smallest triangular board where a solution to a single vacancy to single survivor problem can go through a board position with rotational symmetry. An interesting puzzle is to come up with such a solution. You can try this puzzle right now on my web game. [Hint]

The Triangle(8) Board   Play Now!

This 36-hole null-class board has many interesting properties. It is the triangular board closest in size to the English 33-hole board. There are 80 distinct single vacancy to single survivor problems on this board. Finding short solutions by hand is difficult, yet in 1975 a 14-move solution was found by Harry Davis and Wade Philpott [B2]. In our notation, they gave a solution to the problem: "vacate c5, finish at c8".

Davis and Philpott state that "14 move solutions are minimal" [B2]; but using a computer, I have found 13-move solutions. There is no 13-move solution which begins from the interior, so the Davis and Philpott solution is in fact minimal for that particular problem. Perhaps their statement refers only to this particular problem.

All 13-move solutions begin from the edge, and in fact there is a 13-move solution starting from any edge hole (not counting the corners, of course). One can start from the a7 vacancy and play a5-a7, then in 12 more moves it is possible to finish at any of a1, d4, c5, b6, e6, a7, g7 or f8. These same solutions can be reached starting with a4 vacant, by playing a6-a4 as the first move. The only other possibility for a 13-move solution is to begin with c8 vacant, from which we can finish in 13-moves at a4, c5, b6, e6, a7 or g7. You can see from all this that there is only one complement problem solvable in 13-moves, the a7-complement (or symmetric equivalents: the a2, b2, g7, b8 or g8 complement).

Using straight exhaustive search, it takes many hours, even weeks, to find short solutions on this board. However, Merson Regions [W1] are a powerful way to reduce the search space; and using them a computer can demonstrate that no 12-move solution exists in a few seconds of CPU time, and find all 13-move solutions in a few minutes.

The longest sweep geometrically possible on this board has length 18=3T(3). In 1975, Davis and Philpott [B2] gave a solution ending with a 15-sweep, and believed that this was the longest sweep possible in a single vacancy to single survivor game. However I have shown that the 18-sweep sweep can in fact be reached. As with Triangle(6), there are again 3 problems involving the 18-sweep:

  1. Vacate c5, play to finish at a1 with the last move an 18-sweep.
  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. The 18-sweep begins and ends at c7.
All of these problems can be solved in a minimum of 15 moves. The solution to the first problem can be found in [W1].

Larger Triangular Boards   Play Now!

Can long sweeps be found in solutions on larger triangular boards? The brief answer is yes, and I refer you to my paper [W1]. While Triangle(6) and Triangle(8) support the longest possible (maximal length) sweeps, it appears that game on larger triangular boards cannot contain maximal sweeps. However, rather remarkably, it is possible to construct a solution to a single vacancy to single survivor problem that finishes with a sweep of arbitrarily large length! For details, see [W1].

On Triangle(9), can any single vacancy to single survivor problem be solved in 15 (or fewer) moves? In 2005, I completed calculations that show the answer is ... no. I have found 16-move solutions, therefore these are the shortest possible on this board.

On Triangle(10), the shortest possible solution has 18 moves. This is the largest board (55 holes) on a triangular grid for which a solution having minimal length is known. The major difficulty here is not finding an 18-move solution, it is in demonstrating that there can be no 17-move solution to any possible single vacancy to single survivor problem.

* A web page on large triangular boards

Hexagonal Boards

Hexagonal boards are the analog of square boards in the triangular lattice world (specifically, they have the highest symmetry possible among all gapless boards). A hexagonal board of side n, will be referred to as Hexagon(n). This board has 6T(n-1)+1 = 3n(n-1)+1 holes: 1, 7, 19, 37, 61, 91, ... The board Hexagon(n) is a null-class board if (and only if) n is of the form 3i+2, so n=2, 5, 8, etc (this is equivalent to requiring that the diameter be a multiple of 3). Hexagonal boards always have a center hole. If a hexagonal board is not a null-class board, then the full board is in the same position class as a peg at the central hole. Therefore on such boards no single vacancy to single survivor problem is solvable which begins or ends at the center. The same notation as for triangular boards is used, where the leftmost hole on the top row is "a1".

Subtrax is a peg solitaire game marketed by ThinkFun. It was designed by the famous puzzle expert Nob Yoshigahara. The board is Hexagon(3) with three symmetric corner holes removed. This board is not null-class, and it is not clear to me why the three corners were removed. Most of the problems are small patterns, so the shape of the board is not that important.

The 61-hole Hexagon(5) board is the smallest hexagonal board where a complement problem is solvable, and in fact all complement problems on this board are solvable. This is also the smallest (gapless) board with 12-fold symmetry where the central complement problem is solvable. A solution to the central complement problem on this board can pass through board states with 6-fold rotational symmetry, a snapshot from such a solution is shown in the blue diagram above, with the full solution shown under the link below.

It is also possible to develop a theory for all 12-fold symmetric boards as was done for square-symmetric boards in the square lattice case [P3]. See the link below for this theory.

* A web page on hexagonal boards and 12-fold symmetry

Stellar Boards

We construct a stellar board by taking the board Hexagon(n), and adding six Triangle(n-1) boards symmetrically to each edge. The board that results we call Star(n). The Star(n) board has 12T(n-1)+1 = 6n(n-1)+1 holes: 1, 13, 37, 73, 121, 181, ...

Star(n) is null-class if (and only if) n is of the form 3i+2, so again n=2, 5, 8, etc.. The smallest stellar board on which every single vacancy complement problem is solvable is the 121-hole Star(5) board. This board is in fact the standard Chinese Checkers board (shown on the left)!

Star(2) is null-class and has 13 holes. No jump is possible into or out of the center hole. Other than problems beginning or ending at the center, all single vacancy to single survivor problems are solvable on this board, and all are fairly easy. This board seems quite a bit easier to solve than Triangle(5), and all problems can be solved in a minimum of 7 moves. All 7 move solutions consist of 6 moves starting at corners plus one "free" move. Below we show solutions to the two complement problems in 7 moves:

Null-class stellar boards also have the property that they can be cut into three identical null-class pieces, on larger boards this allows the central complement problem to again be solved in thirds. The central complement problem on the Star(5) board can also go through positions with 6-fold rotational symmetry.

Rhombus Boards

Rhombus boards are square boards drawn on a triangular lattice. One can also rotate them 60 degrees so that they have a diamond shape, which gives them a more pleasing symmetry. The nxn Rhombus(n) board has n2 holes and is null-class only when n is a multiple of 3. The Rhombus(n) board may also be thought of as a Triangle(n) and Triangle(n-1) board glued together.

The board Rhombus(6) is in fact the familiar 6x6 square board with the addition of moves along one diagonal. You can play this board using a 6x6 board with moves along one diagonal allowed, but I find this confusing and the symmetry of the board is hard to see. This board is very similar to Triangle(8), both are null-class, have 36 holes and single vacancy to single survivor problems can be solved in a minimum of 13 or 14 moves. There is no single vacancy to single survivor problem on Rhombus(6) solvable in 12 moves.

Rhombus boards are similar to triangular boards in that for n odd there exists a sweep that jumps over or into every hole in the board. The sweep must begin at one 120-degree corner and end at the other one. The length of this sweep, for odd n is (3n+1)(n-1)/4, for n=3, 5 or 7 this gives sweeps of length 5, 16 or 33, respectively. As with triangular boards, these sweeps can sometimes be reached on a board one larger in size. The figure above shows a 33-sweep on Rhombus(8) that can be reached from a single vacancy start. On Rhombus(2n), the sweep length may be calculated as (3n-1)(n-1). For much more on Rhombus boards, see [W2].

Propeller Boards

The first known triangular lattice board, from an 1891 parent, was a 16-hole "propeller board", shown to the left. This board may also be considered as a superposition of three Triangle(3) boards joined at their apex. This board is null-class, and the central vacancy complement problem is solvable. However, no other single vacancy to single survivor problem is solvable on the 16-hole propeller board.

The 16-hole propeller board can be generalized by overlapping three Triangle(n) boards at their apex. The resulting board Propeller(n) has 3T(n)-2 holes: 1, 7, 16, 28, 43, 61, ... Propeller(2) is the same as Hexagon(2). Propeller(3) is the 16-hole propeller board, Propeller(4) has 28 holes but is not null-class. It is not hard to show that Propeller(n) is null class if and only if the component boards Triangle(n) are null-class.

Hourglass Boards

Hourglass boards can be formed by merging two triangular boards tip to tip, with a choice of the degree of overlap. Physical boards have been marketed with this shape, having rows of width 5, 4, 3, 4, 5 (21 holes) or 7, 5, 4, 3, 4, 5, 7 (35 holes). These boards are both null-class and the center peg complement problem is solvable in either case.

Online Puzzles

The 15-hole Triangle(5) board is quite common, but other boards are very hard to find. But it's easy to create any board on a computer. This also has the added advantage of being able to include demos and the ability to take back moves.

Here is a list of the triangular games on this site. These are all written in JavaScript, and you must have JavaScript activated in your browser to view them. Works best with Internet Explorer.

I have also designed the (hexagonal) levels of a free online peg solitaire game. You will need to download Shockwave to use it. Thanks to Rob Gordon of Article19 for the GUI.

Solution Catalogs

Here is a complete listing of shortest length solutions for some of the boards above. These were calculated by computational search.

Given a board and a (solvable) single vacancy to single survivor problem, there is a minimum number of moves that can solve it. These solutions have an elegant look to them and they tend to be extremely hard to find by hand.

The table below shows a list of boards, together with some statistics about each. If you click on a board, you will see another table listing all single vacancy to single survivor problems solvable on that board, together with information about these solutions. These boards all have triangular symmetry, and we only list unique single vacancy to single survivor problems. In other words, if one problem can be obtained from another by rotation and/or reflection, only one will be listed. If you keep clicking on the tables, you can view diagrams of minimal length solutions. The solution catalog shown may be incomplete. Only those with a check mark before them can display all solutions. It is labor intensive producing these and they may not be complete for some time.

Some column heads you will see that require explanation:

Board Name [click to see catalog] Number
of Holes
Null-
Class?
Number of Problems Longest Sweep (any problem) Minimal Solution Properties
Solution Lengths Longest Sweep Time to Calculate
Star(2) 13 Yes 6 5 ‡ 7 5 .1 second
Triangle(5) 15 Yes 12 5 9-11 5 1 second
Triangle(6) 21 Yes 29 9 ‡ 9-11 9 30 seconds
Triangle(7) 28 No 27 ≥11 12-13 ≥11 2 hours
Triangle(8) 36 Yes 80 18 ‡ 13-15 ≥16 2 days
Rhombus(6) 36 Yes 120 16 ‡ 13-14 ≥13 2 days
Table Footnotes: (‡) This is the longest sweep geometrically possible on this board, and at least one such sweep can be realized as the final move to a single vacancy to single survivor problem.

How Hard Is Peg Solitaire?

Most people have a hard time solving the Triangle(5) board by hand, and Triangle(6) is more difficult. Let us consider the complement problem on an arbitrarily large (null-class) triangular board. We just want to find any solution to this problem, not the shortest solution like you see in the solution catalogs. Intuitively, it seems obvious that the larger the board, the harder this must be to solve. This seems to be confirmed by exhaustive computer search calculations. Many people (including myself) have written programs that try to find a solution by going through all possible jump sequences, or all possible board states that can be reached. If you apply such programs to larger and larger boards, the time to find a solution increases exponentially, until at some point, your program will not be able to find a solution after running many hours.

However, I have been able to show that far from being obvious, the intuition above is actually incorrect, and that the complement problem does not get harder as the board size increases! The trick here is to show that solutions to smaller boards can be used inside of larger boards in an inductive fashion. For example a solution on Triangle(6) can be used to solve one corner of a much larger board, with all remaining areas cleared by chains of block removal moves (these are combinations of jumps that remove a whole block of pegs, leaving the rest of the board unchanged, see [W3]).

What does all this mean? It does not mean that peg solitaire is trivial, it means that the complement problem isn't really much harder for larger boards. If you proceed using an exhaustive search technique, or random moves, you are bound to have a much harder time the larger the board is. However the optimal search technique doesn't have any trouble with large boards of regular, predictable shape. An example of such an algorithm can now be found in my Triangular Peg Solitaire Game (the algorithm is described in [P4]).

Here we have considered playing from a board state that is entirely full (except for one hole) to a board state with one peg. It is critical that the starting configuration is a completely uniform pattern, except for the one vacancy. For it has been shown in the case of a square lattice, the general problem of determining if an arbitrary pattern of pegs can be reduced to one peg is NP complete [P3]. From a practical standpoint this means that any algorithm to solve this problem must have a run time that increases exponentially with the problem size. The complement problems are a tiny subset of such problems that can be solved very quickly (probably linear time).

Triangular Peg Solitaire References

See also ordinary (square lattice) peg solitaire references.

Books

  B1. John D. Beasley, The Ins & Outs of Peg Solitaire, Oxford Univ. Press, 1985 (the paperback Edition 1992, contains an additional page: Recent Developments) ISBN 0-19-286145-X (paperback).
B2. Martin Gardner, Mathematical Carnival, Random House, 1975, pp. 15-16 & 268-270, ISBN 0-39-449406-7.

Papers

  P1. Irvin Hentzel and Robert Hentzel, Triangular Puzzle Peg, Journal of Recreational Mathematics, 1986, Vol 18, p. 253-6.
P2. John Duncan and Donald Hayes, Triangular Solitaire, Journal of Recreational Mathematics, 1991, Vol 23, p. 26-37.
P3. Ryuhei Uehara and Shigeki Iwata, Generalized Hi-Q is NP-complete, Trans. IEICE, E73, pp.270-273, 1990
P4. George I. Bell, Solving Triangular Peg Solitaire, Journal of Integer Sequences, Vol 11 (2008), article 08.4.8

Web References

W1. Triangular Peg Solitaire Unlimited (pdf version), Issue #36 (web version) of The Games and Puzzles Journal, Nov-Dec 2004. This paper shows how to construct solutions on triangular boards that finish with sweeps of arbitrary length.
W2. Diamond Solitaire (pdf version), Issue #41 (web version) of The Games and Puzzles Journal, Sep-Oct 2005. This paper shows how to construct solutions on rhombus boards that finish with sweeps of arbitrary length.
W3. Cut The Knot contains a good description of how to solve peg solitaire problems using block removals (called packages and purges, Conway's terminology).
W4. Sidney Graham has an excellent site for 15-hole triangular peg solitaire. There are many sample problems and solutions, together with theory.
W5. Jurgen Koller's Peg Solitaire web site lists many printed references to triangular peg solitaire.
W6. Eric Weisstein has a short page on mathworld.wolfrom.com that describes the 15-hole board and lists many printed references.
W7. Durango Bill has a page on 15-hole triangular peg solitaire.
W8. Dan O'Brien has a page on 15-hole triangular peg solitaire with an exhaustive list of solutions.
W9. Don Hartzler has a page on 15-hole triangular peg solitaire where you can view solutions.
W10. Ken Duisenberg also had a triangular peg puzzle for his problem of the week (Dec 3, 1997 and also Nov 11, 2005). The second part of the 1997 problem involves a square grid with diagonal jumps allowed. His comment that this problem originated in 400 AD is incorrect!
W11. The On-Line Encyclopedia of Integer Sequences, see sequences A120422, A127500, A130515, and A130516.

Copyright © 2006–2014 by George I. Bell

To square lattice peg solitaire    To the peg solitaire army
To my home page