Triangular Peg Solitaire
These pages were created and are maintained by George Bell (gibell@comcast.net) Last Modified January 9th, 2009 Copyright © 2007 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
• Just show me how to solve the Cracker Barrel Puzzle (15-hole board)!
• Preliminaries
• Boards: Triangular (4), (5), (6), (7), (8), Hexagonal, Stellar, Rhombus
• Online Games and Puzzles
• Solution Catalogs
• How Hard Is Peg Solitaire?
• References

Introduction

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. A board composed of staggered squares (with centers at the same points as the hexagon centers).
4. On a square lattice with the understanding that "normal" (square lattice) moves plus those along one diagonal are allowed (see the figure below, left board).

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

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

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 N_i(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 N₁, N₂ or N₃ increases by one while the other two decrease by one. Therefore the evenness or oddness of the differences T-N_i 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-N₁,T-N₂,T-N₃). As you play solitaire you cannot leave the position class that you start in. [You might think there should be 2³ or 8 position classes. However the numbers N_i are not independent, because T = N₁+N₂+N₃, and this implies that either two of the three T-N_i are odd or they are all even].

Consider the board position with every peg filled. On the above board T=21 and N_i=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 (x₀,y₀). Then we can only finish with a single peg at board positions (x₁,y₁) where (x₁-x₀)-(y₁-y₀) 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

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 (although Rhombus boards also share this property). From any board location, the total number of possible jumps 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(n²-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 N₁=N₂=N₃, 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 postion 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!

The Triangle(5) Board   Play Now!

Board Notation	The SAX count

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}

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!

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.

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!

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 what this "worst possible game" looks like?

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. Hint: try starting with c6 empty and play: e6-c6, c4-e6, b5-d5. Can you now solve this rotationally symmetric board position to one peg? You can try this puzzle right now on my web game.

The Triangle(8) Board   Play Now!

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.

Larger Triangular Boards   Play Now!

On Triangle(9), can any single vacancy to single survivor problem be solved in 15 (or fewer) moves? I have recently completed calculations that show the answer is ... no. I have found 16-move solutions, therefore these are the shortest possible on this board. Here is an example of a solution in 16 moves: a4-a2, a6-a4, c5-a3-a5, e7-c5(4), g9-e7, d4-d6-f8, i9-g9-e7, f6-d4-b4-d6-f8(8), c7-c5, a1-a3, h8-f6, e9-e7(12), c9-c7, a9-c9-e9-g9-g7-e5, b2-d4-f6-d6-b4, a8-c8-e8-g8-e6-e8-c6-a4-c4-a2-a4-a6-c6-c8-a6-a8(16).

A web page on large triangular boards

Hexagonal Boards

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

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

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].

Online Puzzles

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.

• Ultimate Triangular Peg Solitaire ( http://tinyurl.com/2v53ya , 2006) This online game allows you to play on triangular boards as large as Triangle(24). If you get stumped, the computer can solve the problem for you.
• "Never Lose" Triangular Peg Solitaire ( http://tinyurl.com/5rh2rx , 2008) On Triangle(4), Triangle(5) and Triangle(6), this version has the ability to point out all jumps that lead to a dead end. This tends to make the puzzle seem trivial!

Solution Catalogs

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:

• Number of Problems: This is the number of different solvable single vacancy to single survivor problems on this board (not including problems equivalent by symmetry).
• Longest Sweep: The first column is the longest sweep possible in any single vacancy to single survivor problem, regardless of solution length. The second "Longest Sweep" column is the longest sweep possible in a minimal length solution.
• Solution Lengths: This is the range in the number of moves in the minimal length solutions, over all problems.
• Time to Calculate: This is the amount of CPU time that was needed to calculate the underlying table (find all minimal solutions to all problems).

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?

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

Books

Papers

Web References

Copyright © 2009 by George I. Bell

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