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 possible unique
positions that are reachable in the standard game. (Start and finish at
the center hole. Up to 8 board positions can be reduced to a single
unique position via reflections/rotations.) Note the symmetry that
appears in the "Winning Positions" column.
Number
Number
Total Winning
Of Holes of
Moves Positions Positions
1
0
1
1
2
1
1
1
3
2
2
2
4
3
8
8
5
4
39 38
6
5
171 164
7
6
719 635
8
7
2,757 2,089
9
8
9,751 6,174
10
9
31,312 16,020
11
10
89,927 35,749
12
11
229,614 68,326
13
12
517,854 112,788
14
13
1,022,224 162,319
15
14
1,753,737 204,992
16
15
2,598,215 230,230
17
16
3,312,423 230,230
18
17
3,626,632 204,992
19
18
3,413,313 162,319
20
19
2,765,623 112,788
21
20
1,930,324 68,326
22
21
1,160,977 35,749
23
22
600,372 16,020
24
23
265,865 6,174
25
24
100,565 2,089
26
25
32,250 635
27
26
8,688 164
28
27
1,917
38
29
28
348
8
30
29
50
2
31
30
7
1
32
31
2
1
Totals
23,475,688 1,679,072
Interpretation:
The first line is the starting position for the game. There is only one
pattern (hole in the center) and at least one solution can be found
from this position.
After 2 moves there are 3 empty holes. There are two intrinsically
different patterns (allows for rotations/reflections), and a solution
can be reached from either position.
After 4 moves there are 39 possible game positions, but only 38 of
these can lead to a solution.
After 30 moves (two pegs left on the board) there are 7 possible
patterns, but only 1 of these leads to a solution.
Finally, if the game ends after 31 moves the peg must either be in the
center, or it must be in position 1 (or one of the three rotational
equivalents).
Number of possible
positions (But not adjusted for rotations/ reflections)
The number of different board positions can also be
calculated, with the data shown not adjusted for rotations/reflections.
In the table below note that the total possible board positions after
each possible jump/turn is nearly 8 times larger than the number shown
above. Also shown below is the total number of ways that you can reach
a dead end after “N” moves.
Number
Number
Total Number of
of Holes of
Moves Positions
“Deadends”
1
0
1
0
2
1
4
0
3
2
12
0
4
3
60
0
5
4
296
0
6
5
1,338
0
7
6
5,648
32
8
7
21,842
0
9
8
77,559
0
10
9
249,690
0
11
10
717,788 280
12
11
1,834,379 31,920
13
12
4,138,302
0
14
13
8,171,208 386,416
15
14 14,020,166
1.81681E+07
16
15 20,773,236
5.23638E+07
17
16 26,482,824
5.69426E+08
18
17 28,994,876
3.64088E+10
19
18 27,286,330
3.80028E+11
20
19 22,106,348
8.52066E+12
21
20 15,425,572
1.95539E+14
22
21 9,274,496
3.72085E+15
23
22 4,792,664
5.31076E+16
24
23 2,120,101
6.04666E+17
25
24
800,152 4.40707E+18
26
25
255,544 2.16258E+19
27
26
68,236 8.24755E+19
28
27
14,727 1.35522E+20
29
28
2,529 2.10994E+20
30
29
334 1.05088E+20
31
30
32 1.62608E+19
32
31
5 8.17233E+16 (Includes wins)
Totals
187,636,299 5.77116E+20
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, the number of ways to win, the number of
possible games, and other single peg solutions using the given start
hole. (Hole numbers use the 0 – 32 numbering system shown
earlier.)
Start/End
Total Board Nbr. of Ways
Total Game Single Peg
Hole
Positions to
Win Combinations
Solutions at
0
207,684,279 2.34365E+18
1.54738E+21 0,15,18,30
1
110,743,405 8.41595E+14
1.44279E+20 1,13,16,19,31
3
195,940,885 1.73855E+19
3.68658E+21 3,22,25
4
136,519,802 3.09973E+16
4.36756E+20 4,20,23,26
8
264,273,045 1.38410E+20
9.41405E+21 8,11,27
9
206,218,425 8.94099E+18
3.21491E+21 6,9,12,28
16
187,636,299 4.08616E+16
5.77116E+20 1,13,16,19,31
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
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
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 still take well
over 18,000 years to complete the search of the 577+ quintillion
possible games. Thus, we will look for a better algorithm.
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. Many of these combinations can not occur in
a real game. A further substantial reduction in the number of position
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. It turns out
that "only" 23,475,688 unique patterns are encountered (adjusted for
the 8 rotation/reflection variations).
Thus our computer program will modify the earlier "For each of
..." algorithm as follows:
Initially, start the brute force search using 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
// 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
The actual computer program (on a 1.4 GHz. Athlon with 256
MB of RAM) took 12 min. 23 sec. to complete. The history look-up system
used 20 bits of the "score" as a hash index into the history arrays.
Link lists were maintained for all records that shared the same 20 bit
pattern. Records were variable length (most patterns do not lead to
solutions and hence did not need extra space for this info.) and
averaged just over 2 unsigned long array entries per history record.
The first algorithm works for the center-hole solution,
but the rotations/reflections produce a problem when you try to solve
for other start/end holes. Thus we use the following algorithm that
avoids reflection/rotation problems. (It also requires 1 gigabyte of
RAM.)
Initialize the system with data for the game “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
Note: You are dealing with many large numbers. Watch for memory and
precision problems. The above algorithm can also be optimized.
Note about
Google’s/Yahoo’s search engines
For reasons unknown and for which Yahoo refuses to
disclose, this entire website has been banned/blacklisted from
Yahoo’s search engine. Other websites have suffered a similar
fate. If you are trying to find information via Google’s search
engine vs. Yahoo’s search engine, you should understand that
Yahoo’s results may not include the information that you are
seeking.
Return to Durango Bill's Home page
Web page generated via
KompoZer