A 33-hole (32 peg) version of peg solitaire is widely available in the U.S. and parts of Europe, but the 37-hole (36 peg), more difficult version is popular in France and other areas of Europe. The results of computer program analysis for the 37-hole (French) version including total possible games for all possible initial positions, counts for all possible win sequences, and sample wining game moves are given here.




                                0   1   2
                            3   4   5   6   7
                        8   9  10  11  12  13  14
                       15  16  17  18  19  20  21
                       22  23  24  25  26  27  28
                           29  30  31  32  33
                               34  35  36

   Initially, a player places 36 pegs in a board that has 37 holes as per the above diagram. One hole will be left open. (Player’s choice as to the specific hole.) A possible initial board might look like:

                                O   P   P
                            P   P   P   P   P
                        P   P   P   P   P   P   P
                        P   P   P   P   P   P   P
                        P   P   P   P   P   P   P
                            P   P   P   P   P
                                P   P   P

   In the above diagram, the 36 pegs have been placed in holes 1 – 36 while hole “0” has been left open. A move consists of selecting a peg (from any of the peg positions), jumping either horizontally or vertically over some other peg, and landing in an empty hole. The jumped over peg is removed from the board.

   In the above diagram there are 2 legal moves.
1) The peg at “2” can jump over the peg at “1” and land in position “0”. The jumped over peg at “1” is removed.
     or
2) The peg at “10” can jump over the peg at “4” and land in position “0”. The jumped over peg at “4” is removed.

   If we try the first of these possibilities the board will look like the diagram below:

                                P   O   O
                            P   P   P   P   P
                        P   P   P   P   P   P   P
                        P   P   P   P   P   P   P
                        P   P   P   P   P   P   P
                            P   P   P   P   P
                                P   P   P

  For the next possible move, either the peg at “11” or the peg at“12” could jump up to the top row. The object of the game is to make a total of 35 jumps which will leave a single peg somewhere on the board. (Most trials will run out of legal moves before obtaining a single peg position.)

  For example, if you start with the hole at position “0” it is possible to leave a single peg at position “2” after a total of 35 moves. In fact there are 1,131,718,132,489,632,047,392 game sequences that will leave a single peg at position “2”. If you printed out a list of these winning sequences using single space printing at 6 solutions per inch (no top or bottom margins) , on continuous paper, the list would be more than 12,000,000,000 times longer than the average distance from the earth to the moon. Surely, there shouldn’t be any trouble finding at least one of these solutions. (Smirky grin)

                                O   O   P
                            O   O   O   O   O
                        O   O   O   O   O   O   O
                        O   O   O   O   O   O   O
                        O   O   O   O   O   O   O
                            O   O   O   O   O
                                O   O   O

   The bad news is that there are more than 5,000 times as many possible game sequences that will not produce the above winning position. (If you want to cheat, scan down the page for an example of a winning sequence.)




      The game rules state that a player has a choice of what hole should be left open at the start of the game. Only 16 of the 37 possible initial conditions can lead to a winning game. The diagram below shows what initial holes can lead to a winning game vs. those that have no single peg solution.

                                W   L   W
                            L   L   W   L   L
                        W   L   L   W   L   L   W
                        L   W   W   L   W   W   L
                        W   L   L   W   L   L   W
                            L   L   W   L   L
                                W   L   W

   If you start with the initial hole at any of the “L” positions, it is impossible to win the game. The best that could happen is that you are left with 2 pegs that are separated (no legal move). If you start in any of the “W” positions, it is possible to win. However, for any initial “W” position, there are only 4 possible finishing single peg positions. None of these allow a single peg solution in the initial hole.



   For the results below, we will examine what happens if the initial hole is in positions 0, 1, 3, 4, 5, 10, 11, and 18. Rotations and/or a reflection (mirror image) can be used to obtain all other possible initial positions.


                                0   1   2
                            3   4   5   6   7
                        8   9  10  11  12  13  14
                       15  16  17  18  19  20  21
                       22  23  24  25  26  27  28
                           29  30  31  32  33
                               34  35  36

   If the initial hole is at position “0”, there are 5,889,625,054,564,792,595,793,171 possible game sequences. A winning sequence will leave a single peg in position 2, 16, 19, or 36. (There are no other single peg solutions.)

   The number of possible winning sequences for each, and a sample solution for each are shown below.

Total Possible Games:  5,889,625,054,564,792,595,793,171
Final peg at “2”:          1,131,718,132,489,632,047,392 ways to win
Final peg at “16”:         2,596,612,238,681,448,154,246 ways to win
Final peg at “19”:         2,532,493,542,039,458,869,661 ways to win
Final Peg at “36”:         2,316,692,235,146,090,648,664 ways to win

No solutions for any other final peg position.

              <----------------- Initial hole at “0” ---------------->
 Move        Last  Peg       Last  Peg       Last  Peg       Last  Peg
Number         at  2           at 16           at 19           at 36
----------------------------------------------------------------------
   1          2 to  0         2 to  0         2 to  0         2 to  0
   2         11 to  1        11 to  1        11 to  1        11 to  1
   3          0 to  2         0 to  2         0 to  2         0 to  2
   4          3 to  5         3 to  5         3 to  5         3 to  5
   5          6 to  4         6 to  4         6 to  4         6 to  4
   6          9 to 11         9 to 11         9 to 11         9 to 11
   7         12 to 10        12 to 10        12 to 10        12 to 10
   8         14 to 12        14 to 12        14 to 12        14 to 12
   9         19 to  6        19 to  6        19 to  6        19 to  6
  10          2 to 12         2 to 12         2 to 12         2 to 12
  11         17 to 19        21 to 19        17 to 19        17 to 19
  12          4 to 17        19 to  6         4 to 17         4 to 17
  13         19 to  6         7 to  5        19 to  6        19 to  6
  14          7 to  5         4 to  6         7 to  5         7 to  5
  15         21 to 19        17 to  4        21 to 19        21 to 19
  16         23 to  9        15 to 17        23 to  9        23 to  9
  17          8 to 10        18 to 16         8 to 10         8 to 10
  18         17 to  4        23 to  9        17 to  4        17 to  4
  19          4 to  6         8 to 10         4 to  6         4 to  6
  20         25 to 23         4 to 17        25 to 23        25 to 23
  21         22 to 24        25 to 23        22 to 24        22 to 24
  22         27 to 25        22 to 24        27 to 25        26 to 12
  23         25 to 23        32 to 19        25 to 23         6 to 19
  24         29 to 16        28 to 26        29 to 16        28 to 26
  25         15 to 17        26 to 12        15 to 17        35 to 25
  26         34 to 24         6 to 19        34 to 24        25 to 23
  27         17 to 30        30 to 32        17 to 30        29 to 16
  28         35 to 25        17 to 30        35 to 25        15 to 17
  29         33 to 31        34 to 24        33 to 31        33 to 31
  30         30 to 32        36 to 26        30 to 32        19 to 32
  31         36 to 26        19 to 32        36 to 26        34 to 24
  32         25 to 27        33 to 31        25 to 27        17 to 30
  33         28 to 26        35 to 25        28 to 26        36 to 26
  34         26 to 12        25 to 23        26 to 12        30 to 32
  35         12 to  2        29 to 16         6 to 19        26 to 36

      It should be remembered that the above solution sequences are a result of computer searches. Search algorithms have a defined search sequence. If a 2nd final peg position shares early solution moves with the 1st final peg position, then the results of computer searches may show similar early move sequences. An extreme case shows up for final peg positions 2 and 19. The moves are identical except for the final move.


   If the initial hole is at position “1”, there are 4,165,647,885,507,148,792,455,478 possible game sequences. None of these will lead to a single peg solution.

   If the initial hole is at position “3”, there are 5,875,710,058,201,291,406,597,964 possible game sequences. None of these will lead to a single peg solution.

   If the initial hole is at position “4”, there are 12,315,900,287,442,257,292,351,833 possible game sequences. None of these will lead to a single peg solution.

   If the initial hole is at position “5”, there are 9,729,404,958,320,804,496,982,848 possible game sequences. A winning sequence will leave a single peg in position 8, 11, 14, or 31. (There are no other single peg solutions.)

   The number of possible winning sequences for each, and a sample solution for each are shown below.

Total Possible Games:  9,729,404,958,320,804,496,982,848
Final peg at “8”:          2,596,612,238,681,448,154,246 ways to win
Final peg at “11”:         4,052,938,255,966,544,591,906 ways to win
Final peg at “14”:         2,596,612,238,681,448,154,246 ways to win
Final Peg at “31”:         4,011,246,957,909,066,396,228 ways to win

No solutions for any other final peg position.

              <----------------- Initial hole at “5” ---------------->
 Move        Last  Peg       Last  Peg       Last  Peg       Last  Peg
Number         at  8           at 11           at 14           at 31
----------------------------------------------------------------------
   1          3 to  5         3 to  5         3 to  5         3 to  5
   2          6 to  4         6 to  4         6 to  4         6 to  4
   3         16 to  3        16 to  3        16 to  3        16 to  3
   4          3 to  5         3 to  5         3 to  5         3 to  5
   5         11 to  9        11 to  9        11 to  9        11 to  9
   6          1 to 11         1 to 11         1 to 11         1 to 11
   7          8 to 10         8 to 10         8 to 10         8 to 10
   8         11 to  9        11 to  9        11 to  9        11 to  9
   9         13 to 11        13 to 11        13 to 11        13 to 11
  10         22 to  8        22 to  8        22 to  8        18 to  5
  11          8 to 10         8 to 10         8 to 10        22 to  8
  12         17 to  4        17 to  4        17 to  4         8 to 10
  13          0 to 10         0 to 10         0 to 10        17 to  4
  14         19 to 17        19 to 17        11 to  9         0 to 10
  15         27 to 13        27 to 13        25 to 11        27 to 13
  16         14 to 12        14 to 12        23 to 25         7 to 20
  17         25 to 27        25 to 27        26 to 24        25 to 27
  18         28 to 26        28 to 26        27 to 13        23 to 25
  19         29 to 16        29 to 16        14 to 12        27 to 13
  20         32 to 19        32 to 19        19 to  6        14 to 12
  21         19 to  6        19 to  6         2 to 12        19 to  6
  22          2 to 12         2 to 12        11 to 13         2 to 12
  23         11 to 13        11 to 13         7 to 20        34 to 24
  24          7 to 20         7 to 20        21 to 19        36 to 26
  25         21 to 19        21 to 19        35 to 25        25 to 27
  26         30 to 32        30 to 32        25 to 23        28 to 26
  27         17 to 30        17 to 30        29 to 16        35 to 25
  28         34 to 24        34 to 24         9 to 23        25 to 27
  29         36 to 26        36 to 26        34 to 24        33 to 20
  30         19 to 32        19 to 32        23 to 25        21 to 19
  31         33 to 31        33 to 31        36 to 26        19 to  6
  32         35 to 25        35 to 25        25 to 27         6 to  4
  33         25 to 23        25 to 23        33 to 20         4 to 17
  34         23 to  9        23 to  9        19 to 21        17 to 30
  35         10 to  8         9 to 11        28 to 14        29 to 31


   If the initial hole is at position “10”, there are 29,105,246,880,681,150,847,158,004 possible game sequences. None of these will lead to a single peg solution.

   If the initial hole is at position “11”, there are 12,804,765,198,432,079,368,812,072 possible game sequences. A winning sequence will leave a single peg in position 5, 22, 25, or 28. (There are no other single peg solutions.)

   The number of possible winning sequences for each, and a sample solution for each are shown below.

Total Possible Games: 12,804,765,198,432,079,368,812,072
Final peg at “5”:          4,052,938,255,966,544,591,906 ways to win
Final peg at “22”:         2,532,493,542,039,458,869,661 ways to win
Final peg at “25”:         2,391,159,317,054,857,984,652 ways to win
Final Peg at “28”:         2,532,493,542,039,458,869,661 ways to win

No solutions for any other final peg position.

             <------------------ Initial hole at “11” --------------->
 Move        Last  Peg       Last  Peg       Last  Peg       Last  Peg
Number         at  5           at 22           at 25           at 28
----------------------------------------------------------------------
   1          1 to 11         1 to 11         1 to 11          1 to 11
   2          3 to  5         3 to  5         3 to  5          3 to  5
   3          6 to  4         6 to  4         6 to  4          6 to  4
   4         16 to  3        16 to  3        16 to  3         16 to  3
   5          3 to  5         3 to  5        11 to  9          3 to  5
   6         11 to  9        11 to  9         0 to 10         11 to  9
   7          8 to 10         8 to 10         3 to 16          8 to 10
   8         13 to 11        13 to 11        19 to  6         13 to 11
   9         17 to  4        11 to  9         2 to 12         17 to  4
  10          0 to 10        22 to  8        21 to 19          0 to 10
  11         19 to 17        27 to 13        19 to  6         19 to 17
  12         17 to  4         7 to 20         7 to  5         17 to  4
  13          4 to  6        25 to 27        14 to 12          4 to  6
  14          2 to 12        23 to 25        25 to 11          2 to 12
  15         11 to 13        27 to 13        11 to  9         11 to 13
  16         14 to 12        14 to 12         8 to 10         21 to 19
  17         21 to 19        19 to  6        17 to  4          7 to 20
  18         29 to 16         2 to 12         4 to  6         20 to 18
  19         15 to 17        34 to 24         6 to 19         29 to 16
  20         25 to 23        36 to 26        15 to 17         15 to 17
  21         22 to 24        25 to 27        23 to 25         17 to 19
  22         27 to 25        28 to 26        34 to 24         25 to 23
  23         24 to 26        35 to 25        25 to 23         22 to 24
  24         34 to 24        25 to 27        22 to 24         27 to 25
  25         17 to 30        33 to 20        17 to 30         25 to 23
  26         35 to 25        21 to 19        27 to 25         34 to 24
  27         25 to 27        19 to  6        36 to 26         23 to 25
  28         28 to 26         6 to  4        25 to 27         36 to 26
  29         33 to 31         0 to 10        28 to 26         25 to 27
  30         19 to 32         9 to 11        19 to 32         28 to 26
  31         36 to 26        11 to 25        35 to 25         35 to 25
  32         30 to 32        25 to 23        29 to 31         25 to 27
  33         32 to 19        29 to 16        25 to 35         33 to 20
  34         19 to  6        17 to 15        33 to 31         19 to 21
  35          7 to  5         8 to 22        35 to 25         14 to 28

   If the initial hole is at position “18”, there are 16,662,591,542,028,595,169,821,912 possible game sequences. None of these will lead to a single peg solution.





   The theoretical maximum number of positions that could be encountered in any arbitrary game is limited by 2³⁷ = 137,438,953,472. A hole can be in any of 2 states (occupied or not occupied) and there are 37 holes.

   In practice, most of these potential positions can not be reached in any game. The following table gives the number of possible positions that could possibly be seen given the initial empty hole.

Initial                     Total Possible
Hole at:                       Positions
   0                         3,049,878,082
   1                         2,252,125,041
   3                         2,632,044,649
   4                         2,798,639,171
   5                         3,101,423,276
  10                         3,744,574,033
  11                         2,990,375,067
  18                         2,993,979,754

   For any initial hole, a detailed depth first search would have to keep interim data for each of the possible positions that might occur. (Each position is a “node” in the “search tree”) As seen above, this varies from 2 to 4 billion per initial hole. Interim data would include pattern recognition ability, number of games/wins in the subtree below the particular tree node, etc. This required 32GB of computer RAM.

   (Technically, you can exceed your physical RAM by using virtual memory, and even expand the default virtual memory via http://windows.microsoft.com/en-us/windows/change-virtual-memory-size#1TC=windows-7 ; but if virtual memory were used, it would entail a lot of disk thrashing and take a prohibitive amount of time since disk access is much slower than RAM access.)

  The following table shows the number of possible board positions after move "N' given that the initial hole is at “0”.

             Total    Nbr of Win   Nbr of Win   Nbr of Win   Nbr of Win
After       Possible   Positions    Positions    Positions    Positions
Move         Board      If Last      If Last      If Last      If Last
Number     Positions   Peg at  2    Peg at 16    Peg at 19    Peg at 36
-----------------------------------------------------------------------
   0              1            1            1            1            1
   1              2            2            2            2            2
   2              6            6            6            6            6
   3             32           32           32           32           32
   4            173          173          173          165          173
   5            919          891          893          763          887
   6          4,742        4,278        4,328        3,301        4,282
   7         22,820       18,344       18,682       12,960       18,348
   8        101,116       69,184       71,062       46,224       69,081
   9        410,035      229,351      238,392      149,651      229,432
  10      1,503,492      666,322      701,660      436,369      668,606
  11      4,924,564    1,695,989    1,811,269    1,135,069    1,710,876
  12     14,261,786    3,778,954    4,100,313    2,610,268    3,841,537
  13     36,137,026    7,370,035    8,130,846    5,292,996    7,558,666
  14     79,406,360   12,586,142   14,117,421    9,449,849   13,028,400
  15    150,455,758   18,814,061   21,442,245   14,815,779   19,640,992
  16    245,322,135   24,601,401   28,451,125   20,389,008   25,850,391
  17    344,874,094   28,136,229   32,972,663   24,620,881   29,670,290
  18    420,040,537   28,136,229   33,385,750   26,068,872   29,670,290
  19    445,790,702   24,601,401   29,555,976   24,221,997   25,850,391
  20    414,325,336   18,814,061   22,919,772   19,761,207   19,640,992
  21    338,416,017   12,586,142   15,595,022   14,157,476   13,028,400
  22    243,422,988    7,370,035    9,329,945    8,924,338    7,558,666
  23    154,300,131    3,778,954    4,916,338    4,957,116    3,841,537
  24     86,103,949    1,695,989    2,284,787    2,427,463    1,710,876
  25     42,214,067      666,322      938,059    1,049,825      668,606
  26     18,121,405      229,351      340,144      400,782      229,432
  27      6,765,112       69,184      108,900      135,055       69,081
  28      2,180,651       18,344       30,729       40,175       18,348
  29        601,443        4,278        7,597       10,419        4,282
  30        139,428          891        1,673        2,376          887
  31         26,591          173          340          492          173
  32          4,140           32           61           92           32
  33            484            6           12           17            6
  34             36            2            3            4            2
  35              4            1            1            1            1
Total 3,049,878,082

   The symmetry that can be seen in the number of positions for final peg in “2” and final peg in “36” is of interest. Any solution for the 37 hole Peg problem can always be run backwards to get a complementary solution. If the final “peg” position is merely a rotation or reflection of the initial hole position, then the forward and backward solutions will be similar for every solution.

   With this in mind, we note that the initial hole in “0” is a reflection (about the central axis) of the final hole at “2”. When the final peg is at “36”, it is merely a one half rotation of the initial hole at “0”.

   The last move for "Total Possible Board Positions" includes all 4 possible winning holes vs. a single designated winning hole.

   The table also shows that any combination of the first 3 moves can lead to a win. However, if you are trying to leave the final peg in hole 19, you can go off on the wrong track as early as the 4th move.

   For each of the above possible positions, the computer has to be able to recognize a board position, to try all 92 possible moves, to recognize new board positions as they are generated so cumulative totals can be kept (Any board position on round “N + 1” can be reached from several possible board positions that exists on round “N”), to keep the > 64-bit subtotals and totals that build up, etc. Would you like to guess why the computer needs 32GB of RAM for the program?

   As for recognizing board positions, the 37 holes were translated into binary “bit” positions. Bit “0” was used for hole “0”, bit ‘1” was used for hole “1’”, etc. (Which explains the “0” in the hole numbering system.)



  The following table shows the number of possible board positions after move "N' given that the initial hole is at “5”.

             Total    Nbr of Win   Nbr of Win   Nbr of Win   Nbr of Win
After       Possible   Positions    Positions    Positions    Positions
Move         Board      If Last      If Last      If Last      If Last
Number     Positions   Peg at  8    Peg at 11    Peg at 14    Peg at 31
-----------------------------------------------------------------------
   0              1            1            1            1            1
   1              3            3            3            3            3
   2             12           12           12           12           12
   3             61           61           61           61           61
   4            347          340          309          340          341
   5          1,768        1,673        1,407        1,673        1,688
   6          8,645        7,597        5,798        7,597        7,705
   7         39,477       30,729       22,087       30,729       31,262
   8        165,426      108,900       76,592      108,900      111,010
   9        630,538      340,144      238,889      340,144      348,300
  10      2,162,662      938,059      664,585      938,059      966,929
  11      6,609,159    2,284,787    1,645,237    2,284,787    2,377,098
  12     17,877,575    4,916,338    3,613,438    4,916,338    5,176,019
  13     42,547,680    9,329,945    7,030,983    9,329,945    9,949,906
  14     88,668,995   15,595,022   12,112,065   15,595,022   16,842,474
  15    161,273,164   22,919,772   18,425,565   22,919,772   25,057,062
  16    255,551,426   29,555,976   24,721,194   29,555,976   32,689,747
  17    352,676,758   33,385,750   29,223,604   33,385,750   37,350,761
  18    424,599,679   32,972,663   30,381,041   32,972,663   37,350,761
  19    447,384,729   28,451,125   27,768,319   28,451,125   32,689,747
  20    413,876,291   21,442,245   22,308,599   21,442,245   25,057,062
  21    337,004,173   14,117,421   15,746,852   14,117,421   16,842,474
  22    241,929,154    8,130,846    9,780,778    8,130,846    9,949,906
  23    153,211,874    4,100,313    5,352,369    4,100,313    5,176,019
  24     85,497,652    1,811,269    2,583,887    1,811,269    2,377,098
  25     41,958,995      701,660    1,103,093      701,660      966,929
  26     18,042,673      238,392      416,185      238,392      348,300
  27      6,750,362       71,062      138,692       71,062      111,010
  28      2,180,394       18,682       40,875       18,682       31,262
  29        602,480        4,328       10,516        4,328        7,705
  30        139,799          893        2,377          893        1,688
  31         26,648          173          491          173          341
  32          4,152           32           92           32           61
  33            484            6           17            6           12
  34             36            2            4            2            3
  35              4            1            1            1            1
Total 3,101,423,276

   Note, the results for the final peg at “8” and “14” are the same as one is a reflection of the other.



  The following table shows the number of possible board positions after move "N' given that the initial hole is at “11”.

             Total    Nbr of Win   Nbr of Win   Nbr of Win   Nbr of Win
After       Possible   Positions    Positions    Positions    Positions
Move         Board      If Last      If Last      If Last      If Last
Number     Positions   Peg at  5    Peg at 22    Peg at 25    Peg at 28
-----------------------------------------------------------------------
   0              1            1            1            1            1
   1              4            4            4            4            4
   2             17           17           17           17           17
   3             92           92           92           91           92
   4            495          491          492          450          492
   5          2,475        2,377        2,376        1,902        2,376
   6         11,771       10,516       10,419        7,189       10,419
   7         52,226       40,875       40,175       24,720       40,175
   8        212,527      138,692      135,055       77,746      135,055
   9        789,228      416,185      400,782      223,462      400,782
  10      2,640,323    1,103,093    1,049,825      582,635    1,049,825
  11      7,870,055    2,583,887    2,427,463    1,367,757    2,427,463
  12     20,730,606    5,352,369    4,957,116    2,864,456    4,957,116
  13     47,916,748    9,780,778    8,924,338    5,330,499    8,924,338
  14     96,715,832   15,746,852   14,157,476    8,797,592   14,157,476
  15    170,154,214   22,308,599   19,761,207   12,827,458   19,761,207
  16    260,956,703   27,768,319   24,221,997   16,500,751   24,221,997
  17    349,541,944   30,381,041   26,068,872   18,727,545   26,068,872
  18    410,294,786   29,223,604   24,620,881   18,727,545   24,620,881
  19    423,631,649   24,721,194   20,389,008   16,500,751   20,238,008
  20    385,887,175   18,425,565   14,815,779   12,827,458   14,815,779
  21    310,724,581   12,112,065    9,449,849    8,797,592    9,449,849
  22    221,398,196    7,030,983    5,292,996    5,330,499    5,292,996
  23    139,580,751    3,613,438    2,610,268    2,864,456    2,610,268
  24     77,748,102    1,645,237    1,135,069    1,367,757    1,135,069
  25     38,162,987      664,585      436,369      582,635      436,369
  26     16,445,627      238,889      149,651      223,462      149,651
  27      6,178,002       76,592       46,224       77,746       46,224
  28      2,007,607       22,087       12,960       24,720       12,960
  29        559,163        5,798        3,301        7,189        3,301
  30        131,269        1,407          763        1,902          763
  31         25,378          309          165          450          165
  32          4,012           59           32           91           32
  33            481           12            6           17            6
  34             36            3            2            4            2
  35              4            1            1            1            1
Total 2,990,375,067

   Note, the results for the final peg at “22” and “28” are the same as one is a reflection of the other.





   If you start with the empty hole at “0” or “11” (or any of the rotational and/or mirror reflections of this position), it is possible to hit a “dead end” (no more moves) in just 13 moves.

   If you start with the hole at “0”, there are 144,605 move sequences that hit a dead end after 13 moves. Here's one of these sequences:


Which produces the following pattern:



   If you start with the hole at “11”, there are 705,158 move sequences that hit a dead end after 13 moves. Here's one of these sequences:


Which produces the following pattern:






   All of the above results were obtained by exhaustive computer searches. There are two main algorithms involved – breadth first search and depth first search. Each has its own advantages and disadvantages.

  A depth first search is similar to the classic “mouse in a maze”.  In a simple maze, if you keep your right hand on the right wall (and continue to do so at all corners, intersections, etc.), and if the maze has only one entrance; you will eventually make a complete tour of the maze. A left hand rule will also work. A “simple” maze is a “tree” where there is exactly one path between any two points in the maze.

  If the maze is complex (has multiple paths between any two points – which allows the mouse to go in circles), if you drop “cookie crumbs” along your path, and if you backtrack whenever your search encounters some of the “cookie crumbs”; then either the right or left hand rule will again generate a complete maze tour. (The cookie crumbs are used as a memory/history system that says: "Been here before, done that, don't have to do it again.)

   A complete maze tour will find all solutions to the 37-hole peg problem. A simple maze tour (as described above) takes a minimal amount of computer memory. The bad news is that it takes a long time.

   For the 37-hole peg problem, we noted earlier that the “smallest” number of potential games exist if you start at position “1”. If your depth first search could process the 4,165,647,885,507,148,792,455,478 possible game sequences at the rate of 1,000,000,000 per second, then it would take about 132,000,000 years to discover that there are no solutions if the initial hole is at position “1”. If the initial hole were at “10”, it would take 7 times as long to discover that “10” doesn’t have any solutions either.

   The execution time for a depth first search can be significantly shortened (for a “complex” maze) if the computer program keeps track of “positions” as the search progresses. (For the 37-hole peg game, a “position” is any pattern of occupied vs. not occupied holes).

   Whenever the search encounters a pattern that has been seen before, the computer program can simply use the prior known results that were previously discovered starting at that position. The subtree search below the position (the “node”) does not have to be searched again. This produces a huge saving in search time. The trade-off is that you need a method for quickly finding your prior result. You also need lots of RAM as there are billions of these prior patterns.


   The second type of computer search is “breadth first”. In a “breadth first” search, instead of sending a single mouse into the maze, you send an army of mice. For the 37-hole peg game the required army was over 500,000,000 mice. (Which also translates into a lot of RAM for the computer program.)

   Initially, you send the army of mice into the maze entrance. Then everyone takes one step forward. The search consists of “one step at a time” sequences. Whenever there is an intersection in the maze, part of the army takes one branch while the rest of the army takes the other branch. Over a sequence of steps, the army will subdivide into smaller and smaller platoons. Any time a platoon (or single mouse) reaches a dead end, that particular platoon (or single mouse) is instantly transported to some other location where more mice are needed.

   The above approach will explore the whole maze in a relatively short period of time. For the 35 jumps in a game, it means “one step at a time” is repeated 35 times. As mentioned above, it requires a lot of computer RAM for the “breadth” of the army. In this particular case, the computer program required nearly 16GB of RAM. The good news is that this approach is significantly faster and needs less RAM than the depth first with history. The bad news is that even though total solutions are counted, a breadth first search doesn't remember how a solution was found. Thus it cannot output a single solution path. If you want to count positions that lead to a solution, or output the actual solution moves; you need depth first.

   We can trace the progress of a breadth first search by using the initial hole at position “0” example. Initially, there is only one position – there is a hole at position “0”. For the first “one step at a time”, we try all 92 potential moves that can be made on the board. Only two of these 92 can be used for “move 1” which leads to two possible board positions.

   For “move 2”, we try all possible 92 moves on each of the two board positions that are possible as a result of move 1. This produces 6 possible board configurations after 2 moves.

   For “move 3”, we try all possible 92 moves on each of the above 6 possible board configurations. This produces 32 possible board configurations.

   The process continues for the 35 potential moves. In the middle of the game the process produces hundreds of millions of possible board positions. As the process approaches the end of the game, the number of possible board configurations begins to decrease. At each step of the way, the computer program cumulates the number of ways to get to each board configuration. At the end of 35 moves, all that is left are the single peg solutions (if any).




For the history and solution analysis of Peg Solitaire (including 37-hole "French" Peg Solitaire) please see George Bell's web page at:
http://www.gibell.net/pegsolitaire/index.html



Also please see:
http://www.durangobill.com/Peg41.html for 41-hole peg solitaire analysis
and
http://www.durangobill.com/Peg33.html for 33-hole peg solitaire analysis
and
http://www.durangobill.com/PegSolitaire.html for 15-hole peg solitaire analysis



Return to Durango Bill's Home page


Web page generated via Sea Monkey's Composer HTML editor
within  a Linux Cinnamon Mint 18 operating system.
(Goodbye Microsoft)