

These pages were created and are maintained by George Bell (gibell@comcast.net) Last Modified January 24th, 2015 Copyright © 2006–2015 by George I. Bell 


Leave only one — you're genius, ... Leave four or more'n you're just plain "egnoramoose". Cracker Barrel peg game instructions 
The origin of triangular peg solitaire is not known, although it is certainly well over 100 years old. The earliest known reference is a US patent from 1891 for a 16hole propeller board. This patent does not mention the 15hole triangular board, but it the first (known) description of peg solitaire played on a triangular grid. The earliest known reference to the 15hole triangular board is a 1932 booklet titled Puzzle Craft, edited by Lynn Rohrbough [B2].
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 (3removal, 2removal, 6removal, and Lmove [B1], [W3]) carry over to triangular solitaire and are equally useful. However, the 15hole and 21hole 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:
Where can you buy a board? There are many companies that sell the 15hole triangular board, my favorite is made by Venture (shown in the above photo). It is difficult to find physical versions of the larger boards, one possibility is to use a Chinese Checkers set. A Chinese Checkers set can be used for triangular boards up to Triangle(13), as well as hexagonal and stellar boards. For online puzzles, see my online triangular peg solitaire game.
On the 15hole 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 33hole English Board, short solutions have for the most part not been considered in triangular solitaire. We will discuss the shortest possible solution for most boards below.

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. "a3a1". The loop move from a1 of length 3 is abbreviated "a1a3c3a1".
Any hole on the board that cannot be jumped over is called a corner hole.
A triangular board has 3 corners,
and a hexagonal board has 6 corners.
The number and geometry of the corners is an important aspect of any peg
solitaire board.
We will call a board gapless if for any two holes which are on a line
parallel to the three jumping directions,
all the intervening holes are also part of the board.
Most of the boards on this page are gapless, one exception is
Propeller(n) for n>2.
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.
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.

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_{1}, N_{2} or N_{3} increases by one while the other two decrease by one. Therefore the evenness or oddness of the differences TN_{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: (TN_{1},TN_{2},TN_{3}). As you play solitaire you cannot leave the position class that you start in. [You might think there should be 2^{3} or 8 position classes. However the numbers N_{i} are not independent, because T = N_{1}+N_{2}+N_{3}, and this implies that either two of the three TN_{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 nullclass 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 nullclass 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 nullclass. 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 nullclass, 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 nullclass boards on a square lattice.
We may summarize all this by the following rules:
From a practical standpoint, how do we determine whether a particular board is nullclass 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 nullclass, 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 nullclass.
A Triangle(5) board made in Japan, imported by William A. Rogers (photo courtesy Richard Chabot) 
In fact if the triangular board is not nullclass 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 loop that jumps into or over every single location on
the board!
The length of this sweep is
Consider now a nullclass 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_{1}=N_{2}=N_{3}, and hence the board position is in the position class of the empty board. This proves that on a nullclass triangular board, no solution to a single vacancy to single survivor problem can go through a board position with rotational symmetry. We shall see that solutions on triangular boards that are not nullclass (i.e., n=7), or nullclass hexagonal boards can go through positions with rotational symmetry.
This board provides a simple example which can yield insight for larger boards.
For example, it is easy to find all solutions by hand to the problem starting with a2 vacant.
The diagram below
(copied from [P5])
shows the solutions in the form of a directed graph.
The total number of solutions is simply the number of ways to traverse this graph.
The number below each node shows the number of ways to reach it from the start,
so we see that there are exactly 14 solutions to this peg solitaire problem.
The same technique can be used to count solutions on larger boards,
although the graph rapidly becomes too large to display.
For example, on Triangle(5),
the corner complement problem has 6,816 solutions.
The above diagram contains several interesting symmetries.
For example, the number of board positions after n jumps
is the same as the number of board positions n jumps from the finish.
There are other, more subtle symmetries present as well.
For example, every board position on the left appears on the right,
complemented and reflected.
The middle four board positions are complements and reflections of one another.
In fact, the solution graph for every complement problem
contains these symmetries, as shown in [P5].
The alert reader may note that the above diagram is not for a complement problem,
but it still may be considered as a kind of generalized complement problem where we
finish at a reflection and/or rotation of the starting board position.

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 righthand 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. a2a4 or d4b2. 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 b3complement 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 a1complement 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 a1complement 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 a3a1. The second jump c4a2 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 a5a3 is also a dead end, for although a5a3 doesn't lose anything, all third jumps from this position lose 1. Therefore the only choices for the second jump are c3a3 and c5a3, 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 a1complement can be derived from the following two solutions:
Type 1: 
{a3a1, c3a3, b5b3, d5b5, a5c5, e5c3, b2d4, c5c3}, then {a4a2, d4b2}, followed by {a1a3, a3c3, c3a1} (or the reverse). 
Type 2: 
{a3a1, c5a3, a5c5, d5b5, c3c5, b5d5, e5c5, a1c3}, then {d4b2, a4a2}, followed by {b2b4, c5a3, a3a1} (or the reverse). 
A metal Triangle(5) board with brass pegs (photo courtesy Richard Chabot) 
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 a1complement 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 a1complement must pass through an intermediate position with symmetry about the yaxis, 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 OnLine 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? [Hover here for the answer]
For all problems on this board, 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:
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 a1complement 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:

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 c4a4 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 a4vacancy must begin with the move a2a4, and solutions to the a1vacancy 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 c5complement that finishes with a 5sweep. This is the longest sweep that can appear in any solution, and is only possible for the c5complement. 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 6sweep (or longer), then it would have 8 moves or less (remember, there are only 13 pegs total to be jumped, and a 6sweep 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, giving a 21hole board
shown on the right.
Such a modification of any nullclass triangular board is also nullclass,
but is no longer gapless.
The 21hole board proves awkward to play on, because removal of each of the
six corner pegs removes a peg at the locations
(on the original Triangle(5) board) L={a1,a3,c3,a5,c5,e5}.
This means that a starting vacancy from any hole in L or any
corner is unsolvable to one peg.
By coloring the holes on the board as shown on the right, we may state the problems on this board in the following way: "Fill the board with pegs and remove one peg at a particular color. Play to finish with one peg at any hole of the same color (including the one you started from). All these problems are solvable."

There are 10 single vacancy to single survivor problems on Truncated Triangle(5), each can be solved in a minimum of 6 to 8 moves. The following table shows the length of the shortest solution for each of these 10 problems on the blue board locations. The board notation is the same as for Triangle(5), shown in the right column.
An interesting challenge is to find a 6move solution on this board. Note that this board has 6 corners, a 6move solution must consist of one move beginning from each corner. Here is a solution.
The Truncated Triangle(5) board is probably the smallest gapless board on the triangular lattice on which the complement problem is solvable at any hole. It is certainly the smallest board with this property with 120 degree rotational symmetry.
To my knowledge, a commercial copy of this board has never been produced.
Rather surprising considering the number of versions of the standard
Triangle(5) board you can buy.
A computer analysis of the a1complement 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 a3a1, c3a3, e5c3, c5e5, b4d4 take you to a board position from which the a1finish cannot be reached (although a solution is possible before the 5th move). Still, it is clear that there are many more solutions to the a1complement 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 12peg 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 911 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
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]. To see the solutions to all three problems, see
A solution page about 9loops on Triangle(6)
Play the 18hole truncated Triangle(6) board
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"? [Hover for 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.
[Hover for hint]
Davis and Philpott state that "14 move solutions are minimal" [B2]; but using a computer, I have found 13move solutions. There is no 13move solution which begins from the interior, so the Davis and Philpott solution is in fact minimal for that particular problem.
All 13move solutions begin from the edge, and in fact there is a 13move solution starting from any edge hole (not counting the corners, of course). One can start from the a7 vacancy and play a5a7, 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 a6a4 as the first move. The only other possibility for a 13move solution is to begin with c8 vacant, from which we can finish in 13moves at a4, c5, b6, e6, a7 or g7. You can see from all this that there is only one complement problem solvable in 13moves, the a7complement (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 12move solution exists in a few seconds of CPU time, and find all 13move solutions in a few minutes.
The longest sweep geometrically possible on this board has length
A solution page about 18loops on Triangle(8)
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 16move 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 18move solution, it is in demonstrating that there can be no 17move solution to any possible single vacancy to single survivor problem.
A web page on large triangular boards
Subtrax is a peg solitaire game marketed by ThinkFun, it was designed by puzzle expert Nob Yoshigahara. The board is Hexagon(3) with three symmetric corner holes removed, resulting in a 16hole board. This board is not nullclass, 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 61hole 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 12fold symmetry where the central complement problem is solvable. A solution to the central complement problem on this board can pass through board states with 6fold 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 12fold symmetric boards as was done for squaresymmetric boards in the square lattice case [P3]. See the link below for this theory.
A web page on hexagonal boards and 12fold symmetry
Star(n) is nullclass 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 121hole Star(5) board. This board is in fact the standard Chinese Checkers board (shown on the left)!
Star(2) is nullclass 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:
Nullclass stellar boards also have the property that they can be cut into
three identical nullclass 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 6fold rotational symmetry.
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 nullclass, 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 120degree corner
and end at the other one.
The length of this sweep, for odd n is
The 16hole propeller board can be generalized by overlapping three Triangle(n) boards at their apex.
The resulting board Propeller(n) has
We can further generalize by overlapping the three boards over more than just the apex hole.
For example, if we overlap three Triangle(4) boards across their top three holes we obtain
the 12hole board mentioned previously as
Truncated Triangle(5).
A sweep of length 15 can be reached on the 33hole Hourglass board from a singlevacancy start,
one possible sweep move is shown on the right.
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. Unfortunately, these don't work well on mobile devices with touch sensitive screens, due to the lack of a mouseover equivalent.
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  911  5  1 second 
Triangle(6)  21  Yes  29  9 ‡  911  9  30 seconds 
Triangle(7)  28  No  27  ≥11  1213  ≥11  2 hours 
Triangle(8)  36  Yes  80  18 ‡  1315  ≥16  2 days 
Rhombus(6)  36  Yes  120  16 ‡  1314  ≥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. 
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).
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 019286145X (paperback).  
B2.  Martin Gardner, Mathematical Carnival, Random House, 1975, pp. 1516 & 268270, ISBN 0394494067 [in Chapter 2, "Penny Puzzles"]. 
P1.  Irvin Hentzel and Robert Hentzel, Triangular Puzzle Peg, Journal of Recreational Mathematics, 1986, Vol 18, p. 2536.  
P2.  John Duncan and Donald Hayes, Triangular Solitaire, Journal of Recreational Mathematics, 1991, Vol 23, p. 2637.  
P3.  Ryuhei Uehara and Shigeki Iwata, Generalized HiQ is NPcomplete, Trans. IEICE, E73, p. 270273, 1990.  
P4. 
George I. Bell,
Solving Triangular Peg Solitaire,
Journal of Integer Sequences, Vol 11 (2008),
article 08.4.8
(the ArXiv link is the best version, because it contains some additional comments at the end).  
P5.  George I. Bell, Notes on solving and playing peg solitaire on a computer, last updated 2014. 
W1.  Triangular Peg Solitaire Unlimited (pdf version), Issue #36 (web version) of The Games and Puzzles Journal, NovDec 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, SepOct 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 15hole 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 15hole board and lists many printed references.  
W7.  Durango Bill has a page on 15hole triangular peg solitaire.  
W8.  Dan O'Brien has a page on 15hole triangular peg solitaire with an exhaustive list of solutions.  
W9.  Don Hartzler has a page on 15hole 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 OnLine Encyclopedia of Integer Sequences, see sequences A120422, A127500, A130515, and A130516.  
W12.  Jaap Scherphuis has a peg solitaire web page, with a nice discussion of the Think and Jump and Triangle(5) boards. Jaap also has a Peg Solitaire Java Applet.  
W13.  Warren Porter has written a javascript web page which can solve the Triangle(5) board. 
Copyright © 2006–2014 by George I. Bell