In his 1985 book The Ins & Outs of Peg Solitaire, John D. Beasley states that the origins of Solitaire are unknown, and that the earliest clear evidence of the game he found is this portrait of Anne Chabot de Rohan Princesse de Soubise, who lived 16481709, engraved by ClaudeAuguste Berey in 1697. (The French Wikipedia article on Berey says he lived circa 16801730, so perhaps he did this engraving at the age of 17!) Another very similar engraving by Antoine Trouvain entitled Dame de Qualité Joüant au Solitaire (A Woman of Quality, Playing Solitaire), from Figures du règne de Louis XIV, vol 1, fol 105, dates from 1695. Beasley says he regards "the existence of Solitaire at the court of King Louis the XIV as adequately proven."
Beasley includes a quote from Gottfried Wilhelm Leibniz that appears in the 1710 Miscellanea Berolinensia I: "Not so very long ago there became widespread an excellent kind of game, called Solitaire, where I play on my own, but as if with a friend as witness and referee to see that I play correctly." (The Miscellanea Berolinensia (Berlin Miscellanea) was the primary journal of the Berlin Academy, and was published in seven volumes between 1710 and 1746.)
George Bell has done a lot of analysis of Peg Solitaire in its various forms. George's website offers all kinds of information and is definitely worth a visit! Also, at Alexander Bogomolny's CuttheKnot, there is a good explanation of the solution technique involving packages and purges, taken from Winning Ways for Your Mathematical Plays by Berlekamp, Conway, and Guy. Other statistics can be found at JeanCharles Meyrignac's website euler.free.fr.
In their 2005 paper New Problems on Old Solitaire Boards (PDF), George Bell and John Beasley state that "The game appears ... to have been the 'Rubik's Cube' of the court of Louis XIV."
The game is played on a board having an arrangement of holes, with counters of some sort  typically pegs or marbles. The objective is to start with pegs in specific holes, and one or more vacant holes, then by legal jumping movements, remove pegs to achieve a goal configuration. A game where one must start with a full board save one empty hole, and end with one peg, is called a "single vacancy to single survivor" problem. When the initial empty hole and the location of the final peg must be the same, it is called the "complement problem."
Typically, a legal move is to jump a peg over an adjacent peg, in a straight line, either horizontally or vertically in any direction but not diagonally. Depending on the variant being played, sometimes diagonal jumps are permitted, or jumps in certain directions are prohibited. In addition, the game can be played in reverse (as noted by Leibniz)  start with a single peg and then by "reverse jumps" repopulate the board, with the objective of filling a specific field of holes.
The shape of the board and the arrangement of holes varies as well. Solitaire is usually played on a 33hole crossshaped board known as the "English" board (though according to Beasley this board type probably appeared in Germany before appearing in England). A standard notation labeling the holes on the English board assigned the letters abcdefg to the columns and the digits 17 to the rows. The center hole is thus d4. The standard problem on the English board is to start with all holes filled save the central hole, and end with a lone peg there  this is called the Central Game, or the d4 complement problem. Modern readers may be more familiar with the side5 triangular variant offering diversion at tables in Cracker Barrel and other restaurants.
The portrait shows the Princess with the 37hole French board, but on this board it is impossible to start with the central hole vacant and end with the last peg there. Bell and Beasley explain, "The unsolvability of the problem 'start by vacating the central hole, play to leave a single man in this hole' on the 37hole board is a consequence of a property known as 'position class': the various positions possible on a Solitaire board can be divided into 16 different classes, and it is impossible to play from a position in one class to a position in another." It is usually assumed that diagonal moves are prohibited, but it really isn't known definitvely whether or not diagonal moves were allowed when this was devised, and if they are, then the central game on the 37hole French board is solvable in 13 moves.
1. European (or Continental) board,
17th century, 37 holes 2. J. C. Wiegleb, Germany 1779, 45 holes 3. Asymmetrical 3322, 20th century 
4. The English Board, 33 holes
5. Diamond, 41 holes 6. Triangular (side5), 15 holes 
Click here to open a window and run my Triangle Solitaire Solver. 
A puzzler improves at Solitaire by at first achieving the objective of leaving but a single peg in the correct hole (rather than two or more pegs isolated across the board, or even one peg but in the wrong hole), and then by reducing the number of moves required for the task to its minimum. The number of jumps will always be equal to or less than the number of initial pegs minus one, since every jump eliminates one peg  but the number of moves can be less if we count the same peg jumping more than one other peg in succession to be a single move. For a given configuration, an interesting mathematical and computational challenge is to determine this minimum, and the correct sequence of moves  indeed, to determine if a solution exists at all for a given starting configuration and objective. The shortest solution to the central game on the English board requires 18 moves, shown by Ernest Bergholt in 1912 and proved in 1964.
Many versions of Peg Solitaire have been produced. One particularly wellknown version called HiQ was offered by Kohner in the 1950s and 60s. According to this article by Richard Gottlieb, the Kohner brothers Frank, Paul, and Michael played a major role in shaping the modern toy industry. Frank Kohner died on Feb. 6 2011 at the age of 100.
In the 1960's, Setko (aka the Set Screw and Mfg. Co. of Bartlett IL) offered a number of nice peg solitairetype jumping and transposition puzzles. Some were "made for" Baekgaard & Butler  Glenview Ill. Several of them were designed by a Calvin O. Brown. Hoyle, Crestline, and even SkorMor offered similar sets. 
Various box lid graphics, including a screw, crest, and alt. crest. 

101 Cross The classic  set up pegs in all holes except center. Jump in straight line horizontally or vertically, not diagonally, & remove jumped peg. End in center hole. 
102 TriPuzzler Walnut board, Oak board Another classic, but on a side6 grid rather than the side5 at Cracker Barrel. Start with one hole anywhere, jump & remove, end in a corner. 

103 Reversal (Reverse All) 9 pegs of one color, 9 of another. Set up as shown. Jump forward (diagonally) or sideways, no removal. Reverse the setup vis colors. 
104 3 Square eq. to Crestline's Cross Over and SkorMor's Switch Put 9 pegs of one color in lower right square & 9 pegs of the other color in upper left square. Jump up/down/left/right (not diagonally) over any color, without removal. Exchange the complete colored squares of 9. 
105 Double Diamond The included instructions are unclear on the setup, and suggest the setup shown here, but the patent and the Hoyle version clarify  the setup should resemble the Hoyle picture I show. The 3 special pegs go in the circled holes. Jump, no removal, to move all pegs to the opposite diamond, with the special pegs in the corresponding circled holes. The instructions aren't clear on whether diagonal jumps are allowed. U.S. Patent 2778640  Calvin O. Brown 1957 
Hoyle Double Diamond 
106 Bullseye Start with center, circled hole empty. Jump in any straight line, remove jumped peg, leave last peg in center. 

Setko Bullseye II Start with center, circled hole empty. Jump & remove, any direction (including diagonally), end in circled hole. 
107 Kan Yu Set up a side6 triangle, with a special peg in the center of the row of 3 (a circled hole). Jump forward only  not backwards or sideways, no removal. Transfer all pegs to the opposite triangle, with the special peg in the corresponding circled hole. U.S. Patent 2712938  Calvin O. Brown 1955 
108 Zig Zag 8 pegs of one color, 7 of another. To begin, lay all the pegs in the groove, in some order you pick. Starting on the right end, move the first peg in line to the left end of the groove then place the next peg on the right into the first hole on the left of the top row of holes. Repeat, moving the first in line to the end and placing the next into the next available hole from left to right, top then second row of holes. The goal is to end with an alternating arrangement of colored pegs in the holes. You're trying to discover the starting lineup in the groove that will permit the goal to be reached when following the prescribed process. U.S. Patent 2778639  Calvin O. Brown 1957 (The instructions actually give the wrong patent number  2778640, which is for Double Diamond! The above is correct.) 
Setko Fore and Aft Hoyle Fore and Aft 8 pegs of one color and 8 of another  set up as shown. When oriented as shown in the Setko photo, the dark pegs can move right or down only, the light pegs move left or up only. Jump over a peg of the opposite color, no removal. Reverse the starting setup vis colors. See U.S. Patent 522250  Emerson 1894. 
Hoyle Why No instructions with my copy. Eq. to Setko Puzzler 67 

Setko 1971 Puzzler Fill all holes with pegs, remove one to start. Jump in any direction, removing jumped pegs. End in circled hole (left empty in photo). 
Setko Red Puzzler No instructions included, but should be same as 1971. 
Setko X (?  no name on package or board) No instructions included, but should be same as 1971. 
Crestline Square Peg (eq. to SkorMor's Lonely Peg) Start as shown, jump & remove, end in center. Instructions aren't clear on whether diagonal jumps are allowed  I assume not. 
Setko Mill Mill is a twoplayer game. The board starts empty. 
Setko also packaged puzzles in sets  3Square, Mill, and Cross were included in a set; Tri, Reversal, Double Diamond, and Bullseye were offered in another set. 
U.S. Patent 2778641  Calvin O. Brown 1957 
Springbok's 1973 puzzle called "Cubits" is an interesting take on solitaire  there are 32 identical small cubes which are mixed and randomly placed on a 6x6 grid on the red base, leaving the four corner positions empty. Five sides of a cube have a pattern of arrows and the sixth the word Cubits. A cube can jump an adjacent cube that lies in the direction of an arrow on its topmost face. If the word Cubits is topmost, then the cube can jump in any direction. (Diagonal jumps are not allowed.) When a cube lands in a corner space, it is turned so Cubits is topmost. The objective is to jump until only one cube with Cubits topmost remains. This puzzle was invented by Robert J. White. 
This is Springbok's Sweep (1973). The pieces include simply the blue base which has a 6x6 grid of shallow peg holes numbered from 1 to 36, and a set of clear acrylic pegs. This is basically Peg Solitaire  the instructions give 21 game plans indicating which peg to remove first, and the hole on which the last peg must land. 
Springbok Moebies (See my Packing section.) 
Springbok Right Connections (See my RouteBuilding section.) 
Springbok Fitting and Proper (See my Packing section.) 
Springbok Pentominoes (sealed) (See my Assembly/Polyominoes section.) 
This is the "Ancient Star Problem Puzzle." It is copyright 1949 Barters, Inc. and was issued by the Reflex Products Company of Cleveland. 36 numbered holes are arranged in a star pattern on the metal board, with radial lines, chords, and concentric circles printed to show allowable jumping paths. Various initial peg setups are given in the accompanying instructions sheet, and the challenge is to jump pegs until a single peg is left in the center hole. An insert challenged puzzlers of 1950 to send in unique problems for cash awards. See U.S. Patent 2569637  Loe 1951 (assigned to Barters).

Here is another peg solitaire type puzzle with holes arranged in a star shape. (I don't have this  shown for reference.) This one was issued to advertise "Chas. H. Rickert's Cash Shoe Store" of Reading PA. See U.S. Patent 484882 awarded in Oct. 1892 to Charles Rickert. Centercomplement goal. Evidently Rickert designed and patented his own puzzle to use as advertising for his shoe business. 
This boxed set of four solitairetype puzzles and logic games was issued by SkorMor. Included are: the Twenty To One Ball Puzzle (jump balls until only one remains in center), the 12 High Game (2 players move according to dice rolls), Six Man Morris, and the NimWit Game.

Rather than jumping and removal, peg puzzles can have placement as their objective. On the left is the Eight Point Puzzle from Sherms. Use eight coins  place one on any of the eight points, then move the coin along one of the two lines from that point, to the opposite point and leave it there. Continue with another coin, placing it on one of the remaining vacant points and moving it as described, until seven of the eight points have been covered. You win if you can place seven coins as described, and can simply place the eighth coin on the last point. Galileo's Wheel was issued by Milton Bradley in 1962. It is similar in principle to the 8Point puzzle, but with 10 points rather than 8. The blue base has 10 symmetrically spaced holes around its perimeter. There are 10 orange cones and a transparent hub piece that, when set on an existing cone position, indicates the two possible positions for the next cone  in lieu of the lines printed on the 8Point card. The hub also serves as a storage cradle for the cones as shown. In "Star Craze," you choose a hole in which to place the first peg. Each subsequent placement may be made only in a hole connected to the previously placed peg by lines on the board. The objective is to fill all the holes.

Pentalpha Played on a pentagonal star shaped board, using the ten points and line intersections  highlighted by circles in the diagram. Play with 9 coins or other markers. A move consists of starting on an empty circle, moving in a straight line over one empty or occupied circle, landing on a third circle which must be empty, and placing a marker there. Continue until no more moves are possible  the goal is to end with all nine markers placed and a single remaining empty circle. A pentagram is among several diagrams incised into stone slabs comprising the roof of the Temple of Kurna at Thebes, dating to the rule of Rameses I circa 1400 B.C. The diagrams are supposedly gaming boards, cut there by the stonemasons who were shaping the slabs in the quarries. Three of the various diagrams were partly cut away when the stones were finally trimmed and placed in the roof of the temple. 
Peg puzzles can also have transposition as their objective. A peg can either move forward, or jump a peg in front of it (but neither is removed). The object is to exchange the two sets of pegs. See U.S. Patent 243688  Bullard 1881. The lefthand version of peg solitaire is similar to "Teez" offered by Tryne. I have also heard it called "Mountain Goats"  pretend the pegs are two lines of mountain goats traveling in opposite directions on a narrow mountain path, who need to pass but the path is only wide enough for one goat so they must jump over each other. Also pictured is Hop Over by Pressman. Kohner's Switch poses several transposition challenges. On the right is a vintage British metal puzzle called Draught Board  identical in principle to Hop Over. 
I found a second Draught Board puzzle  but this second one (the goldhued one in the comparison photos) is
an inferior copy of the original silverhued version I have.
In particular, see the photos of the backs of the two puzzles.
The copy is blank, while the original has instructions and a registry number (594918).

Martin Gardner mentions in his book The Last Recreations that the minimum number of moves necessary to exchange the two sides of checkers pieces without forcing any jumps has been proven to be 120. Anthony Filipiak in his book 100 Puzzles  How to Make and Solve Them discusses several peg problems, including some played in linear fashion, on a circular board, and on a Chinese Checkers board. Filipiak describes a simple and interesting variation using just 3 bicolor pegs, that can be played just as well with 3 coins. Align the 3 coins with the 2 end coins headsup and the center coin tailsup. Now, in exactly three moves, where a move consists of flipping any two coins in place, get all 3 coins either heads up or tails up. (Reread the previous sentence if you're thinking, "I can solve that in one move!" You need to do it in "exactly three moves.") A vintage Presidential Muddle Puzzle:
Yes, it is missing a button  but it is sturdy metal and larger than I thought. I like it a lot. See U.S. Patent 524703  Carter Aug. 1894

Balance the Wheel, No. 108 "An L. J. Gordon creation" by Peterson Games of Sacramento CA, 1972. The box claims it is "A puzzle which becomes increasingly difficult as you get closer and closer to the ultimate objective." A transposition puzzle akin to Hop Over, around a circular track, with six pegs of each of two colors.

The "Lucky Plucky Lindy Bird Puzzle" (I don't have this  shown for reference.) Copyright 1927 by W. N. Ebling Eight wooden pieces each with one letter from "LINDBERG"  I believe there are 10 numbered spaces. Start with the pieces at: E1 D2 G3 I4 R5 L6 B7 N8. Move two adjacent blocks at a time into any two vacant adjacent spaces. In four such moves, rearrange the letters to spell LINDBERG. Then, starting with the letters where they end up, make the same type of move, end with GREBDNIL, using any number of moves. 
Other examples of puzzles where moves are governed by rules rather than physically:
Rubik's Triamid 
Switchback  Binary Arts 
Think and Jump  Pressman 
Thinkfun's Stormy Seas 
This is Binary Arts' Lunar Lockout. You can read about the genesis of this puzzle and a computer analysis of it on John Rausch's site. You can play Lunar Lockout online here. 
Pete's Pike  Thinkfun An updated version of Lunar Lockout. 
TipOver  Thinkfun 
Hoppers  Binary Arts 
Leapin' Lizards  Binary Arts 
Hot Spot  Thinkfun 
Subtrax  Thinkfun 
Cool Moves (a type of peg solitaire) by Discovery Toys 
Oops!  from Foxmind 50 challenges  set up the pieces as indicated by the challenge card. Goal is to end with a stack having the hat on the bottom and the head on the top. The hat cannot move. A stack can move orthogonally a number of spaces equal to the number of pieces contained in the stack. Every move must end on top of another piece, culminating of course with the hat. 
Solitaire Chess invented by Vesa Timonen For each of 60 challenges of graduated difficulty, successively capture pieces using legal chess moves until only one remains. 
This puzzle is called Right On and was produced by Skor Mor. There are five colored pegs each of which can hold seven discs. There are twenty discs, four of each peg color. The instructions give an initial arrangement of the discs. The goal is to get all four discs of each color onto their corresponding pegs. You can only transfer one or a stack of two adjacent discs at a time, and the bottom moving disc must land either on an empty peg of its color, or on another disc of its color. It can be done in 26 moves. 
Right On appears identical to this 1984 puzzle I do not have, from Marks and Spencer, called "Stack It." 
The Olympic WanderRings seem to be a version of the same puzzle. They were produced by Logical Toys in Hungary as a souvenir of the 100th Olympic Games, held in Atlanta. 
This puzzle asks you to achieve a specific goal ordering of objects given an initial ordering and constraints on moving the objects.
The set of objects are the nine ("traditional") planets and the initial ordering from left to right is:
The goal ordering is the “natural” ordering:
The rules for movements are as follows:
For example, a legal first move would be to take the subset (Venus Pluto Jupiter) and move it to the left, resulting in the new state:
The Exhaustive Method
One approach to a solution is an exhaustive search of all possible moves. This entails exploring all the possible legal moves (many of which will not be smart moves) while not missing any, and ideally also not unnecessarily repeating any. The search can be organized as a tree, with the initial state as the root, each node representing a particular ordering/state, and each edge representing a specific legal move. The limit of four moves defines the exact depth at which all branches must terminate. On termination, each leaf node will be either a solution equal to the goal ordering or a nonsolution indicating an unsuccessful sequence of four moves. The search may terminate when the first leaf node equal to the goal state is found, unless an enumeration of all possible solutions is required in which case the entire tree must be realized.
The size of this tree can be determined as follows. From the initial state, there are 6 possible moves  you can choose any group of 3 adjacent planets beginning with the second from the left (Venus) and ending with the third from the right (Neptune). In fact, at each level of the tree, from each node, there will always be 6 possible moves. In four moves, there will be 6*6*6*6 = 1296 possible branches. While the exploration of this tree can be automated, doing it by hand will be tedious and timeconsuming (unless by luck a solution branch is found early). However, the problem can be approached heuristically using some puzzlesolving techniques I’ll explain below.
Working Backwards
First, one should look at the goal state and work backwards to see if additional constraints can be deduced which can serve to reduce the search space. This technique is sometimes fruitful when solving mazes, for example, especially mazes constructed by hand since often the psychology of the mazemaker leads them to unconsciously build in more choices near the entrance and fewer near the exit.
In the case of the Aligning the Planets puzzle, we have the following. Examining the goal state we can deduce with certainty that the last (4th) move must put the leftmost 3 planets into their proper positions. This means that the 4th move must take the subset (Pluto Neptune Uranus) from somewhere in the sequence and move it to the left end intact. Furthermore, at that point the rest of the sequence must also be in its final goal form. This means that prior to this 4th move, Saturn must be on the left end.
What must be to the immediate right of Saturn at this time (i.e. prior to the 4th move but after the 3rd move)? There are only two possibilities: either the (Pluto Neptune Uranus) subset must itself have come from there, or the required Jupiter must already be there, since only the 4th move remains so there would be no other way to get Jupiter to where it is needed.
Let’s find a helpful way to diagram what we’ve deduced so far:
Initial state: [Earth Venus Pluto Jupiter Mars Uranus Neptune Saturn Mercury]
Possible States after 1st move: (6 of them)…
Possible States after 2nd move: (36 of them)…
Viable States after 3rd move:
Goal state after 4th move: [Pluto Neptune Uranus Saturn Jupiter Mars Earth Venus Mercury]
Viable means that the state can lead to the required next state  in this case the goal state  in one move.
Simplifying the Problem
To make further progress, we employ the mathematical technique of making an assumption, then showing that either the assumption leads to a contradiction or absurdity, in which case it must be false, or that we can prove the assumption true.
The assumption I’ll investigate is as follows. Note that in the initial state, Earth Venus and Mercury, though not yet adjacent, are already in the correct order. Is it possible that the only planets that must be moved are the middle six (Pluto Jupiter Mars Uranus Neptune Saturn)? Note that moving them would ensure that they end up to the left of Earth and Venus, and we leave Mercury where it is, eventually resulting in Earth Venus Mercury in order on the right as required.
If we look at only these middle six planets, we have effectively reduced the search space  we have simplified the problem to finding a way to order just these six planets correctly. The size of the search tree is more tractable since now within these six planets there are only three possible moves at any time.
Bear in mind that if our assumption is false  i.e. that the true solution in fact requires moves that involve any of Earth Venus Mercury, then we will have to explore the entire tree for the six planets and show there are no solutions within it to this reduced problem. However, this smaller tree for the six planets has 3*3*3*3 = only 81 branches.
We can employ the same strategy of looking backwards from the goal on this subset as we did on the whole set. By working simultaneously forward from the initial state and backwards from the goal we might be able to see a solution more easily.
Our diagram now looks like the following.
Initial state: [Pluto Jupiter Mars Uranus Neptune Saturn]
All Possible States after 1st move:
Possible States after 2nd move: ?
Viable States after 3rd move:
Goal state after 4th move: [Pluto Neptune Uranus Saturn Jupiter Mars]
Bridging the Gap  An Intuitive Leap
Now our problem is to find a (or show there is no) second move and resulting state that bridges the gap from one of the 3 possible states ac shown after the 1st move, to one of the 3 viable states xz shown after the 3rd move.
A methodical exploration begins with an examination of the 3 possible 2nd moves and resulting states available from (a):
Are any of these states 13 one legal move away from any of the 3 viable states xz?
By inspection, we can find that, yes, in fact #3 is. From #3, we can make the move (Saturn Jupiter Mars) to end up with (x) the first viable alternative: Saturn Jupiter Mars Pluto Neptune Uranus.
We have found our bridge and validated our assumption. In fact, if we now piece together our conclusions, we have solved the puzzle by finding a sequence of four moves that accomplishes the goal.
Granted, it was fortunate that we only had to examine part of even the reduced sixplanet tree before running across a solution. If the puzzle had been constructed so that our assumption was false, we would have had more work to do to prove that. In fact, puzzle makers do this to increase the difficulty and/or “elegance” of their puzzles  deliberately craft the puzzle conditions and constraints so that a solution does not arise by chance easily.
A Solution
The solution we’ve found is as follows. The subset of planets to be moved is enclosed in parenthesis in each state, beginning with the initial state. Per our assumption, Earth Venus and Mercury are never moved. The last state is the goal.