Durango Bill's

33 Hole Peg Solitaire

(Sold commercially as Hi-Q)

How many ways (number of solutions) are there to win the

33 hole (32 pegs) version of Peg Solitaire?

(Click here for 15-hole Peg Solitaire)

(Click here for 37-hole Peg Solitaire)

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.

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 is realized when you adjust for rotations and reflections.)

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 16/16 standard game, it turns out that "only" 23,475,688 unique patterns are encountered (adjusted for the 8 rotation/reflection variations). Even if you ignore rotations/reflections, the standard game only has 187,636,299 possible board patterns.

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

Calculate the position's score // If applicable, try all possible rotations/reflections of the

// new pattern.

// Express each of these as a binary number (Use board number

// pattern for bit positions). The lowest of these is the "score"

// which will be used for pattern recognition.

Look this position ("score") 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 { // A 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 arrays.

// 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 modern multicore processors is typically just a few minutes. The algorithm can be modified to use any of the 33 holes as a start hole, and then try to find solutions by ending at any arbitrary finish hole. If you are just solving for total possible games, the program takes full advantage of symetry. (Rotations and reflections produce 8 variations of a unique position)

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

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

Note: You are dealing with many large numbers. Watch for memory and precision problems. The above algorithm can also be optimized.

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 first program used a modified tree search (depth first) 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.html

The second program used a standard “breadth first” algorithm. This second program can be seen here.

http://www.durangobill.com/Peg33BreadthSearch.html

Return to Durango Bill's Home page

Web page generated via KompoZer

33 Hole Peg Solitaire

(Sold commercially as Hi-Q)

How many ways (number of solutions) are there to win the

33 hole (32 pegs) version of Peg Solitaire?

(Click here for 15-hole Peg Solitaire)

(Click here for 37-hole Peg Solitaire)

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.

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

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.

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

All Possible Winning Combinations

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

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 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 is realized when you adjust for rotations and reflections.)

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 16/16 standard game, it turns out that "only" 23,475,688 unique patterns are encountered (adjusted for the 8 rotation/reflection variations). Even if you ignore rotations/reflections, the standard game only has 187,636,299 possible board patterns.

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

Calculate the position's score // If applicable, try all possible rotations/reflections of the

// new pattern.

// Express each of these as a binary number (Use board number

// pattern for bit positions). The lowest of these is the "score"

// which will be used for pattern recognition.

Look this position ("score") 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 { // A 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 arrays.

// 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 modern multicore processors is typically just a few minutes. The algorithm can be modified to use any of the 33 holes as a start hole, and then try to find solutions by ending at any arbitrary finish hole. If you are just solving for total possible games, the program takes full advantage of symetry. (Rotations and reflections produce 8 variations of a unique position)

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

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

Note: You are dealing with many large numbers. Watch for memory and precision problems. The above algorithm can also be optimized.

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 first program used a modified tree search (depth first) 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.html

The second program used a standard “breadth first” algorithm. This second program can be seen here.

http://www.durangobill.com/Peg33BreadthSearch.html

Return to Durango Bill's Home page

Web page generated via KompoZer