The 41-hole (40 peg) version of peg solitaire is no where near as popular as the 15, 33, and 37 hole versions, but it is interesting computer problem since peg solitaire complexity approximately doubles for every peg that is added to the game. A computer analysis of the 41-hole variation requires 128 GB of RAM memory, and that is after efficient storage of the data involved. The results of computer program analysis for the 41-hole 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
                                37 38 39
                                   40

   Initially, a player places 40 pegs in a board that has 41 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:

                                    P
                                 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  P  P
                                    P

   In the above diagram, the 40 pegs have been placed in holes 0, 2 – 40 while hole “1” 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 “3” can jump over the peg at “2” and land in position “1”. The jumped over peg at “2” is removed.
     or
2) The peg at “11” can jump over the peg at “5” and land in position “1”. The jumped over peg at “5” is removed.

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

                                    P
                                 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  P  P
                                    P

  For the next possible move, the peg at “12” (or the peg at“13”) could jump up to the empty space at “2” (or “3”). The object of the game is to make a total of 39 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 “1” it is possible to leave a single peg at position “3” or at position “18” after a total of 39 moves. In fact there are 300,957,589,551,875,598,436 game sequences that will leave a single peg at position “3”. 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 3,300,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  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  O  O
                                    O

   The bad news is that there are more than 1,600,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 12 of the 41 possible initial positions 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.

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

   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. If you start with the initial open hole at “1”, it is possible to end with a single peg at position 3 or position 18. If you start with the initial open hole at “6”, it is possible to end with a single peg at either position 9, 15, or 34. There is no way to leave a single peg at any initial start hole. (Use reflections and or rotations to solve for the other “W” initial holes.)



   For the results below, we will examine what happens if the initial hole is in positions 0, 1, 2, 4, 5, 6, 11, 12, and 20. 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
                                37 38 39
                                   40

   If the initial hole is at position “0”, there are 62,933,236,442,662,739,091,668,888 possible game sequences. None of these will lead to a single peg solution.

   If the initial hole is at position “1”, there are 486,807,777,048,720,709,128,907,245 possible game sequences. A winning sequence will leave a single peg in position 3 or 18. (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:  486,807,777,048,720,709,128,907,245
Final peg at “3”:              300,957,589,551,875,598,436 ways to win
Final peg at “18”:             432,196,735,777,422,403,975 ways to win

No solutions for any other final peg position.

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

      It should be remembered that the above solution sequences are a result of computer searches. Search algorithms have a defined search sequence. For the above solutions, the search sequence for each move/round will favor moves that use low numbered pegs.


   If the initial hole is at position “2”, there are 487,195,565,098,594,440,432,285,556 possible game sequences. None of these will lead to a single peg solution.

   If the initial hole is at position “4”, there are 533,228,978,299,382,247,075,241,858 possible game sequences. None of these will lead to a single peg solution.

   If the initial hole is at position “5”, there are 767,645,130,872,338,358,597,209,194 possible game sequences. None of these will lead to a single peg solution.

   If the initial hole is at position “6”, there are 1,077,593,175,825,139,048,472,127,936 possible game sequences. A winning sequence will leave a single peg in position 9, 15, or 34. (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: 1,077,593,175,825,139,048,472,127,936
Final peg at “9”:               432,196,735,777,422,403,975 ways to win
Final peg at “15”:              432,196,735,777,422,403,975 ways to win
Final peg at “34”:            2,212,487,273,101,839,099,948 ways to win

No solutions for any other final peg position.

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


   In the above solutions, note that an alternate last 3 moves for the single peg at 15 will leave the last peg at 34.

   If the initial hole is at position “11”, there are 1,709,645,137,625,890,434,697,658,372 possible game sequences. None of these will lead to a single peg solution.

   If the initial hole is at position “12”, there are 979,317,477,406,419,751,349,922,520 possible game sequences. None of these will lead to a single peg solution.


   If the initial hole is at position “20”, there are 1,948,782,260,394,377,761,729,142,224 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⁴¹ = 2,199,023,255,552. A hole can be in any of 2 states (occupied or not occupied) and there are 41 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               Total Possible
Hole at:         Positions                     Games
   0          13,975,565,325      62,933,236,442,662,739,091,668,888
   1          23,055,659,092     486,807,777,048,720,709,128,907,245
   2          17,762,974,938     487,195,565,098,594,440,432,285,556
   4          21,897,781,775     533,228,978,299,382,247,075,241,858
   5          20,181,660,511     767,645,130,872,338,358,597,209,194
   6          26,521,227,887   1,077,593,175,825,139,048,472,127,936
  11          28,351,107,848   1,709,645,137,625,890,434,697,658,372
  12          21,562,385,456     979,317,477,406,419,751,349,922,520
  20          25,210,747,608   1,948,782,260,394,377,761,729,142,224

   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 13 to 29 billion per initial hole. Interim data would include pattern recognition ability, number of games/wins, etc. in the subtree below the particular tree node, etc. A complete tabulation would require well in excess of 128 GB of computer RAM.




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

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

Which produces the following pattern:



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


Which produces the following pattern:


   If you start with the hole at “12”, there are 512 move sequences that hit a dead end after 10 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 41-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 41-hole peg problem, we noted earlier that the “smallest” number of potential games exist if you start at position “0”. If your depth first search could process the 62,933,236,442,662,739,091,668,888 possible game sequences at the rate of 1,000,000,000 per second, then it would take nearly 2 billion years to discover that there are no solutions if the initial hole is at position “0”. If the initial hole were at “20”, it would take more than 30 times as long to discover that “20” 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 41-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 41-hole peg game the required army was over 5,000,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 39 jumps in a game, it means “one step at a time” is repeated 39 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 128GB 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 “2” example. Initially, there is only one position – there is a hole at position “2”. For the first “one step at a time”, we try all 100 potential moves that can be made on the board. Only one of these 100 can be used for “move 1” which leads to just one possible board position.

   For “move 2”, we try all possible 100 moves on the single board position that resulted from move 1. This produces 6 possible board configurations after 2 moves.

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

   The process continues for the 39 potential moves. In the middle of the game the process produces billions 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 39 moves, all that is left are the single peg solutions (if any).




For the history and solution analysis of various Peg Solitaire games, please see George Bell's web page at:
http://www.gibell.net/pegsolitaire/index.html



Also please see:
http://www.durangobill.com/Peg37.html for 37-hole peg solitaire analysis
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)