Peg Solitaire (also known as Hi-Q) is a game that is played on a board with some pegs and holes. A move is to jump a peg over another peg into an empty space, with the peg that has been jumped over removed. Jumps are to take place vertically or horizontally, and sometimes diagonally. The following figure shows the English Board, on which diagonal moves are not allowed.
 
 
The goal is to have only one peg left on the board after making a series of moves. If we count any number of consecutive jumps made with a single peg as just one move, the minimum number of moves to solve the puzzle is 18, and it has been mathematically proved by John Beasley in 1964. Other variations of the game is also possible: we can declare a certain peg as the finalist, i.e. the last peg on board; or we can declare certain hole is where the last peg to reside; we can also combine the two to have a peg started at certain position to be the last peg and finished at another position; various boards have also been developed, such as triangular board and circular board.
 
Here we shamelessly copy some paragraphs from Winning Ways for Your Mathematical Plays to show how Central Solitaire, where the last peg is to be at the center of an English board, can be easily solved.
 
PACKAGES AND PURGES
 
It's nice to be able to know the effect of a whole collection of moves before you make them, so let us sell you some of our instant packages. When a package is used to clear all the pegs from a region, we call it a purge.
 

Purging Three Pegs
 
The figure above shows the handy little 3-purge, our most popular package. When three pegs - the tail, the body, and the head - are adjacent in line, this will remove them all, provided the head has an additional peg on one side of it, and an empty space on the other, as in the figure. Move 1 of the package jumps the additional peg over the head; move 2 jumps tail over body into head; and move 3 jumps over the head, back to its original position. Since the peg and the space on either side of the head are essential to the package, but are restored to their original state, we call them the catalyst.
 
In the figure below, dark dots indicate pegs to be purged, hollow ones indicate spaces to be filled, and crosses XX indicate catalyst places of which one must be full and the other empty. In most of the purges there are two catalyst moves in opposite directions over the same position (which may be a peg or an empty space) and the remaining moves form one or two packages, which deliver pegs to that place. For the 3-purge (a), one peg was already in place and the second is delivered by a single jump which we might call the "2-package" (b). The 6-purge (c) is usually accomplished using a 2-package to deliver the first peg and a 4-package (d) for the second.
 

A Parcel of Packages
 
The L-purge (e) and L-package (f) are very useful indeed. The first peg for the L-purge is already in place and an L-package supplies the second. The first two moves of the L-package form a 2-purge (g) which can also be used in other situations. The catalyst for the 2-purge is restored in a rather unorthodox way, as is alternative catalyst for the 6-purge (h).
 
PACKAGES PROVIDE PERFECT PANACEA
 
Plenty of problems are performed with panache by people who purchase our packages.
 
Below we can see at a glance a solution to the Central Solitaire, consisting of two 3-purges (1 and 2) followed by three 6-purges (3,4 and 5) and an L-purge, leaving only for the final jump to be made. You should check that every purge has a catalyst it needs.

Central Solitaire Painlessly Packaged
 
Theories for the peg solitaire on the English board and other related information can be found in Winning Ways for Your Mathematical Plays, while Ins and Outs of Peg Solitaire is devoted to peg solitaire. At the same time, you can try to play the game here.
 
R. Uehara and S. Iwata, and D. Avis and A. Deza separately proved that finding a linear time algorithm to determine the solvability of a given n x n board is NP-Complete. However B. Ravikumar showed that the answer to the similar question of the existence of such an algorithm for a given k x n board, with any fixed k, is positive. C. Moore and D. Eppstein gave an explicit formula for the 1 x n board, although the result has been known for some time.
 
A Maple package was written to try to find the formulae for the k x n board with any fixed k. To better understand the program, we here quote from the famous philosopher Leibniz:
The game called Solitaire pleases me much. I take it in reverse order. That is to say that instead of making a configuration according to the rules of the game, which is to jump to an empty place and remove the piece over which one has jumped, I thought it was better to reconstruct what had been demolished, by filling an empty hole over which one has leaped.
Of course we know that jumping a piece into a hole and filling the empty hole that was jumped over is the same game as jumping a hole over another hole into a piece and removing (i.e. inserting a piece into) the hole that was jumped over. However, he did give us another approach to the game that many people have followed, especially in the case we are to discuss.
 
The package is capable of reconstructing all solvable Solitaire formations, and try to find possible patterns from them, the same as what we human do inductively over and over again. Just like we create "human errors" by try-and-error, computers cannot avoid the same fate when they are being taught. Computers can be "coachable" if we tell them how to think and how to self correct. The package is able to find probable patterns, validate them, and correct them if error occurs. Detailed proof is presented within the package. In less than a minute, the computer found the following regular expression for all the solvable positions on the 1 x n board:
 
[1] + [[1, 1, [0, 1]], [1, [1, 0], 0, 1, [1, 1], [0, 1], 1] + [1, 1, [0, 1], 1, 1, 0, [1, 1], [0, 1], 1] + [1, 1, [0, 1], 1, [1, 1], 0, 1, 1, 1, [0, 1], 1] + [1, 1, [0, 1], 1, 1, 1, 1, [1, 1], 0, [0, 1], 1]]
 
Where each pattern is surrounded by [ and ], and each extra pair of [ and ] inside a pattern means 0 or more repetitions of the string inside. It is obvious that we forgot to teach computer the beauty of symmetry that has pleased human eyes for so long. In fact, the "beauty" of mathematics was traded for the simplicity of calculation.
 
The program tries to expand the set of known solvable formations before making educated guesses. The output of each stage is the input for the next stage. For the one-dimensional Solitaire, formations of up to 15 pegs total were calculated, and the size of the output of each stage is less than twice of that of the previous one. Therefore the size of the input for the final stage requires only about 215 * Constant computations. 2 x n is trivial because there is no vertical move, thus it is only two separate one-dimensional games. 3 x n is much harder: the size of the output of each stage is four times the previous one, and a conservative estimate of up to total 24 pegs needed to complete the computation, which will require 424 * Constant computations, a number big enough for a Giga Hz computer to calculate for years!
 
The program is available here, and the complete result for the one-dimensional Peg Solitaire is here.
 
Parts of the content and graphics are taken from Winning Ways, and one of my favorite sites cut-the-knot.org, in which you can play a lot of combinatorial games, including Peg Solitaire.
 
 
 
References