peg solitaire

Peg solitaire is a game for one player. You begin with an arrangement of pegs - the diagram below shows the most common starting arrangement.

    * * *
    * * *
* * * * * * *
* * *   * * *
* * * * * * *
    * * *
    * * *

The aim is to leave just one peg in the centre, by repeatedly jumping one peg over another in a horizontal or vertical line, and removing the peg which was jumped over.

Two peg solitaire positions are sometimes said to be equivalent if one can be converted into the other by a sequence of forwards or backwards moves. (A backwards move is jumping a peg over an empty hole and filling the hole.) It can be proved that two positions are equivalent if and only if one can be transformed into the other by repeatedly taking any three adjacent pegs/holes and inverting them - replacing all the holes by pegs and all the pegs by holes. Since forwards and backwards moves are special case of this inversion procedure, it's clear that if two positions cannot be transformed into each other this way, then they are not equivalent. The inverse of this statement is not so obvious, but has been proved mathematically.

A variant on the "classic" peg solitaire layout described by wangmu is a fifteen-peg game commonly found at the Cracker Barrel with which the idea is to jump pegs and end up with one left. The pegs are arranged in a triangular fashion:

	    *
	   * *
	  * * *
	 * * * *
	* * * * *

To begin, the player removes any peg from the board. The game proceeds in the same manner as the classic game by jumping pegs and removing the jumped pegs. The goal is, of course, to finish with one peg.

Here's the instructions on the Cracker Barrel game:

"Jump All But One Games"
Jump each tee and remove it
Leave only one -- you're genius
Leave two and you're purty smart
Leave three and you're just plain dumb
Leave four or mor'n you're just plain
"EG-NO-RA-MOOSE"

Cracker Barrel Old Country Store

Being the hacker type, I wrote a little Perl script to analyze the possible ways to jump the pegs so that one peg remains. To simplify my description, I'll label the points the board as follows:

	    A
	   B C
	  D E F
	 G H I J
	K L M N O

Now, accounting for symmetry and rotation of the board, there are four logically different starting points — A, B, D, and E. K and O are the same as A; C, G, J, L, and N are all the same as B; F and M are equivalent to D; finally, H and I can be translated to E.

According to my script (which, I should add, was slapped together and not extensively checked, so the resulting numbers might be inaccurate) the number of different winning combinations and the possibilities for the last position are largely dependent on what peg is taken out first.

	Peg |  Wins | Final position
	----+-------+---------------
	D   | 85258 | C, D, I, L, O
	A   | 29760 | A, M, F, J
	B   | 14880 | B, K, N, F
	E   |  1550 | M

(Note: these are the "raw" numbers, not accounting for symmetry/rotation.)

Therefore, the best bet for winning the game is to start by removing peg D (or, if you like, F or M). I've noticed many people start with E/H/I, which is perhaps why they always end up with four or five pegs left.

As an interesting (?) side note, it does not appear to be possible to jump the pegs in any way that results in the mythical eight-peg endgame. (I read somewhere that it was possible but that there were only a few ways to do it, and now I'm quite sure that the person who wrote that was just making shit up.)

If you'd like to impress your friends with your amazing ability to move little pieces of plastic, but don't want to spend several hours figuring out how to get it right, here's a few ways to end up with one peg, and even in the same position the first peg was taken from:

• Remove A, D-A, F-D, G-B, A-D, O-F, L-E, N-L, K-M, C-J, M-F, J-C, D-F, F-A
• Remove B, G-B, M-D, B-G, C-H, J-C, A-F, K-M, N-L, F-M, L-N, O-M, M-D, G-B
• Remove D, M-D, K-M, N-L, J-H, C-J, O-F, D-M, A-D, G-B, B-I, L-N, N-E, F-D

Cracker Barrel distributes the game with a cheat sheet describing another solution, though it doesn't leave the last peg in the starting position:

Remove A, D-B, F-D, A-F, G-B, L-D, I-H, B-G, G-I, O-L, K-N, F-L, N-K, J-L