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