33 Hole Peg Solitaire (2024)

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

Number of Possible Positions

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

NbrNbr 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 133 0
2 1 4 4528 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 125,456 105,088,038,911,515,040,128
31 30 32 4528 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 +

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.

Alternate Games

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/EndTotalBoardNbr. of WaysTotal 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.

MoveStart/End Start/End Start/End Start/End Start/End Start/End
Nbrat 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
1015 to 17 6 to 8 15 to 17 12 to 10 21 to 7 15 to 3
1113 to 15 15 to 3 17 to 5 16 to 14 6 to 8 13 to 15
1222 to 8 0 to 8 12 to 10 13 to 15 15 to 3 17 to 5
1320 to 22 21 to 7 5 to 17 17 to 5 0 to 8 22 to 8
1423 to 21 7 to 9 20 to 6 19 to 17 20 to 6 3 to 15
1524 to 10 16 to 4 6 to 8 22 to 8 23 to 21 15 to 17
165 to 17 23 to 21 27 to 15 20 to 22 24 to 10 20 to 22
1718 to 16 24 to 10 15 to 3 24 to 10 19 to 17 23 to 21
1826 to 24 5 to 17 0 to 8 5 to 17 26 to 24 24 to 10
1912 to 26 18 to 16 24 to 22 26 to 24 30 to 22 5 to 17
2030 to 22 26 to 24 21 to 23 23 to 25 21 to 23 18 to 16
2121 to 23 12 to 26 26 to 24 27 to 15 24 to 22 26 to 24
2223 to 25 30 to 22 23 to 25 15 to 3 31 to 23 12 to 26
2326 to 24 21 to 23 32 to 24 0 to 8 32 to 24 30 to 22
2431 to 23 23 to 25 17 to 29 7 to 9 17 to 29 21 to 23
2523 to 25 26 to 24 19 to 17 32 to 24 22 to 24 23 to 25
2632 to 24 31 to 23 30 to 32 17 to 29 29 to 17 26 to 24
2725 to 23 23 to 25 32 to 24 30 to 32 17 to 5 31 to 23
2823 to 9 32 to 24 25 to 23 32 to 24 2 to 10 23 to 25
299 to 7 25 to 23 28 to 16 25 to 23 11 to 9 32 to 24
306 to 8 23 to 9 17 to 15 28 to 16 9 to 7 25 to 23
318 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

All Possible Winning Combinations

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

InitialEmpty All Possible Single
Hole Peg Ending Holes
00, 15, 18, 30
11, 13, 16, 19, 31
22, 14, 17, 32
33, 22, 25
44, 20, 23, 26
55, 21, 24
66, 9, 12, 28
77, 10, 29
88, 11, 27
96, 9, 12, 28
107, 10, 29
118, 11, 27
126, 9, 12, 28
131, 13, 16, 19, 31
142, 14, 17, 32
150, 15, 18, 30
161, 13, 16, 19, 31
172, 14, 17, 32
180, 15, 18, 30
191, 13, 16, 19, 31
204, 20, 23, 26
215, 21, 24
223, 22, 25
234, 20, 23, 26
245, 21, 24
253, 22, 25
264, 20, 23, 26
278, 11, 27
286, 9, 12, 28
297, 10, 29
300, 15, 18, 30
311, 13, 16, 19, 31
322, 14, 17, 32

How to calculate the number of winning solutions.

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

Depth first search with memory

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.

Breadth first search

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.

The Computer Programs

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)