Peg Solitaire (sometimes referred to as just Solitaire, although the latter term can also refer to the card game also known as Patience) is a single-player board game. Its straightforward rules have made it a widely-played game, with millions of sets in existence, a set being a not-uncommon present. However, solving the game is more complicated than it looks. While many different boards exist, the most common is played on a 33-hole board. Moves are made by jumping one peg over another horizontally or vertically, and removing the jumped peg. The objective of the game is to remove all the pegs but one, and have the remaining peg end up in the centre square of the board. The game, and the solvability of various positions, are also of mathematical interest.
The origins of Solitaire are unclear. Many legends as to the game's origins exist, but all lack evidential support. The earliest known reference to the game is the 1697 engraving Madame la Princesse de Soubize joüant au jeu de Solitaire by Claude-Auguste Berey, and the earliest textual reference was written by Gottfried Leibniz in 1710. Because of the simplicity of the game, it is not inconceivable that some version of this game could have been played well before these dates, however.
The board shown in the engraving mentioned above is the 37-hole board. The 33-hole board was first mentioned in Unterricht in der natürlichen Magie by J. C. Wiegleb, published in 1779. The 33-hole board has come to be the standard-sized board in most countries, although the 37-hole board is the most common board in France and can be found elsewhere.
Before discussing a solution, it is convenient to introduce a suitable notation. Several different systems of notation are in use; the one used by Beasley in The Ins & Outs of Peg Solitaire labels the seven columns a through g and the seven rows 1 through 7, so each hole is denoted by its row and column reference. For example, the central square can be denoted as d4. The same notation can be used for the 37-hole board; the only difference is that b2, f2, b6, and f6 represent squares on the 37-hole board but not the 33-hole board.
For the 37-hole game, there is no solution for the centre-complement game (i.e. leaving the centre hole empty, and playing to leave a single peg in the centre hole). This can be demonstrated through the following argument. Divide the 37-hole board into three sets of diagonals A, B, and C, running from top-left to bottom-right, and three sets of diagonals D, E, and F, running in the opposite direction, as shown below:
ABC DEF BCABC DEFDE CABCABC DEFDEFD BCABCAB EFDEFDE ABCABCA FDEFDEF ABCAB EFDEF ABC DEF
Counting up the number of pegs in each of the six diagonals, they are all even, and the total number of pegs on the board is even. If any move is made, the number of pegs in each of the six diagonals will be odd, and the total number of pegs on the board will be odd. It can be seen that, due to the way that moves are made, each of the six diagonals will always have the same parity (even or odd) as the number of pegs currently on the board. The target position, however, will have a different parity on diagonals A, C, D, and F. Therefore, the centre-complement problem cannot be solved on the 37-hole board; similar arguments can show that a position with only the centre hole vacant cannot be reduced to a single peg anywhere on the board, nor can a position with any hole vacant be reduced to a single peg on the square left vacant. Among games for which there is a solution, the most common are to start with a vacancy on a3 and end with a peg on g7, and to start with a vacancy on d3 and end with a peg on d5.
Performing the above analysis on the 33-hole board would show that a solution is theoretically possible. In fact, there are solutions to the game on the 33-hole board. They are very difficult to arrive at, however, for those ignorant of the strategy of the game. Casual players might play time and time again without ever stumbling upon a solution. A player who is particularly attentive might notice that the games often end with pegs in far-off corners that cannot be captured, or without a peg that can jump into the centre hole to complete the game. From there, a player might be able to develop a strategies involving the removal of blocks of pegs.
The 37-hole board has already been discussed. Another board that is not uncommon, although little has been written about it, is the 15-hole triangular board. On this board, moves may be made parallel to any of the three sides of the board. Boards of other sizes, as well as boards of more than two dimensions and infinite-sized boards are also of mathematical interest.
One common variation (on the 33-hole and 37-hole boards) is to allow diagonal moves, similar to those of checkers, as well as orthogonal moves. This variation creates a game that many judge to be too simple. One feature, however, is that it makes a solution to the 37-hole centre-complement game possible.
Various puzzles also exist. Instead of playing from a nearly-full board to a nearly-empty board, these puzzles may ask the player to create a certain (often picturesque) layout of pegs, or to reduce a (often picturesque) layout to a single peg.