Rules of the game: The 33-hole version of peg solitaire consists of 33 holes (see diagram below) and 32 pegs. To start the game, a player places the 32 pegs in the holes leaving the center hole empty. (The game may also be played by simply drawing the diagram on a piece of paper and then using any 32 markers as the pegs.) Then moves are made by taking any peg, jumping over another single peg and landing in an empty hole. Moves may be in any horizontal or vertical direction but must be in a straight line. Each jumped over peg is removed from the board.

As an example of a legal move, the starting position has a hole at position 16, and all other holes are filled. The 4 possible legal moves are: 4 over 9 to 16 (remove the peg at 9), 14 over 15 to 16 (remove the peg at 15), 18 over 17 to 16 (remove the peg at 17), or 28 over 23 to 16 (remove the peg at 23).

If a player can make 31 moves and leave the last peg in the center hole, the player wins.


               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

A few questions can be raised at this point:
How many different games are possible?
How many ways are there of winning?
What is the shortest (worst) possible game (no more legal moves)?
Can the game be won using some other hole as the starting and end point?

First, there are 577,116,156,815,309,849,672 different game sequences. That's:

   577 quintillion
   116 quadrillion
   156 trillion
   815 billion
   309 million
   849 thousand
   672
   possible game sequences of Hi-Q.

   If this number existed as U. S. dollars and be spread equally, then each of the world's nearly 7.5 billion people would be worth about 77 billion dollars.

From this total, the number of solutions is 40,861,647,040,079,968. (Most of these are rotations and reflections of unique solutions). If you want to express this as a number, it is:

     40 quadrillion
    861 trillion
    647 billion
     40 million
     79 thousand
   968

Sample solution:
Using the board notation given above, one way to solve the puzzle would be the following sequence:
4->16, 7->9, 0->8, 2->0, 9->7, 6->8, 10->2, 12->10, 15->3, 0->8, 13->15, 15->3, 17->5, 2->10, 19->17, 17->5, 27->15, 20->22, 22->8, 3->15, 15->17, 24->10, 5->17, 26->24, 23->25, 32->24, 17->29, 30->32, 32->24, 25->23, 28->16

Another solution is:
28->16, 9->23, 18->16, 16->28, 31->23, 29->17, 26->24, 17->29, 32->24, 12->26, 23->25, 26->24, 5->17, 24->10, 11->9, 21->23, 30->22, 23->21, 20->22, 15->27, 13->15, 8->22, 27->15, 0->8, 2->0, 15->3, 6->8, 9->7, 0->8, 7->9, 4->16

Shortest (Worst) Possible Game

It is possible to reach a dead end in just six moves using the following sequence:
4->16, 23->9, 14->16, 17->15, 19->17, 31->23

This leaves the following peg pattern:


             0  1  2
             3     5
       6  7  8  9 10 11 12
      13    15    17
      20 21 22 23 24 25 26
            27    29
            30    32




   The table below shows the number of positions that are reachable in the standard game. (Start and finish at the center hole.) The count includes all possible positions – many of which are a rotation and/or a reflection of single unique position. (Earlier versions of this web page just counted unique positions.)

Notes:
Total positions are those reachable by ordinary game moves.
Total Arbitrary Positions include all possible peg placements. Most of these positions are not reachable in a standard game. The number of Total Arbitrary Positions given “N” holes is equal to COMBIN(33,N).

 Nbr    Nbr                                  Total                  Number of ways
 of     of       Total      Winning        Arbitrary             to hit a dead end
Holes  Moves   Positions   Positions       Positions                  on this move
   1      0            1           1              33                             0
   2      1            4           4             528                             0
   3      2           12          12           5,456                             0
   4      3           60          60          40,920                             0
   5      4          296         292         237,336                             0
   6      5        1,338       1,292       1,107,568                             0
   7      6        5,648       5,012       4,272,048                            32
   8      7       21,842      16,628      13,884,156                             0
   9      8       77,559      49,236      38,567,100                             0
  10      9      249,690     127,964      92,561,040                             0
  11     10      717,788     285,740     193,536,720                           280
  12     11    1,834,379     546,308     354,817,320                        31,920
  13     12    4,138,302     902,056     573,166,440                             0
  14     13    8,171,208   1,298,248     818,809,200                       386,416
  15     14   14,020,166   1,639,652   1,037,158,320                    18,168,144
  16     15   20,773,236   1,841,556   1,166,803,110                    52,363,776
  17     16   26,482,824   1,841,556   1,166,803,110                   569,426,456
  18     17   28,994,876   1,639,652   1,037,158,320                36,408,754,040
  19     18   27,286,330   1,298,248     818,809,200               380,028,309,224
  20     19   22,106,348     902,056     573,166,440             8,520,659,218,816
  21     20   15,425,572     546,308     354,817,320           195,539,172,954,288
  22     21    9,274,496     285,740     193,536,720         3,720,848,140,835,952
  23     22    4,792,664     127,964      92,561,040        53,107,584,231,437,936
  24     23    2,120,101      49,236      38,567,100       604,666,435,961,470,144
  25     24      800,152      16,628      13,884,156     4,407,068,360,590,383,432
  26     25      255,544       5,012       4,272,048    21,625,765,333,357,588,280
  27     26       68,236       1,292       1,107,568    82,475,526,111,015,358,616
  28     27       14,727         292         237,336   135,521,776,905,015,042,336
  29     28        2,529          60          40,920   210,993,770,838,107,635,688
  30     29          334          12           5,456   105,088,038,911,515,040,128
  31     30           32           4             528    16,260,787,716,385,283,832
  32     31            5           1              33        81,723,294,080,159,936
Totals       187,636,299  13,428,122                   577,116,156,815,309,849,672

  Totals for move 31 consist of 40,861,647,040,079,968 ways to end in the center hole plus 4 times 10,215,411,760,019,992 for the other single-hole solutions.
     =  40,861,647,040,079,968 + 40,861,647,040,079,968  =  81,723,294,080,159,936


Interpretation:

The first line is the starting position for the game. There is only one pattern (hole in the center) and the solution can be found from this position.

After move number 1, there are 2 empty holes. There are 4 possible board patterns and the solution can be reached from all 4 of these. (All 4 of these possible board patterns are rotations of a single unique pattern.)

After 2 moves there are 3 empty holes. There are 12 possible board patterns and the solution can be reached from all 12 of these.

After 4 moves there are 296 possible board positions, but only 292 of these can lead to a solution.

After 30 moves (two pegs left on the board) there are 32 possible patterns, but only 4 of these lead to a solution.

Finally, if the game ends after 31 moves, the peg must either be in the center, or it must be in one of the 4 positions 1, 13, 19, 31.



   The game can also be played using other holes as a starting and finishing point. The table below shows the number of possible board combinations (includes the start position), the number of ways to win, and the number of possible games given the start hole. (Hole numbers use the 0 – 32 numbering system shown earlier.)

Start/End  Total Board           Nbr. of Ways                   Total Game
   Hole     Positions               to Win                     Combinations
    0      207,684,279    2,343,652,440,537,181,612   1,547,384,243,264,761,654,653
    1      110,743,405          841,594,661,434,808     144,279,039,203,827,462,418
    3      195,940,885   17,385,498,352,036,301,092   3,686,581,720,187,360,986,140
    4      136,519,802       30,997,283,487,697,056     436,756,431,197,750,501,664
    8      264,273,045  138,409,681,956,904,365,268   9,414,044,171,826,018,738,112
    9      206,218,425    8,940,989,276,947,390,168   3,214,909,287,232,785,028,120
   16      187,636,299       40,861,647,040,079,968     577,116,156,815,309,849,672

   The most difficult of the above variations is to start with a hole at position 1 and then leave the final peg at position 1. A possible solution is: 9->1, 23->9, 18->16, 5->17, 24->10, 26->24, 12->26, 16->4, 7->9, 0->8, 15->3, 31->23, 23->25, 26->24, 21->23, 23->25, 32->24, 30->22, 25->23, 23->21, 21->7, 6->8, 20->6, 9->7, 11->9, 6->8, 9->7, 2->0, 0->8, 7->9, 9->1

Here are solutions to all these alternate games including another solution to start/end at 1.

Move  Start/End  Start/End  Start/End  Start/End  Start/End  Start/End
 Nbr     at 0       at 1       at 3       at 4       at 8       at 9
  1     2 to  0    9 to  1    5 to  3   16 to  4    0 to  8    1 to  9
  2     9 to  1    7 to  9   16 to  4    1 to  9    2 to  0   16 to  4
  3     0 to  2    0 to  8    1 to  9   14 to 16    5 to  3    7 to  9
  4     7 to  9    2 to  0   14 to 16    3 to 15   16 to  4    0 to  8
  5    10 to  8    9 to  7    3 to 15    6 to  8    3 to  5    4 to 16
  6     2 to 10    6 to  8    6 to  8    9 to  7    7 to  9   11 to  9
  7    11 to  9   11 to  9    9 to  7   11 to  9   10 to  2    2 to 10
  8     8 to 10    9 to  7   17 to  5    2 to 10   12 to 10    9 to  7
  9    17 to  5   20 to  6    2 to 10    9 to 11    9 to 11    6 to  8
 10    15 to 17    6 to  8   15 to 17   12 to 10   21 to  7   15 to  3
 11    13 to 15   15 to  3   17 to  5   16 to 14    6 to  8   13 to 15
 12    22 to  8    0 to  8   12 to 10   13 to 15   15 to  3   17 to  5
 13    20 to 22   21 to  7    5 to 17   17 to  5    0 to  8   22 to  8
 14    23 to 21    7 to  9   20 to  6   19 to 17   20 to  6    3 to 15
 15    24 to 10   16 to  4    6 to  8   22 to  8   23 to 21   15 to 17
 16     5 to 17   23 to 21   27 to 15   20 to 22   24 to 10   20 to 22
 17    18 to 16   24 to 10   15 to  3   24 to 10   19 to 17   23 to 21
 18    26 to 24    5 to 17    0 to  8    5 to 17   26 to 24   24 to 10
 19    12 to 26   18 to 16   24 to 22   26 to 24   30 to 22    5 to 17
 20    30 to 22   26 to 24   21 to 23   23 to 25   21 to 23   18 to 16
 21    21 to 23   12 to 26   26 to 24   27 to 15   24 to 22   26 to 24
 22    23 to 25   30 to 22   23 to 25   15 to  3   31 to 23   12 to 26
 23    26 to 24   21 to 23   32 to 24    0 to  8   32 to 24   30 to 22
 24    31 to 23   23 to 25   17 to 29    7 to  9   17 to 29   21 to 23
 25    23 to 25   26 to 24   19 to 17   32 to 24   22 to 24   23 to 25
 26    32 to 24   31 to 23   30 to 32   17 to 29   29 to 17   26 to 24
 27    25 to 23   23 to 25   32 to 24   30 to 32   17 to  5   31 to 23
 28    23 to  9   32 to 24   25 to 23   32 to 24    2 to 10   23 to 25
 29     9 to  7   25 to 23   28 to 16   25 to 23   11 to  9   32 to 24
 30     6 to  8   23 to  9   17 to 15   28 to 16    9 to  7   25 to 23
 31     8 to  0    9 to  1   15 to  3   16 to  4    6 to  8   23 to  9



   Still another variation of the game is to leave 4 pegs in the corners of the square surrounding the center (i.e. in positions 8, 10, 22, and 24). A sample solution is: 4->16, 7->9, 0->8, 2->0, 9->7, 6->8, 10->2, 12->10, 15->3, 0->8, 13->15, 15->3, 17->5, 2->10, 19->17, 17->15, 22->8, 3->15, 20->22, 22->8, 24->22, 26->24, 27->15, 29->27, 30->22, 15->27, 32->30, 30->22
The number of ways to solve this variation is: 4,540,128,887,763,134,208

          or

      4  quintillion
   540  quadrillion
   128  trillion
   887  billion
   763  million
   134  thousand
   208
   


The following table shows all possible single peg ending holes for possible starting holes.

Initial Empty     All Possible Single
    Hole           Peg Ending Holes
      0             0, 15, 18, 30
      1             1, 13, 16, 19, 31
      2             2, 14, 17, 32
      3             3, 22, 25
      4             4, 20, 23, 26
      5             5, 21, 24
      6             6, 9, 12, 28
      7             7, 10, 29
      8             8, 11, 27
      9             6, 9, 12, 28
     10             7, 10, 29
     11             8, 11, 27
     12             6, 9, 12, 28
     13             1, 13, 16, 19, 31
     14             2, 14, 17, 32
     15             0, 15, 18, 30
     16             1, 13, 16, 19, 31
     17             2, 14, 17, 32
     18             0, 15, 18, 30
     19             1, 13, 16, 19, 31
     20             4, 20, 23, 26
     21             5, 21, 24
     22             3, 22, 25
     23             4, 20, 23, 26
     24             5, 21, 24
     25             3, 22, 25
     26             4, 20, 23, 26
     27             8, 11, 27
     28             6, 9, 12, 28
     29             7, 10, 29
     30             0, 15, 18, 30
     31             1, 13, 16, 19, 31
     32             2, 14, 17, 32






A possible algorithm to count the number of solutions could be:

For each of the possible first moves (There are four as noted above)
   For each of these four possible moves try all possible second moves.
      For each of these second moves, try all possible third moves.
         Etc. for all possible moves through 31 turns.

   If you wrote a computer program using this simple algorithm and had a super computer that could generate and process 1 billion of these potential games per second, it would take over 18,000 years to complete the search of the 577+ quintillion possible games. Thus, we will look for a better algorithm.

   There are two standard algorithms that a computer program might use to find and count solutions to the peg problem. One algorithm would be a “depth first” search http://en.wikipedia.org/wiki/Depth-first_search while another algorithm would be a “breadth first” search. http://en.wikipedia.org/wiki/Breadth-first_search 


   The algorithm that we gave above is a “depth first” search as it will try to search (make trial moves) as deeply as possible, and backs up only when it hits a dead end. As noted earlier, a pure “depth first” search would take many thousands of years.

   The depth first search can be modified to run much faster. We note that the peg solitaire board has 33 holes. Each hole can either be empty or it can contain a peg. Thus there is a maximum of 2^33 = 8,589,934,592 combinations of holes that may or may not have a peg in them. Most of these combinations can not occur in a standard game. (If you are just solving for total game positions, a further substantial reduction in the number of combinations could be realized if you adjust for rotations and reflections. However, there is a lot of overhead involved, and the bottom line is that this memory reduction isn't worth the trouble.)

   Thus we will design a computer program that keeps track of the number of solutions that are possible as it searches from each possible position. When a subsequent set of moves reaches and recognizes one of these positions, it can merely add the number of solutions found earlier without having to retrace the same search pattern. If you are solving for total possible games for the start at hole 16 and end at hole 16 standard game, it turns out that "only" 187,636,299 possible game patterns could be encountered.

    Thus our computer program will modify the earlier "For each of ..."  algorithm as follows: A stack is used to keep track of where the search is, how many solutions have been found, what trial move to try next, etc.

    Initially, start the brute force search using the equivalent of the nested "For each of ..." loops. Data for the current position in the search tree is kept in a stack. As each minor subtree search is completed, a record is saved in the history array. Each of these records contains information on how many solutions were found, plus a look-up system that can identify the particular board position and a method to rapidly find these results when needed at some future time in the search pattern.

The outline for the algorithm then becomes:

do {                                         //  Repeat loop until all possible combinations have been processed
                                             //  There are 76 potential moves for various peg patterns.
  Get next trial move                        //  Try the next one of these for the current "For each of ..." level
  If a potential move is found {             //  If one of these is a current legal move...
    Convert this position to a number        //  Each of the board's 33 positions is either occupied or empty. This
                                             //  converts to a "1" or "0". The status of the board thus becomes a 33 bit
                                             //  binary number. In turn 25 of these bits are used as a hash index
                                             //  into the history records.
    Look this position up in the history records
    If found, then add the prior number of solutions to the current running total (in the stack)
                      and continue at the top of the "do" loop
    Else a new pattern has been found in the search sequence. Increment the stack pointer
                      (move down one level in the "For each of ..." sequence)
  }                                          //  End of  "If a potential move is found" sequence. Return
                                             //  to the top of the  "do {"  loop to continue the search.
  Else {                                     //  Else s potential move was not found. Reached the end of move
                                             //  combinations. The subtree search at this level is complete.
    Add to history data                      //  Create a new record for this game position in the history array.
                                             //  If this position is seen again at some future point in the
                                             //  search sequence, the relevant data is available and the
                                             //  subtree sequence does not have to be searched again.
    Restore the former board pattern
    Move up one level in the stack
 }                                           //  End of else not found sequence
}  while more stack levels                   //  Repeat the "do" loop until the search is complete
Output the number of solutions               //  Report the result before ending the program


   Execution time on an Intel i7-6700K running Linux Mint 18 (GNU GCC compiler - optimization set to -O2) was about 190 seconds to count all 40+ quadrillion solutions. (See code listing below) The algorithm can use any of the 33 holes as a start hole, and then try to find solutions by ending at any arbitrary finish hole.



   A few paragraphs ago, we mentioned that the peg problem can also be solved by a “breadth first” search. In a breadth first search we start with all known positions after “N” moves, and then find all possible positions for the “N+1” move. Initially there is only one board position. (Empty space at the start position.)

   For the standard game, initially there is only one position (The “old” position). If we try all possible valid moves, the algorithm finds 4 possible “new” positions at the end of round 1. These 4 new positions are then relabeled as “old” positions, and all possible moves are tried using these “old” positions to see how many “new” positions can be found for the end of round 2. The computer also keeps track how how many combinations are found

   The processes is continued for the 31 possible rounds of play. On the 31st move the algorithm finds all possible finishing holes. If one of these is the solution location, the “remembered” number of combinations becomes the number of ways to win.

Thus our computer algorithm for a breadth first becomes:

Initialize the system with data for the game’s “Start position” in the “New” arrays.

For 31 rounds of possible jumps
   Copy the board position data from the “new” arrays to the “old” arrays
   For each of the "old" positions (typically there are tens of millions of them)
      Try all possible next moves (There are 76 possible moves subject to peg positions.)
      Each time a move can be made, update the position data in the “new” arrays.
   Repeat for all old records/positions.
Repeat for all 31 rounds of possible jumps

   The good news for breadth first search is that given any staring hole, the algorithm simultaneously counts the total number of possible games and the number of winning games for all possible solution holes. The bad news is that a breadth first search doesn't remember how you got to any of these solutions.

   Execution time on an Intel i7-6700K running Linux Mint 18 (GNU GCC compiler - optimization set to -O2) was 233 seconds to count all 40+ quadrillion solutions and the 577 quintillion possible game sequences. (See code listing below) The algorithm can use any of the 33 holes as a start hole

  

Notes: For both algorithm, you are dealing with many very large numbers. The computer program must allocate sufficient RAM memory and devise its own way of doing arithmetic with numbers that exceed 64 bits.




   Two different computer programs (using different algorithms) were used to calculate the results shown on this web page. Both programs came up with the same number of wins and same number of total possible games. (This is always comforting.) However, each program could supply a little additional information that the other couldn’t.

    The depth first with memory program used a modified tree search  with interim results kept on a stack. The standard tree search was modified so that the program could recognize positions that had been visited before. The source code for the current version of this “depth first” search program can be seen here.
http://www.durangobill.com/Peg33SourceCode.txt

  The second program used a standard “breadth first” algorithm. This second program can be seen here.
http://www.durangobill.com/Peg33BreadthSearch.html

   You can watch this “breadth first” program in action here:
https://www.youtube.com/watch?v=XgbTHPPI-W8&feature=youtu.be
The program takes less than 4 minutes to find/count ALL games & solutions to the standard problem.




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)