Jump to content

Peg solitaire

From Wikipedia, the free encyclopedia

This is an old revision of this page, as edited by ZéroBot (talk | contribs) at 08:10, 20 April 2012 (r2.7.1) (Robot: Adding eu:Bakar-joko (taula-jokoa)). The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.

The Princess of Soubise playing solitaire, 1697

Peg solitaire is a board game for one player involving movement of pegs on a board with holes. Some sets use marbles in a board with indentations. The game is known simply as Solitaire in the United Kingdom where the card games are called Patience. It is also referred to as Brainvita (especially in India).

According to a popular story, the game was invented by a French aristocrat in the 17th century, when incarcerated in the Bastille, explaining the game's less common name Solo Noble. John Beasley (author of "The Ins and Outs of Peg Solitaire") has extensively searched for evidence to support this, and has found it lacking. The first reference to this story appeared in 1810, more than a hundred years after the alleged event. He believes that the colorful tale is fiction, yet it persists. In other sources, the invention of the game is attributed to the Native Americans—there is also no evidence to support this.

The first evidence of the game can be traced back to the court of Louis XIV, and the specific date of 1697, with an engraving made that year by Claude Auguste Berey of Anne de Rohan-Chabot, Princess of Soubise, with the puzzle by her side. Several works of art from that time show peg solitaire boards, demonstrating that the game was highly fashionable.

The standard game fills the entire board with pegs except for the central hole. The objective is, making valid moves, to empty the entire board except for a solitary peg in the central hole.

Board

There are two traditional boards, graphically depicted as follows ('.' as an initial peg, 'o' as an initial hole):

English peg solitaire board
European peg solitaire board
   English          European
      · · ·             · · ·
      · · ·           · · · · ·
  · · · · · · ·     · · · · · · ·
  · · · o · · ·     · · · o · · ·
  · · · · · · ·     · · · · · · ·
      · · ·           · · · · ·
      · · ·             · · ·

Play

A valid move is to jump a peg orthogonally over an adjacent peg into a hole two positions away and then to remove the jumped peg.

In the diagrams which follow, * indicates a peg in a hole, * emboldened indicates the peg to be moved, and o indicates an empty hole. A green ¤ is the hole the current peg moved from; a red * is the final position of that peg, a red o is the hole of the peg that was jumped and removed.

Thus valid moves in each of the four orthogonal directions are: 

* * o  →  ¤ o *  Jump to right

o * *  →  * o ¤  Jump to left 

*     ¤
*  →  o  Jump down
o     *

o     *
*  →  o  Jump up
*     ¤

On an English board, the first three moves might be: 

    * * *             * * *             * * *             * * * 
    * * *             * ¤ *             * o *             * * * 
* * * * * * *     * * * o * * *     * ¤ o * * * *     * o o o * * *
* * * o * * *     * * * * * * *     * * * * * * *     * * * ¤ * * *
* * * * * * *     * * * * * * *     * * * * * * *     * * * * * * *
    * * *             * * *             * * *             * * *
    * * *             * * *             * * *             * * *

Strategy

It is very easy to go wrong and find you have two or three widely spaced lone pegs. Many people never manage to solve the problem.

There are many different solutions to the standard problem, and one notation used to describe them assigns letters to the holes: 

   English          European
    a b c             a b c
    d e f           y d e f z
g h i j k l m     g h i j k l m
n o p x P O N     n o p x P O N
M L K J I H G     M L K J I H G
    F E D           Z F E D Y
    C B A             C B A

This mirror image notation is used, amongst other reasons, since on the European board, one set of alternative games is to start with a hole at some position and to end with a single peg in its mirrored position. On the English board the equivalent alternative games are to start with a hole and end with a peg at the same position.

There is no solution to the European board with the initial hole centrally located, if only orthogonal moves are permitted. This is easily seen as follows, by an argument from Hans Zantema. Divide the positions of the board into A, B and C positions as follows: 

    A B C
  A B C A B
A B C A B C A
B C A B C A B
C A B C A B C
  B C A B C
    A B C

Initially with only the central position free, the number of covered A positions is 12, the number of covered B positions is 12, and also the number of covered C positions is 12. After every move the number of covered A positions increases or decreases by one, and the same for the number of covered B positions and the number of covered C positions. Hence after an even number of moves all these three numbers are even, and after an odd number of moves all these three numbers are odd. Hence a final position with only one peg can not be reached: then one of these numbers is one (the position of the peg, one is odd), while the other two numbers are zero, hence even.

There are, however, several other configurations where a single initial hole can be reduced to a single peg.

A tactic that can be used is to divide the board into packages of three and to purge (remove) them entirely using one extra peg, the catalyst, that jumps out and then jumps back again. In the example below, the * is the catalyst.: 

* * o      ¤ o *      o * *      * o ¤
  *    ->    *    ->    o    ->    o
  *          *          ¤          o

This technique can be used with a line of 3, a block of 2*3 and a 6-peg L shape with a base of length 3 and upright of length 4.

Other alternate games include starting with two empty holes and finishing with two pegs in those holes. Also starting with one hole here and ending with one peg there. On an English board, the hole can be anywhere and the final peg can only end up where multiples of three permit. Thus a hole at a can only leave a single peg at a, p, O or C.

Studies on peg solitaire

A thorough analysis of the game is provided in Winning Ways ISBN 0-12-091102-7 in the UK and ISBN 1-56881-144-6 in the US (Vol 4, 2nd edition). They introduced a notion called pagoda function which is a strong tool to show the infeasibility of a given (generalized) peg solitaire problem. A problem for finding a pagoda function (which concludes the infeasibility of a given problem) is formulated as a linear programming problem and solvable in polynomial time (see Kiyomi and Matsui 2001). Uehara and Iwata (1990) dealt with the generalized Hi-Q problems which are equivalent to the peg solitaire problems and showed their NP-completeness. Avis and Deza (1996) formulated a peg solitaire problem as a combinatorial optimization problem and discussed the properties of the feasible region called 'a solitaire cone'. Kiyomi and Matsui (2001) proposed an efficient method for solving peg solitaire problems.

An unpublished study from 1989 on a generalised version of the game on the English board showed that each possible problem in the generalised game has 2^9 possible distinct solutions, excluding symmetries, as the English board contains 9 distinct 3*3 sub-squares. One consequence of this analysis is to put a lower bound on the size of possible 'inverted position' problems, in which the cells initially occupied are left empty and vice versa. Any solution to such a problem must contain a minimum of 11 moves, irrespective of the exact details of the problem.

Solutions to the English game

The shortest solution to the standard English game involves 18 moves, counting multiple jumps as single moves:

This solution was found in 1912 by Ernest Bergholt and proven to be the shortest possible by John Beasley in 1964.[1]

This solution can also be see on a page that also introduces the Wolstenholme notation, which is designed to make memorizing the solution easier.

Other solutions include the following list. In these, the notation used is

  • List of starting holes
  • Colon
  • List of end target pegs
  • Equals sign
  • Source peg and destination hole (you have to work out what it jumps over yourself)
  • , or / (a slash is used to separate 'chunks' such as a six-purge out)
x:x=ex,lj,ck,Pf,DP,GI,JH,mG,GI,ik,gi,LJ,JH,Hl,lj,jh,CK,pF,AC,CK,Mg,gi,ac,ck,kI,dp,pF,FD,DP,Pp,ox
x:x=ex,lj,xe/hj,Ki,jh/ai,ca,fd,hj,ai,jh/MK,gM,hL,Fp,MK,pF/CK,DF,AC,JL,CK,LJ/PD,GI,mG,JH,GI,DP/Ox
j:j=lj,Ik,jl/hj,Ki,jh/mk,Gm,Hl,fP,mk,Pf/ai,ca,fd,hj,ai,jh/MK,gM,hL,Fp,MK,pF/CK,DF,AC,JL,CK,LJ/Jj
i:i=ki,Jj,ik/lj,Ik,jl/AI,FD,CA,HJ,AI,JH/mk,Hl,Gm,fP,mk,Pf/ai,ca,fd,hj,ai,jh/gi,Mg,Lh,pd,gi,dp/Ki
e:e=xe/lj,Ik,jl/ck,ac,df,lj,ck,jl/GI,lH,mG,DP,GI,PD/AI,FD,CA,JH,AI,HJ/pF,MK,gM,JL,MK,Fp/hj,ox,xe
d:d=fd,xe,df/lj,ck,ac,Pf,ck,jl/DP,KI,PD/GI,lH,mG,DP,GI,PD/CK,DF,AC,LJ,CK,JL/MK,gM,hL,pF,MK,Fp/pd
b:b=jb,lj/ck,ac,Pf,ck/DP,GI,mG,JH,GI,PD/LJ,CK,JL/MK,gM,hL,pF,MK,Fp/xo,dp,ox/xe/AI/BJ,JH,Hl,lj,jb
b:x=jb,lj/ck,ac,Pf,ck/DP,GI,mG,JH,GI,PD/LJ,CK,JL/MK,gM,hL,pF,MK,Fp/xo,dp,ox/xe/AI/BJ,JH,Hl,lj,ex
a:a=ca,jb,ac/lj,ck,jl/Ik,pP,KI,lj,Ik,jl/GI,lH,mG,DP,GI,PD/CK,DF,AC,LJ,CK,JL/dp,gi,pd,Mg,Lh,gi/ia
a:p=ca,jb,ac/lj,ck,jl/Ik,pP,KI,lj,Ik,jl/GI,lH,mG,DP,GI,PD/CK,DF,AC,LJ,CK,JL/dp,gi,pd,Mg,Lh,gi/dp

Brute force attack on standard English peg solitaire

The only place it is possible to end up with a solitary peg, is the centre, or the middle of one of the edges; on the last jump, there will always be an option of choosing whether to end in the centre or the edge.

Following is a table over the number (Possible Board Positions) of possible board positions after n jumps, and the number (No Further Jumps) of those positions from which no further jumps are possible.

If one board position can be rotated and/or flipped into another board position, the board positions are counted as identical.

nPBPNFJ
110
220
380
4390
51710
67191
72,7570
89,7510
931,3120
1089,9271
   
nPBPNFJ
11229,6141
12517,8540
131,022,2245
141,753,73710
152,598,2157
163,312,42327
173,626,63247
183,413,313121
192,765,623373
201,930,324925
   
nPBPNFJ
211,160,9771,972
22600,3723,346
23265,8654,356
24100,5654,256
2532,2503,054
268,6881,715
271,917665
28348182
295039
3076
   
nPBPNFJ
3122

Since the maximum number of board positions at any jump is 3,626,632, and there can only be 31 jumps, modern computers can easily examine all game positions in a reasonable time.

The above sequence "PBP" has been entered as A112737 in OEIS. Note that the total number of reachable board positions (sum of the sequence) is 23,475,688, while the total number of possible board positions is 2^33, or approximately 2^33/8 ~ 1 billion when symmetry is taken into account. So only about 2.2% of all possible board positions can be reached starting with the center vacant.

It is also possible to generate all board positions. The results below have been obtained using the mcrl2 toolset (see the peg_solitaire example in the distribution).

nPBP
11
24
312
460
5296
61,338
75,648
821,842
   
nPBP
977,559
10249,690
11717,788
121,834,379
134,138,302
148,171,208
1514,020,166
1620,773,236
   
nPBP
1726,482,824
1828,994,876
1927,286,330
2022,106,348
2115,425,572
229,274,496
234,792,664
242,120,101
   
nPBP
25800,152
26255,544
2768,236
2814,727
292,529
30334
3132
325

Solutions to the European game

There are 3 initial non-congruent positions that have solutions.[citation needed] These are:

1) 

          0 1 2 3 4 5 6
        0     o * *
        1   * * * * *
        2 * * * * * * *
        3 * * * * * * *
        4 * * * * * * *
        5   * * * * *
        6     * * *

Possible solution: [2:2-0:2, 2:0-2:2, 1:4-1:2, 3:4-1:4, 3:2-3:4, 2:3-2:1, 5:3-3:3, 3:0-3:2, 5:1-3:1, 4:5-4:3, 5:5-5:3, 0:4-2:4, 2:1-4:1, 2:4-4:4, 5:2-5:4, 3:6-3:4, 1:1-1:3, 2:6-2:4, 0:3-2:3, 3:2-5:2, 3:4-3:2, 6:2-4:2, 3:2-5:2, 4:0-4:2, 4:3-4:1, 6:4-6:2, 6:2-4:2, 4:1-4:3, 4:3-4:5, 4:6-4:4, 5:4-3:4, 3:4-1:4, 1:5-1:3, 2:3-0:3, 0:2-0:4]

2) 

          0 1 2 3 4 5 6
        0     * * *
        1   * * o * *
        2 * * * * * * *
        3 * * * * * * *
        4 * * * * * * *
        5   * * * * *
        6     * * *

Possible solution: [1:1-1:3, 3:2-1:2, 3:4-3:2, 1:4-3:4, 5:3-3:3, 4:1-4:3, 2:1-4:1, 2:6-2:4, 4:4-4:2, 3:4-1:4, 3:2-3:4, 5:1-3:1, 4:6-2:6, 3:0-3:2, 4:5-2:5, 0:2-2:2, 2:6-2:4, 6:4-4:4, 3:4-5:4, 2:3-2:1, 2:0-2:2, 1:4-3:4, 5:5-5:3, 6:3-4:3, 4:3-4:1, 6:2-4:2, 3:2-5:2, 4:0-4:2, 5:2-3:2, 3:2-1:2, 1:2-1:4, 0:4-2:4, 3:4-1:4, 1:5-1:3, 0:3-2:3]

and 3) 

          0 1 2 3 4 5 6
        0     * * *
        1   * * * * *
        2 * * * o * * *
        3 * * * * * * *
        4 * * * * * * *
        5   * * * * *
        6     * * *

Possible solution: [2:1-2:3, 0:2-2:2, 4:1-2:1, 4:3-4:1, 2:3-4:3, 1:4-1:2, 2:1-2:3, 0:4-0:2, 4:4-4:2, 3:4-1:4, 6:3-4:3, 1:1-1:3, 4:6-4:4, 5:1-3:1, 2:6-2:4, 1:4-1:2, 0:2-2:2, 3:6-3:4, 4:3-4:1, 6:2-4:2, 2:3-2:1, 4:1-4:3, 5:5-5:3, 2:0-2:2, 2:2-4:2, 3:4-5:4, 4:3-4:1, 3:0-3:2, 6:4-4:4, 4:0-4:2, 3:2-5:2, 5:2-5:4, 5:4-3:4, 3:4-1:4, 1:5-1:3]

Board variants

Peg solitaire has been played on other size boards, although the two given above are the most popular. It has also been played on a triangular board, with jumps allowed in all 3 directions. As long as the variant has the proper "parity" and is large enough, it will probably be solvable.

Peg Solitaire game board shapes:
(1) French (European) style, 37 holes, 17th century;
(2) J. C. Wiegleb, 1779, Germany, 45 holes;
(3) Asymmetrical 3-3-2-2 as described by George Bell, 20th century;
(4) English style (standard), 33 holes;
(5) Diamond, 41 holes;
(6) Triangular, 15 holes.
Grey = the hole for the survivor.

A common triangular variant has five pegs on a side. A solution where the final peg arrives at the initial empty hole is not possible for a hole in one of the three central positions. An empty corner-hole setup can be solved in ten moves, and an empty midside-hole setup in nine (Bell 2008):

SAS code to solve the triangular board

This solution has been proposed by Houliang Li, Frederick, MD. [2] The board is represented as a string of hexadecimal integers starting from the top and going left to right. The empty space is indexed by zero. 

 options nosymbolgen nomprint nomlogic mcompilenote=NOAUTOCALL;
/***it takes about six minutes to find a solution starting with the hole at the top of the pegboard***/
%macro pegboard (start, moves, backtostart=NO, allsolutions=NO) ;
/*start is the peg lineup for each function call and is always 15 character long*/
/*moves keeps track of all legal moves made so far*/
/*backstart=YES if the solution in which the final peg is in the initial hole is desired*/
/*allsolutions=YES if all solutions to a particular starting lineup are requested*/

/*initial setup*/
%local index;/*it is local so that it can keep a separate record of the iterations over the possible legal moves during each macro's execution*/
%if %length(%sysfunc(compress(&start, 0)))=14 %then %do;
	%global originalstart starthole success legalmoves;
	%let originalstart=&start;
	%let starthole= %index(&start,0);
	%let success = 0 ;
	%let legalmoves=124|247|47b|b74|742|421|136|36a|6af|fa6|a63|631|bcd|cde|def|fed|edc||dcb|358|58c|c85|853|259|59e|e95|952|789|89a|a98|987|69d|d96|48d|d84|456|654;
%end;
/*loop over possible legal moves*/
%do index=1 %to 36;/***>>><<<***/
	%if  not &success or (&success and %upcase(&allsolutions)=YES) %then %do;/***XXXXXX***/
	/*if it is not a solution and there are no particular request made with the macro parameters*/
	/*PREPARE FOR THE INDEX-TH MOVE*/
		%let nextmove=%scan(&legalmoves,&index, |);
		/*extract from string legalmoves the index-th word (i.e. a single move) and put it in the variable next move*/
		%let first=%substr(&nextmove,1,1); /*name the pegs involved in the move*/
		%let second=%substr(&nextmove,2,1);
		%let third=%substr(&nextmove,3,1);
			/*conversion from hexadecimal digits, used in parts to represent pegs, to decimal equivalents*/
		%if &first > 9 %then
			%let first=%eval(%sysfunc(rank(&first))-87);
			/*rank returns an integer that represent the character in the ASCII collating sequence*/
		%if &second > 9 %then
			%let second=%eval(%sysfunc(rank(&second))-87);
		%if &third > 9 %then
			%let third=%eval(%sysfunc(rank(&third))-87);
		%if %substr(&start,&first,1)>0 and %substr(&start,&second,1)>0 and %substr(&start,&third,1)=0 %then %do; /***§§§§§§***/
		/*if the first peg can jump over the second and land in a hole*/
		/*DO THE INDEX-TH MOVE*/
			%let allmoves = &moves &first - &second - &third; /* take note of the move in the variable allmoves*/
			%if &first = 1 %then /*if the jumping peg was in the move is at the top of the pegboard*/
				%let newstart=0%substr(&start,2);/*put a hole in the starting point of the jumping peg in the new pegboard*/
			%else %if &first=15 %then /*if the first peg involved in the move is at the bottom right angle of the pegboard*/
				%let newstart=%substr(&start,1,14)0;/*put a hole in the new pegboard in the bottom right angle*/
			%else
				%let newstart=%substr(&start,1,&first - 1)0%substr(&start,&first + 1);
				/*put a hole in the new pegboard at the starting position of the jumping peg*/
			%let newstart=%substr(&newstart,1,&second - 1)0%substr(&newstart,&second + 1);
			/*put a hole at the place of the jumped peg which is taken away from the pegboard*/
			%if &third=1 %then
			/*if the third place involved in the move, the landing place of the jumping peg, is the top place of the pegboard*/
				%let newstart=%substr(&start,&first,1)%substr(&newstart,2);
				/*take the first peg involved in the move and put it in the first place of the new pegboard*/
			%else %if &third=15 %then
			/*if the third place of the move is the bottom right angle*/
				%let newstart=%substr(&newstart,1,14)%substr(&start,&first,1);
				/*put the jumping peg in the bottom right angle of the new pegboard*/
			%else 
				%let newstart = %substr(&newstart,1,&third - 1)%substr(&start,&first,1)%substr(&newstart,&third +1);
				/*put in the landing place of the new pegboard the jumping peg involved in the move*/	
			%if %length(%sysfunc(compress(&newstart,0)))=1 
			and (%upcase(&backtostart)=NO or %upcase(&backtostart)=YES and %substr(&newstart,&starthole,1)>0) %then %do;
			/*if the new pegboard has a unique peg and there are no particular request made with the macro parameter */
				%let success=1;
				%put Starting position is: &originalstart;
				%put successful moves are: &allmoves;
			%end;
			%else %do;
				%pegboard(&newstart,&allmoves);
			%end;
		%end;/***§§§§§§***/		
	%end;/***XXXXXX***/
%end;/***>>><<<***/
%mend pegboard;

To execute this program the following call has to be done with the initial configuration of the board passed as a parameter.

%pegboard(023456789abcdef, )

Literature

  1. ^ For Beasley's proof see Winning Ways, volume #4 (second edition).
  2. ^ For the original paper see http://analytics.ncsu.edu/sesug/2006/SC05_06.PDF,
  • Avis, D.; Deza, A. (2001), "On the solitaire cone and its relationship to multi-commodity flows", Mathematical Programming, 90 (1): 27–57, doi:10.1007/PL00011419.
  • Beasley, J. D. (1985), The Ins and Outs of Peg Solitaire, Oxford.
  • Bell, G. I. (2008), "Solving triangular peg solitaire", Journal of Integer Sequences, 11: Article 08.4.8, arXiv:math.CO/0703865.
  • Berlekamp, E. R.; Conway, J. H.; Guy, R. K. (1982), Winning Ways for your Mathematical Plays, London: Academic Press.
  • de Bruijn, N. G. (1972), "A solitaire game and its relation to a finite field", Journal of Recreational Mathematics, 5: 133–137.
  • Cross, D. C. (1968), "Square solitaire and variations", Journal of Recreational Mathematics, 1: 121–123.
  • Gardner, M., "Mathematical games", Scientific American 206 (6): 156–166, June 1962; 214 (2): 112–113, Feb. 1966; 214 (5): 127, May 1966.
  • Kiyomi, M.; Matsui, T. (2001), "Integer programming based algorithms for peg solitaire problems", Proc. 2nd Int. Conf. Computers and Games (CG 2000), Lecture Notes in Computer Science, vol. 2063, pp. 229–240, doi:10.1007/3-540-45579-5_15.
  • Uehara, R.; Iwata, S. (1990), "Generalized Hi-Q is NP-complete", Trans. IEICE, 73: 270–273.
Wikimedia Commons has media related to Peg solitaire.
Retrieved from "https://en.wikipedia.org/w/index.php?title=Peg_solitaire&oldid=488302502"