Peg solitaire

From Wikipedia, the free encyclopedia

English peg solitaire board
English peg solitaire board
European peg solitaire board
European peg solitaire board

Peg Solitaire is a board game for one player involving movement of pegs on a board with holes. 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). Some sets use marbles in a board with indentations.

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 American Indians--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. 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.

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

   English          European
    · · ·             · · ·
    · · ·           · · · · ·
· · · · · · ·     · · · · · · ·
· · · o · · ·     · · · o · · ·
· · · · · · ·     · · · · · · ·
    · · ·           · · · · ·
    · · ·             · · ·


A simpler, triangular version with fifteen holes is a modern successor. [1]

Contents

[edit] Playing

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) and · indicates an empty hole.

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

* * ·  ->  · · *  Jump to right

· * *  ->  * · ·  Jump to left 

*      ·
*  ->  ·  Jump down
·      *

·      *
*  ->  ·  Jump up
*      ·

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

    * * *             * * *             * * *             * * * 
    * * *             * · *             * · *             * * * 
* * * * * * *     * * * · * * *     * · · * * * *     * · · · * * *
* * * · * * *     * * * * * * *     * * * * * * *     * * * · * * *
* * * * * * *     * * * * * * *     * * * * * * *     * * * * * * *
    * * *             * * *             * * *             * * *
    * * *             * * *             * * *             * * *

[edit] 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.

One solution to the standard English game is:

  1. e-x
  2. l-j
  3. c-k
  4. P-f
  5. D-P
  6. G-I
  7. J-H
  8. m-G-I
  9. i-k
  10. g-i
  11. L-J-H-l-j-h
  12. C-K
  13. p-F
  14. A-C-K
  15. M-g-i
  16. a-c-k-I
  17. d-p-F-D-P-p
  18. o-x

To see the above solution illustrated, go to Solution to peg solitaire. This solution is shortest because it involves touching only 18 pegs (not counting those removed from the board). The solution was found in 1912 by Ernest Bergholt and proven to be the shortest possible by John Beasley in 1964. For Beasley's proof see Winning Ways, volume #4 (second edition).

Note that following the solution in reverse, that is, o-x, P-p, D-P, F-D, p-F, d-p, k-I, etc... also works. However the reversed solution is longer than 18 moves.

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. [2]

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.:

* * ·      · · *      · * *      * · ·
  *    ->    *    ->    ·    ->    ·
  *          *          ·          ·

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.

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.

[edit] 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 infeasiblity 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 the 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.

[edit] Some solutions

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

Diagrams of many solutions can be found here.

[edit] 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 board 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.

n PBP NFJ
1 1 0
2 2 0
3 8 0
4 39 0
5 171 0
6 719 1
7 2,757 0
8 9,751 0
9 31,312 0
10 89,927 1
   
n PBP NFJ
11 22,9614 1
12 517,854 0
13 1,022,224 5
14 1,753,737 10
15 2,598,215 7
16 3,312,423 27
17 3,626,632 47
18 3,413,313 121
19 2,765,623 373
20 1,930,324 925
   
n PBP NFJ
21 1,160,977 1,972
22 600,372 3,346
23 265,865 4,356
24 100,565 4,256
25 32,250 3,054
26 8,688 1,715
27 1,917 665
28 348 182
29 50 39
30 7 6
   
n PBP NFJ
31 2 2

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.

[edit] Some solutions of European Peg Solitaire with solvable initial position

As pointed out in [3] there are 3 (reflections left out) initial positions that must have solutions. 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]

The 3 solutions above were generated by a Java program in 843, 821 and 209 seconds accordingly. The program was created by Juri Reinsalu (contact at gmail.com: juri.reinsalu).

[edit] Literature

  • Avis, D., and Deza, A.: Solitaire Cones, School of Computer Science, McGill University, Technical Report No. SOCS-96.8, 1996.
  • Beasley, J. D.: The Ins and Outs of Peg Solitaire, Oxford, 1985.
  • Beasley J. D.: Some notes on Solitaire, Eureka, 25 (1962), 13–18.
  • Berlekamp, E. R., Conway, J. H., and Guy, R. K.: Winning Ways for Mathematical Plays. Academic Press, London, 1982.
  • de Bruijn N. G.: A Solitaire Game and Its Relation to a Finite Field. Journal ofRecreational Mathematics, 5 (1972), 133–137.
  • Cross D. C.: Square Solitaire and Variations. Journal of Recreational Mathematics, 1 (1968), 121–123.
  • Gardner M.: Scientific American, 206 #6(June 1962), 156–166; 214 #2(Feb. 1966), 112–113; 214 #5(May 1966), 127.
  • Kiyomi, M. and Matsui, T.: Integer Programming Based Algorithms for Peg Solitaire Problems, Lecture Notes in Computer Science, vol. 2063 (2001), pp. 229--240.
  • Uehara, R., Iwata, S.: Generalized Hi-Q is NP-complete, Trans. IEICE, 73 (1990),270-273.

[edit] External links

Wikimedia Commons has media related to: