Peg Solitaire 

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


We can merely mention beanbags, pegboards, size and form boards, as some apparatus found useful for the purpose of amusing and instructing the weakminded. Albutt's "System of Medicine", 1899, VIII, 246 [B3] 

The basic game consists of a crossshaped board, usually made of wood, together with a set of pegs, or more commonly marbles. To start the game, one fills the board with pegs except for the central hole. A jump consists of jumping one peg over another into an empty spot in the board, removing the peg jumped over from the board. Diagonal jumps are not allowed (in the standard version of the game). The goal is to choose a sequence of jumps and finish with as few pegs as possible, ideally a single peg in the center.
It seems almost everybody has run into this puzzle at some point. Boards range from drilled planks using golf tees, to beautifully crafted hardwood boards with indentations for marbles, including a nice rim around the edge for storage of marbles as they are removed. Computer versions of the game are also common (see my Javascript games below).
After unsuccessful attempts at a "manual solution", many people (myself included) try to write a simple computer program to solve it. Even if there are only 48 jumps available at each board position, this can lead to a prohibitively large number of possible jump sequences after only 15 jumps. This game is much older than the computer, and it is remarkable how much was proved about this game without the aid of computers.
Instead of trying to memorize a computer solution, or a YouTube video, the best way to remember a solution is to understand "block removals" or "packages", sequences of moves that remove a whole block of pegs but leave the rest of the board untouched. Once you understand and have mastered the "3removal", "6removal" and "Lmove", the central game rapidly goes from frustrating to being quite simple (see [B1], [B3], [W2] or [W20] for details). This is similar to Rubik's cube in that you memorize a specific sequence of moves that place you closer to your goal but do not mess up the rest of the board.
After the central game above has been solved, what then? We can try to define the "best possible" solution. All solutions have exactly 31 jumps, because we start with 32 pegs and one is lost with each jump. However, when the same peg jumps one or more pegs, we call this one move. The 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? This question turns out to be much harder to answer than simply finding a solution to the central game. The following terminology is useful 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 nsweep. A sweep that begins and ends at the same board location is called a loop.
The boards on this page have holes based on a square lattice; each hole has (at most) 4 neighbors. It is also possible to play on a triangular lattice, where each hole has (at most) 6 neighbors. I now have a separate page for Triangular Peg Solitaire. If you want some tips and solutions for the 15hole triangular board, check out my page on tips and solutions for the Cracker Barrel Puzzle.
We need some kind of notation to identify board locations. On the crossshaped 33hole board the most common notation is to label the board columns ag (left to right) and the rows 17 (top to bottom). This notation works well for any board that fits inside a 7x7 square, and is referred to as "Standard 7x7 Notation". An alternative notation where the holes are numbered consecutively is not recommended because it must be changed every time the board shape changes.



Standard 7x7 Notation [used by Beasley] 
The bulky but general alternative: Cartesian Coordinates 
For larger boards, this coordinate system must be extended. "Standard 9x9 Notation" is the obvious extension, where the columns are ai and the rows 19 (the most interesting boards have an odd width, and that is why we go from 7x7 to 9x9). An unfortunate aspect of this notational switch is that the central hole goes from being called "d4" to "e5". An alternative notation is Cartesian Coordinates, where the center of the board is (0,0).
In standard 7x7 notation, to refer to a jump we simply list the starting and ending board locations separated by a dash, i.e. "e5e3" for one of the jumps available above, and "e5e3c3a3" for the 3sweep move "e5e3, e3c3, c3a3".
Any hole on the board that cannot be jumped over is called a corner hole. The standard board above has 8 corners: c1, e1, a3, g3, a5, g5, c7 and e7. 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 board locations in the same row or column, all the intervening points are also on the board. All of the boards on this page are gapless, and this concept is mainly useful to exclude pathological boards with interior holes or gaps along the edge.
A board is called rectangularsymmetric if it is unchanged when reflected about the x or yaxes, and rotationallysymmetric if it is unchanged by any 90 degree rotation. A board is called squaresymmetric if it is both rectangularsymmetric and rotationallysymmetric. Finally, a squaresymmetric board with a unique central hole is called odd because its width is odd, and it also has an odd total number of holes. We see that the board above is odd, squaresymmetric and gapless.
Consider a diagonal labeling of the board holes (in two ways) as shown below:


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 (and similarly for N_{4}, N_{5}, N_{6}). 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 sixteen position classes depending on the parity (even or oddness) of the six numbers: (TN_{1},TN_{2},TN_{3},T N_{4},TN_{5},TN_{6}). As you play solitaire you cannot leave the position class that you start in. [You might think there should be 2^{6} or 64 position classes. However the numbers N_{i} are not independent, because T = N_{1}+N_{2}+N_{3} = N_{4}+N_{5}+N_{6}, and this implies that among (TN_{1},T N_{2},TN_{3}), there are either zero or two odd parities (and similarly for the other half) and the number of position classes is reduced to 2^{4} or 16].
At the standard starting position with only the center hole vacant, you can easily check that N_{1}=N_{3}=N_{4}=N_{6} =11, N_{2}=N_{5}=10, and the total number of pegs T=32. Therefore the 6 starting parities (TN_{i}), i=1,2, ... 6 and therefore the position class of the board is (Odd, Even, Odd, Odd, Even, Odd). All board positions reachable from this starting position must be in this same position class. The position class of a board position with only a single peg is easy to calculate, it is odd on all diagonals except for the two the peg is in. Hence we see that the only possible finishing locations for the game must be the intersections between diagonals 2 and 5, or the board locations (0,0)=d4, (3,0)=g4, (0,3)=d1, (3,0)=a4 or (0,3)=d7.
Consider the board position with every hole filled by a peg. Then T=33, N_{i}=11 for all i, and all six parities are Even. The empty board with no pegs also lies in the same position class: (Even,Even,Even,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). It is important to realize that nullclass boards are special, and not all boards are nullclass boards.
By using the parity argument above, one can easily prove the following two facts about nullclass boards:
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, 3's through 6's. If these six 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 (vertically or horizontally). A solitaire move itself is such a transformation, but there are others, such as removing three pegs in a row, or replacing two pegs separated by a hole by a peg in the hole. Using this technique we can discover which position class any pattern of pegs is in, and which finishing holes are possible.
A 33hole board from India, 1830 © 2003 puzzlemuseum.com 
The English Board has more going for it than a pleasing shape. It is the smallest squaresymmetric, gapless board on which the central game is solvable (see [P3]). In fact, it is the smallest such board for which every complement problem is solvable.
Ernest Bergholt found an 18move solution to the central game in 1912. In 1964, John Beasley proved that there is no shorter solution to the central game [B1]. Since then the problem of finding minimal length solutions has been attacked by many people using a computer, and minimal length solutions to all single vacancy to single survivor problems have been found. In 2012, Joseph Barker and Richard Korf [P7] applied Computer Science search techniques to this problem, their search algorithm can find Bergholt's solution using less than 3 seconds of CPU time. They can find shortest solutions to all 21 single vacancy to single survivor problems using less than 2 minutes of CPU time [P7].
Over the years, there have been various attempts to describe a solution to the central game that is easy to remember. Bergholt's 18move solution is shortest, but tends to be difficult to recall. Nonetheless, a specialized "Wolstenholme notation" has been invented to assist in recalling it [W19]. Another solution, called "Jabberwockey", is given in Martin Gardner's book [B2]. This solution has some nice symmetry properties, which make it easier to remember, as well as faster because one captures pegs with both hands simultaneously during the solution. Click here to see a diagram of this solution (paired moves are shown in red).
My personal favorite easy to remember solution to the central game requires that you memorize the Lmove (see [W2] under LPackage). Start with d6d4, b5d5, and now focus in on the (purple) Lshaped region defined by L1={c4, c5, c6, c7, d7, e7} (see the diagram on the left). The Lmove consists of three moves (four jumps) whose net effect is to complement or reverse the state of the pegs in L1: c7c5, c4c6, e7c7c5. We now do the Lmove on the other three arms of the cross. First, c2c4 to open up (red) L2={d3, c3, b3, a3, a4, a5}, then the second Lmove: a3c3, d3b3, a5a3c3. Next, f3d3 to open up (blue) L3={e4, e3, e2, e1, d1, c1}, then the third Lmove: e1e3, e4e2, c1e1e3. Finally, e6e4 to open up (orange) L4={d5, e5, f5, g5, g4, g3}, then the last Lmove: g5e5, d5f5, g3g5e5. This leaves you in the "house" board position shown on the right. Notice that a seven jump move is available starting from d3, take it only five jumps (you don't want to get greedy!): d3f3f5d5b5b3. The solution concludes with a 3removal (see [W2] under 3Purge) on {c4, d4, e4}: c3c5, e4c4, c5c3, b3d3, d2d4. Click here to see a diagram of this solution.
If diagonal jumps are allowed, what is the shortest solution to the central game? In Beasley's book [B1] this is given as an open question. Using a computer, it is not so easy to find the minimal length solution because the number of moves from each board position is approximately double. In 2007, I was able to finish the calculation, and the shortest solution has 15 moves [P4].
A web page on the shortest solution when diagonal jumps are allowed.
A page with example computer calculations by
level for the English 33hole board.
This board does have one unusual property: it is possible for any peg on the board to reach some corner. No matter where the final peg is to be left, it is possible to arrange things so that the last four moves start from the four corners. If this board is easy for you try finding solutions with this property. Click here to see an elegant 15move solution with this property, due to John Harris [W1]. Here is another one I found. It is not always possible to have a minimal length solution with this corner finish property.
A double vacancy complement problem
is a puzzle where two pegs are removed at the start,
and your goal is to finish with two pegs in the original vacancies.
On the 6x6 board, all 93 double vacancy complement problems are solvable
(unlike the English 33hole board,
where four double vacancy complement problems are not solvable
[B1, p. 1069]).
It is tedious to find solutions for the 93 cases,
but all are solvable (here is a
sample solution).
The 6x6 board is not the smallest board where all double vacancy complement problems are solvable,
the 6x4 rectangular board also has this property.
Nonetheless, there are ten single vacancy to single survivor problems solvable on this board, and each can be solved in 20 or 21 moves. If you are solving a problem by hand, the best technique to use (on any board) is to decompose it into block removals. Note that the French board decomposes nicely into L and 3removals as shown in the figure on the right. In order to solve a particular problem, one can modify this diagram with appropriate starting and ending moves, as shown in the figures on the left.
In each diagram, the location of the starting hole is marked by an "S", and the finishing hole by an "F". After dividing the board up into block removals, one must also check that the catalyst needed by each block removal is present. The sequencing of the block removals is indicated by the numbering. If you don't understand how to turn such a diagram into a solution, read the introduction to block removals at [W2].
If the game begins with the center peg missing, this board position is in the position class of the empty board, so it is not possible to finish with one peg. An interesting modification of the rules which allows for a d4 to d4 solution is known as Cremers' Key [W16]. According to [W16], this concept was invented around 1998 by Frans Cremers, a retired teacher from Aalter, Belgium. Play proceeds from the center as normal, but the player is allowed to replace the central peg once when the hole is unoccupied. This puts the board position in the correct position class, and a solution can be obtained. The shortest solution to the central game using Cremers' Key has 20 moves.
Note that Cremers' key works not only from the center start, but from ANY start! In the general case one is allowed to replace the peg at the starting hole once. The goal is to finish with one peg, not at the starting location, but always in the center. The reason why this works is clear if you understand position classes. On the French board, the board with every hole filled by a peg is in the same position class as the board with one peg in the center. Therefore, when you replace a peg at the starting hole, what you are doing is changing the position class to that of the full board, so that finishing in the center is now possible. The results of [P3] show that Cremers' Key will put the board in the position class of the center finish on any gapless, odd, squaresymmetric board that is not nullclass.
Another way to make the central game solvable is to allow diagonal jumps. In this case the central game can be solved in as little as 13 moves. One interesting puzzle with diagonal jumps is to begin with pegs at all locations except for the central 9 holes {c3, c4, c5, d3, d4, d5, e3, e4, e5}, and try to play to the complement of this position with only the center 9 holes occupied. Allowing diagonal jumps, this "big central game" is solvable, but the same problem is not solvable on the 33hole English board. The shortest possible solution to the "big central game" has 13 moves. One reason the "big central game" is interesting is that using it one can solve any single vacancy to single survivor problem [P4].
A web page on the shortest solution when diagonal jumps are allowed
This board is a member of a general class known as a draughtsboard. Such boards are obtained by taking any square board, and labeling the holes alternately as on a chess or checkers board. Then the board is rotated 45 degrees and the black squares define the holes of the draughtsboard. The 41hole diamond board can be so obtained starting from a 9x9 square board.
You can try to find a center to center solution using the Cremers' Key [W16] rule modification, but you will not succeed. Replacing the center peg does give one a board position in the correct position class, but using the resource count shown below one can prove that it is not possible to finish with one peg.
Several interesting variations to the 41Hole Diamond Board have been proposed. Around 1882, H.A.H. Hermary proposed removing the leftmost and rightmost holes from the board, giving Hermary's 39Hole board, shown on the right. This board is nullclass, rectangularsymmetric, and most complement problems are solvable [B1]. The central game on Hermary's 39hole board can be solved in a minimum of 23 moves.
In 1894, A. Huber removed 4 holes to produce Huber's 37Hole board, shown on the left.
This board is nullclass and
squaresymmetric—the central vacancy and other
complement problems are solvable.
The central game on Huber's 37hole board can be solved in
a minimum of 20 moves.
This board has a similar size as the
standard English board, but it has 14
corners rather than 8.
In 1941, B. M. Stewart showed that all 25
single vacancy to single survivor problems
were solvable on this board.
My program has found that all of them are solvable in 1719 moves,
with only the d1 (top hole) complement requiring
19 moves.
The d4complement can be solved in
a minimum of 18 moves.
A web page with strategy tips for this board.
The proof of the impossibility of the (4,0) or e1 complement is not a simple matter, a brief outline of a proof is given in Beasley's book [B1]. I have found an alternate proof by integer programming techniques, but no short, simple proof has been found. A computer proof by exhaustive search is possible, but time consuming. It feels like you are smashing a peanut with a sledgehammer. This problem is several orders of magnitude harder than any problem on the English Board.
Problems on this board can be solved most easily using block removals as shown on the figures to the right. The numbering shows the ordering of the block removals. Numbers subdivided a, b, c are block removals that must be interleaved, in other words part b begins before part a is finished. To see the sequence of moves, see the solution in [W3]. Beasley [B1] gives block removal diagrams for one other complement problem on this board.
The longest sweep that can appear in any solution to a single vacancy to single survivor problem has length 16, one such sweep is shown on the board above left. There are three problems on this board for which a 16sweep can occur, these make for interesting problems to solve by hand:
The solution catalog shows the shortest length solution to all 35 solvable problems on this board, an effort in 2004 which required 3 months of CPU time on a 1 GHz Pentium PC. The results can be found in our paper [P2], and in 2012 were confirmed by Barker and Korf [P7]. All the problems are solvable in a minimum of 2023 moves, with only the (3,0) or e2 complement requiring 23 moves. The central game can be solved in 22 moves, but no fewer. There are a few problems on this board with unique minimal length solutions, up to symmetry and move order. For example, there is a unique 20 move solution from c4 to i4.
A web page of computational results for this board
Using the same technique [W1] as for the 6x6 board, it is easy to prove that the solution to any single vacancy to single survivor problem must have at least 24 moves. In 1986, John Harris found a 25move solution by hand [W1]; finding a shorter solution is a difficult computational task, but in 2014 I found a 24move solution (and here is another).
The longest finishing sweep on this board has length 21.
It is not difficult to find a solution finishing with a
21sweep—this is a fun exercise to work out by hand.
As usual, you must begin from the complement of the sweep position
(one possibility is shown on the right).
On this board, what is the shortest solution to the central game? We do not know. In 2004, Alain Maye found a solution by hand in 34 moves. It is likely that the shortest solution has around 30 moves, by analogy with the 10x8 board, which is of similar size.
Rectangular boards where both n and m are even have some interesting properties. By analogy with the proof [W1] on the 6x6 board, it is easy to prove that the solution to any single vacancy to single survivor problem must have at least (n/2+1)(m/2+1)1 = nm/4+(n+m)/2 moves. Therefore, if one can find a solution of this length, it is the shortest possible. On the 6x4 board it is not difficult to find 11move solutions, and we have already mentioned that the 6x6 board has 15move solutions. On the 8x6 board, 19move solutions can be found, and on the 8x8 square board, I have found 24move solutions. All of these are automatically the shortest possible, by the above argument.
In 2014, on the 10x8 board, I found a 29move solution!! This is the largest board (80 holes) for which a solution having minimal length is known. Finding these shortest solutions on such large boards requires advanced search techniques, I use A* search based on the number of filled Merson regions.
I investigated these boards in 2003 and found there are exactly 12 generalized cross boards where the complement problem is solvable at every board location. Of these 12, the only board with square symmetry is the standard 33hole board. Two are rectangularsymmetric (top row of figure to the left), three have rectangular symmetry about only one axis, two have diagonal symmetry (second row) and the remaining four have no symmetries at all.
Of particular interest is the 39hole board in the upper right with alternating arm lengths 3,2,3,2. This board is rectangularsymmetric. A very hard problem is to solve the complement problem from the midpoint of the top row. It can be shown that the solution to this complement problem is unique up to symmetry and move order [P2]. This is an unusual property for a peg solitaire solution and makes the solution very difficult to find, either by hand or using a computer. Try this problem yourself using this online puzzle.
A web page on Generalized Cross Boards
(not available online).
There is now a separate web page for Triangular
Solitaire.
Here is a list of the 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.
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 are squaresymmetric (except for Diamond32) 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 
NullClass?  Number of Problems  Longest Sweep (any problem)  Minimal Length Solution Properties  

Solution Lengths  Longest Sweep  Time to Calculate  
Diamond32  32  Yes  35  8 or 9  1719  8  2 hours 
English  33  Yes  21  9 †  1519  8  2 hours 
6x6  36  Yes  21  10 ‡  1516  10  6 hours 
French  37  No  10  9 †  2021  9  24 hours 
Diamond41  41  No  4  9  26  9  3 hours 
Wiegleb's  45  Yes  35  16 ‡  2023  14  3 months 
Table Footnotes: (†) From John Beasley's book [B1]. (‡) 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. 
The information in the above table has been calculated by other authors in the case of the English, French and 6x6 boards. My results have been checked against their results. In 2012, Barker and Korf [P7] confirmed my results for the 41hole diamond and 45hole Wiegleb's board.
A good introductory reference which has a nice progression of problems is the 2007 book by Koetke [B4]. This book starts out with small boards that are easy to solve, and discusses the problems encountered as larger boards are considered. It also has example programs in java. This is one of the few peg solitaire references that contains a lot of detail about solving the game computationally.
If you try to solve a peg solitaire problem in an inefficient manner your program can take forever to run, even on the standard 33hole board. For example the most obvious technique is to store the sequence of moves (or jumps) and try to exhaustively go through all possible sequences. Because there are a large number of move sequences that result in the same board position, such an algorithm is extremely inefficient. One solution is to use a hash table or some other means to store board positions seen previously so you do not have to investigate them farther.
A similar technique is to only keep track of the set of boards at each level in the tree, rather than the moves. I call this a search by levels. This is much faster than a straight search over move sequences and can solve any problem on the 33hole board relatively quickly. For boards larger than this, additional techniques are needed.
I have used four ideas to speed up a search by levels:
Finally, one should be careful not to confuse the computer's failure to find a solution with a proof that no solution exists. These calculations are complex and lengthy, particularly when resource counts, symmetry and forward/backward calculations are all being used. Logical bugs in the code can easily prevent the computer from finding a solution, and much testing is required to make sure the results are reasonable. For example, no program that reports "no 17 move solution to the English board central game" should be trusted unless it can find the Bergholt solution in 18 moves. You can also test your program by reproducing these tables.
For more detail on computational search techniques see [P4] and [P7].
The most useful resource counts generally have negative values in corners (in fact, it is not hard to show that a resource count can only have a negative value at a corner). If a certain move leaves the board with a value that is less than that of our final position, we know that this move cannot possibly lead to a solution. A very useful resource count on the 41hole diamond board is:
1  
1  1  1  
1  1  0  1  1  
1  1  0  1  0  1  1  
1  1  0  1  0  1  0  1  1  
1  1  0  1  0  1  1  
1  1  0  1  1  
1  1  1  
1  
The above resource constraint can be applied on the French board (by ignoring any value that is not on that board) and it is still somewhat useful. It can also be used on the English board, but with only a very minor speed increase.
On Wiegleb's board a moderately useful resource count (for computations) has a "1" at the eight corners and "+1" at the 12 interior locations: d2, f2, b4, d4, f4, h4, b6, d6, f6, h6, d8 and f8 (and zeros everywhere else).
© 1996 John Robinson 
It was shown in 1990 [P1] that problem #1 is NPComplete. In practical terms this means that any algorithm to solve this problem will have a run time that increases exponentially with the problem size.
Like problem #1, problem #2 also asks if you can reduce a pattern of pegs to a single peg. Does this mean problem #2 is NPComplete also? No, it does not, because a complement problem does not start from an arbitrary pattern of pegs. The starting position has every hole occupied, except for the starting vacancy, hence it is a very regular pattern. Of course the shape of the board could still be somewhat complicated, but as a gapless board it is only the edge that may be complicated. It is still unknown how hard problem #2 is to solve.
Clearly if the board is not nullclass, there is no solution to problem #2 or #3 (we can also check in problem #1 if the configuration of pegs is in the position class of one peg or not). It is very easy to check if a board is nullclass, so we don't need to require this. As the difficult case we may as well assume all boards from now on are nullclass.
Suppose we consider problem #2 on an arbitrary rectangular nullclass board (with both edges at least 4). Finding a solution to a complement problem on such a board, I claim, is actually very easy, and can probably be solved in linear time. Why? Because this problem is easy to solve by hand using block removals. You simply visually identify blocks of pegs you need to remove and make sure the required catalyst is present and that after the block removal you don't strand any pegs too far away from the core bunch. You also need to be careful near the edge of the board. This logic could be programmed, and would result in a computer algorithm that could solve complement problems on rectangular boards extremely quickly.
Even boards which are "not too different" from a rectangular board should also be easy. It is rather difficult to quantify "not too different", but basically any gapless nullclass board that doesn't have any tight spaces can be solved using block removals. The standard 33hole board should fit into this category. It easier to complete this argument on triangular boards, and I now have a simple algorithm that can solve any single vacancy problem on a triangular board of arbitrary size.
In summary, problem #1 has been proven NPComplete. I believe problem #2 is not very hard on "well behaved" boards, which include at least rectangular boards (and certainly triangular boards). Problem #3 is very difficult on any board with more than about 50 holes, and I believe no algorithm can find shortest solutions in polynomial time. In 2012, Joseph Barker and Richard Korf wrote a paper on the subject of searching for short solutions [P7].
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, The Unexpected Hanging and Other Mathematical Diversions, University Of Chicago Press, 1991 (paperback), pp. 122135 ISBN 0226282562. [The chapter "Peg Solitaire" is based on a Scientific American column that appeared in the June, 1962 edition.]  
B3.  John H. Conway, Elwyn R. Berlekamp, Richard K. Guy, Winning Ways for Your Mathematical Plays, Volume 4, AK Peters, 2004 (second edition).  
B4.  Walter Koetke, Classic Thinking Games with Java, Basics & Beyond, Inc., 2007.  
B5.  George I. Bell, Peg Solitaire with Diagonal Jumps, in Ed Pegg Jr., Alan H. Schoen, Tom Rodgers (Editors) Mathematical Wizardry for a Gardner, AK Peters, 2009.  
B6.  George I. Bell, A Compendium of Peg Solitaire related papers, 2009 (175 pages, 90 pages double sided). This is a compilation of 11 papers relating to peg solitaire (20032009). You can download all the papers separately, but this makes a nice, colorcoded, bound volume. To see the list of papers, download the Table of Contents. 
P1.  Ryuhei Uehara and Shigeki Iwata, Generalized HiQ is NPcomplete, Trans. IEICE, E73, pp.270273, 1990  
P2.  George I. Bell and John D. Beasley, New Problems on Old Solitaire Boards, Board Game Studies #8, presented for the 8th international colloquium on board game studies, Oxford, England in April 2005 (finally published in Board Game Studies Online in 2014).  
P3.  George I. Bell, A Fresh Look at Peg Solitaire, Mathematics Magazine, 80:1628, 2007.  
P4.  George I. Bell, Diagonal Peg Solitaire, INTEGERS Electronic Journal of Combinatorial Number Theory, Vol 7, G1, 2007.  
P5.  G. DuPuy, D. Taylor, Using Board Puzzles to Teach Operations Research, INFORMS Transactions on Education, Volume 7, Number 2, January 2007.  
P6.  George I. Bell, Notes on solving and playing peg solitaire on a computer, 2009.  
P7.  Joseph K. Barker and Richard E. Korf, Solving Peg Solitaire using Bidirectional BFIDA*, in the Proceedings of the TwentySixth AAAI Conference on Artificial Intelligence, Toronto, 2012.  
P8.  John Beasley, On 33hole solitaire positions with rotational symmetry, unpublished manuscript, 2012. 
W1.  Solitaire (pdf version), Issue #28 (web version) of The Games and Puzzles Journal, September 2003.  
W2.  Cut The Knot contains a good description of how to solve peg solitaire problems using block removals (called packages and purges, Conway's terminology).  
W3.  Jurgen Koller's Peg Solitaire web site even has ideas on how to construct your own board.  
W4.  MathWorld has a summary page with many printed references.  
W5.  JC Meyrignac's web site contains results from computer runs on the French Board, as well as a peg solitaire competition and other items.  
W6.  Torsten Sillke has independently come up with Generalized Cross Boards.  
W7.  Sidney Cadot published an article (in Dutch) in the January 1998 issue of Machazine. In this article he describes how he was able to calculate all 18move solutions to the central game on the 33hole board. He determined that there are exactly 936 18move solutions.  
W8.  Emmanuel Harang has a very extensive web page on the theory of the game. Unfortunately (for me) it is in French.  
W9.  Durango Bill has a page on peg solitaire where he also calculates the number 23,475,688. This is the total number of board positions reachable from the central vacancy on the standard 33hole board (not including positions equivalent by symmetry). He also calculates the total number of solutions to the central game.  
W10.  Gary Darby has created a Delphi (an object oriented Pascal) program to solve peg solitaire problems, as well as an extensive site on other mathematical games.  
W11.  The University of Waterloo has a games museum that contains some interesting history on peg solitaire.  
W12.  Michel Schellekens is an Associate Professor at the National University of Ireland with an interest in peg solitaire.  
W13.  James Dalgety has one of the largest puzzle collections of puzzles in the word. He runs puzzlemuseum.com, here is a page with history and photos of his gorgeous solitaire board collection.  
W14.  Erich Friedman has a nice collection of peg solitaire puzzles.  
W15.  John Robinson (19352007) is an artist who has made a sculpture of the tree of knowledge in the form of a peg solitaire board, with pegs representing forbidden fruit.  
W16.  This site has some interesting ideas about the French board.  
W17.  Rob Stegmann has a vast puzzle web site with a nice page on Peg Solitaire and Jumping Puzzles.  
W18.  The John and Sue Beasley website has some interesting recent observations of the game. This includes a transcription from the French magazine Mercure Galant from 1697, where the game is described in detail. This French article is the earlest known printed reference to peg solitaire.  
W19.  Top Accolades has a web page which descibes the shortest solution to the central game in a way that is easy to remember.  
W20.  Jaap Scherphuis has a peg solitaire web page, with a nice discussion on block removals and how to determine which problems are solvable on various boards. Jaap also has a nice Peg Solitaire Java Applet. 
Copyright © 2006–2014 by George I. Bell