Durango Bill's
Solitaire Chinese Checkers
What is the minimum number of moves needed to move a set of marbles
from one side of a Chinese Checkers board to the other side?
Normally, Chinese
Checkers is a game for 2 or more people. However, if we limit
the game to just one person, it becomes an interesting puzzle
in trying to find the minimum number of moves needed to move a
set of marbles (markers) from one side of the board to the
other.
First, we will show the starting board position, and define the grid system that we will use for nomenclature. The "M's" identify the holes that are initially filled with the set of 10 marbles and the "O's" identify empty holes.
Legal moves
A marble may move a single space in any of 6 possible directions - along an up diagonal, a down diagonal, or vertically as long as the "move to" space is empty.
or
A marble may jump over another single marble to an empty space in any of the 6 directions provided the "Jump to" space is empty. These jumps may be chained (multiple jumps) within a single turn. The object is to move the set of marbles from the left hand triangle to the extreme right hand triangle in a minimum number of moves.
Minimum Number of Moves
There are many ways the 10 marbles can be moved from the left hand triangle to the right triangle in 27 moves. It appears the 27-move solutions are minimal. (The computer search did not explicitly eliminate a 26-move solution, but given the breadth of the search, a 26-move solution appears EXTREMELY unlikely.)
The following table shows 5 solutions. They are characterized by having different board positions at the end of move number 13. Typically each solution has several variations in the move sequence to get to the "move-13 pattern" followed by several other variations for the final 14 moves. Thus, the total number of solutions is significantly higher.
Moves are defined by moving the marble at "Up diagonal, Down diagonal" to "Up diagonal, Down diagonal" using the grid coordinates shown in the above diagram. If a chain of jumps is involved, only the start and ending position is given.
Notes: Single space moves include both up and down vertical directions. Some chain jumps stop short of the maximal potential chain length.
Move <- "Up diag.,Down diag." to "Up diag.,Down diag." ->
Number Sol. # 1 Sol. # 2 Sol. # 3 Sol. # 4 Sol. # 5
-------------------------------------------------------------------
1 4,1 to 4,2 3,2 to 4,2 4,1 to 4,2 4,1 to 4,2 4,1 to 4,2
2 2,1 to 4,3 1,4 to 5,2 2,1 to 4,3 2,1 to 4,3 2,1 to 4,3
3 3,1 to 5,3 3,1 to 5,3 3,1 to 5,3 3,1 to 5,3 3,1 to 5,3
4 5,3 to 6,3 5,3 to 5,4 5,3 to 6,3 5,3 to 6,3 5,3 to 6,3
5 1,3 to 7,3 1,1 to 5,5 1,3 to 7,3 1,3 to 7,3 1,3 to 7,3
6 1,1 to 5,3 1,3 to 5,3 1,1 to 5,3 1,1 to 5,3 1,1 to 5,3
7 3,2 to 7,4 4,1 to 6,5 3,2 to 7,4 3,2 to 7,4 3,2 to 7,4
8 7,4 to 7,5 6,5 to 7,5 7,4 to 7,5 7,4 to 7,5 7,4 to 7,5
9 4,2 to 3,3 1,2 to 3,2 1,2 to 7,6 1,4 to 7,6 1,4 to 7,6
10 1,4 to 7,6 2,3 to 8,5 1,4 to 7,4 7,6 to 7,7 7,6 to 7,7
11 1,2 to 7,4 2,1 to 6,5 2,3 to 3,2 1,2 to 7,8 1,2 to 7,8
12 2,2 to 8,6 4,2 to 8,6 4,2 to 8,6 2,2 to 3,2 2,3 to 3,2
13 6,3 to 8,7 8,6 to 8,7 8,6 to 8,7 3,2 to 7,6 3,2 to 7,6
14 8,7 to 7,8 2,2 to 8,8 2,2 to 8,8 2,3 to 3,2 2,2 to 3,2
15 4,3 to 8,7 3,2 to 4,2 3,2 to 4,2 3,2 to 7,4 3,2 to 7,4
16 8,7 to 8,8 4,2 to 8,6 4,2 to 8,6 4,2 to 8,8 4,2 to 8,8
17 2,3 to 8,9 5,4 to 9,8 8,7 to 7,8 6,3 to 8,9 6,3 to 8,9
18 3,3 to 4,3 5,2 to 7,8 6,3 to 6,9 4,3 to 6,9 4,3 to 6,9
19 4,3 to 6,9 8,7 to 8,9 4,3 to 8,9 7,7 to 8,6 7,7 to 8,6
20 5,3 to 6,3 5,3 to 5,4 5,3 to 6,3 5,3 to 6,3 5,3 to 6,3
21 6,3 to 8,7 5,4 to 9,6 6,3 to 8,7 6,3 to 8,7 6,3 to 8,7
22 7,5 to 9,9 7,5 to 7,9 7,5 to 9,9 7,5 to 9,9 7,5 to 9,9
23 7,3 to 7,9 5,5 to 9,9 7,3 to 7,9 7,3 to 7,9 7,3 to 7,9
24 7,4 to 7,5 6,5 to 7,5 7,4 to 7,5 7,4 to 7,5 7,4 to 7,5
25 7,5 to 9,7 7,5 to 9,7 7,5 to 9,7 7,5 to 9,7 7,5 to 9,7
26 7,6 to 9,8 8,5 to 6,9 7,6 to 9,8 7,6 to 9,8 7,6 to 9,8
27 8,6 to 9,6 8,6 to 8,7 8,6 to 9,6 8,6 to 9,6 8,6 to 9,6
Solution Notes
The above 5 solutions are characterized by having different board positions after 13 moves. These are the only solutions (as defined by unique board positions after 13 moves) found by the computer program. (The computer program found the above 5 solutions by the time the “breadth” search used the best 200,000 positions on each iteration. A further increase in the size of the “breadth” to 17,000,000 positions did not produce any additional solutions.) While other 27-move solutions might exist, this is considered most unlikely. (Note: there are mirror images of the above sequences, but these are not considered as "different".) Also, a 26-move solution is considered extremely unlikely.
Solutions 4 and 5 are very similar, but the choice of moves at move number 12 produces a slight variation in the move 13 position. Hence, they technically qualify as being different. Solutions 2 and 3 are both symmetrical as the final 13 moves of each are mirror images of the first 13 moves.
Computer Algorithm
The computer program used a 17,000,000 position wide "breadth first" search out of all possible board positions (mirror images were eliminated). With a “breadth width” of 17,000,000, you could waste the first 8 moves (return to the original start position) and this original start position would still be included in the search patterns.
In designing the algorithm, we note that the final position (triangle on the right hand side of the board) forms a mirror image of the start position. i.e. An efficient way of starting a solution must be followed by an efficient way of finishing a solution. Thus, the logic of the program takes advantage of the fact that the final 13 moves of a solution would have to be a mirror image match of one of the other first 13-move positions (26-move solution), or would have to match one of the 14-move positions (27-move solution).
The algorithm used looks like:
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)
First, we will show the starting board position, and define the grid system that we will use for nomenclature. The "M's" identify the holes that are initially filled with the set of 10 marbles and the "O's" identify empty holes.
Down diag. 9 ->
O
O
<- Up diag. 1
O O
Down diag. 8 -> O O O O <- Up diag. 2
O O O O
Down diag. 7 -> O O O O O <- Up diag. 3
O O O O
Down diag. 6 -> O O O O O <- Up diag. 4
O O O O
Down diag. 5 -> O O O O O <- Up diag. 5
M O O O O O
M O O O O O O
M M O O O O O O
M M O O O O O O O
M M O O O O O O
M O O O O O O
M O O O O O
Up diag. 5 -> O O O O O <- Down diag. 5
O O O O
Up diag. 6 -> O O O O O <- Down diag. 4
O O O O
Up diag. 7 -> O O O O O <- Down diag. 3
O O O O
Up diag. 8 -> O O O O <- Down diag. 2
O O
Up diag. 9 -> O O <- Down diag. 1
O O
Down diag. 8 -> O O O O <- Up diag. 2
O O O O
Down diag. 7 -> O O O O O <- Up diag. 3
O O O O
Down diag. 6 -> O O O O O <- Up diag. 4
O O O O
Down diag. 5 -> O O O O O <- Up diag. 5
M O O O O O
M O O O O O O
M M O O O O O O
M M O O O O O O O
M M O O O O O O
M O O O O O O
M O O O O O
Up diag. 5 -> O O O O O <- Down diag. 5
O O O O
Up diag. 6 -> O O O O O <- Down diag. 4
O O O O
Up diag. 7 -> O O O O O <- Down diag. 3
O O O O
Up diag. 8 -> O O O O <- Down diag. 2
O O
Up diag. 9 -> O O <- Down diag. 1
Legal moves
A marble may move a single space in any of 6 possible directions - along an up diagonal, a down diagonal, or vertically as long as the "move to" space is empty.
or
A marble may jump over another single marble to an empty space in any of the 6 directions provided the "Jump to" space is empty. These jumps may be chained (multiple jumps) within a single turn. The object is to move the set of marbles from the left hand triangle to the extreme right hand triangle in a minimum number of moves.
Minimum Number of Moves
There are many ways the 10 marbles can be moved from the left hand triangle to the right triangle in 27 moves. It appears the 27-move solutions are minimal. (The computer search did not explicitly eliminate a 26-move solution, but given the breadth of the search, a 26-move solution appears EXTREMELY unlikely.)
The following table shows 5 solutions. They are characterized by having different board positions at the end of move number 13. Typically each solution has several variations in the move sequence to get to the "move-13 pattern" followed by several other variations for the final 14 moves. Thus, the total number of solutions is significantly higher.
Moves are defined by moving the marble at "Up diagonal, Down diagonal" to "Up diagonal, Down diagonal" using the grid coordinates shown in the above diagram. If a chain of jumps is involved, only the start and ending position is given.
Notes: Single space moves include both up and down vertical directions. Some chain jumps stop short of the maximal potential chain length.
Computer program by Bill
Butler
Move <- "Up diag.,Down diag." to "Up diag.,Down diag." ->
Number Sol. # 1 Sol. # 2 Sol. # 3 Sol. # 4 Sol. # 5
-------------------------------------------------------------------
1 4,1 to 4,2 3,2 to 4,2 4,1 to 4,2 4,1 to 4,2 4,1 to 4,2
2 2,1 to 4,3 1,4 to 5,2 2,1 to 4,3 2,1 to 4,3 2,1 to 4,3
3 3,1 to 5,3 3,1 to 5,3 3,1 to 5,3 3,1 to 5,3 3,1 to 5,3
4 5,3 to 6,3 5,3 to 5,4 5,3 to 6,3 5,3 to 6,3 5,3 to 6,3
5 1,3 to 7,3 1,1 to 5,5 1,3 to 7,3 1,3 to 7,3 1,3 to 7,3
6 1,1 to 5,3 1,3 to 5,3 1,1 to 5,3 1,1 to 5,3 1,1 to 5,3
7 3,2 to 7,4 4,1 to 6,5 3,2 to 7,4 3,2 to 7,4 3,2 to 7,4
8 7,4 to 7,5 6,5 to 7,5 7,4 to 7,5 7,4 to 7,5 7,4 to 7,5
9 4,2 to 3,3 1,2 to 3,2 1,2 to 7,6 1,4 to 7,6 1,4 to 7,6
10 1,4 to 7,6 2,3 to 8,5 1,4 to 7,4 7,6 to 7,7 7,6 to 7,7
11 1,2 to 7,4 2,1 to 6,5 2,3 to 3,2 1,2 to 7,8 1,2 to 7,8
12 2,2 to 8,6 4,2 to 8,6 4,2 to 8,6 2,2 to 3,2 2,3 to 3,2
13 6,3 to 8,7 8,6 to 8,7 8,6 to 8,7 3,2 to 7,6 3,2 to 7,6
14 8,7 to 7,8 2,2 to 8,8 2,2 to 8,8 2,3 to 3,2 2,2 to 3,2
15 4,3 to 8,7 3,2 to 4,2 3,2 to 4,2 3,2 to 7,4 3,2 to 7,4
16 8,7 to 8,8 4,2 to 8,6 4,2 to 8,6 4,2 to 8,8 4,2 to 8,8
17 2,3 to 8,9 5,4 to 9,8 8,7 to 7,8 6,3 to 8,9 6,3 to 8,9
18 3,3 to 4,3 5,2 to 7,8 6,3 to 6,9 4,3 to 6,9 4,3 to 6,9
19 4,3 to 6,9 8,7 to 8,9 4,3 to 8,9 7,7 to 8,6 7,7 to 8,6
20 5,3 to 6,3 5,3 to 5,4 5,3 to 6,3 5,3 to 6,3 5,3 to 6,3
21 6,3 to 8,7 5,4 to 9,6 6,3 to 8,7 6,3 to 8,7 6,3 to 8,7
22 7,5 to 9,9 7,5 to 7,9 7,5 to 9,9 7,5 to 9,9 7,5 to 9,9
23 7,3 to 7,9 5,5 to 9,9 7,3 to 7,9 7,3 to 7,9 7,3 to 7,9
24 7,4 to 7,5 6,5 to 7,5 7,4 to 7,5 7,4 to 7,5 7,4 to 7,5
25 7,5 to 9,7 7,5 to 9,7 7,5 to 9,7 7,5 to 9,7 7,5 to 9,7
26 7,6 to 9,8 8,5 to 6,9 7,6 to 9,8 7,6 to 9,8 7,6 to 9,8
27 8,6 to 9,6 8,6 to 8,7 8,6 to 9,6 8,6 to 9,6 8,6 to 9,6
Solution Notes
The above 5 solutions are characterized by having different board positions after 13 moves. These are the only solutions (as defined by unique board positions after 13 moves) found by the computer program. (The computer program found the above 5 solutions by the time the “breadth” search used the best 200,000 positions on each iteration. A further increase in the size of the “breadth” to 17,000,000 positions did not produce any additional solutions.) While other 27-move solutions might exist, this is considered most unlikely. (Note: there are mirror images of the above sequences, but these are not considered as "different".) Also, a 26-move solution is considered extremely unlikely.
Solutions 4 and 5 are very similar, but the choice of moves at move number 12 produces a slight variation in the move 13 position. Hence, they technically qualify as being different. Solutions 2 and 3 are both symmetrical as the final 13 moves of each are mirror images of the first 13 moves.
Computer Algorithm
The computer program used a 17,000,000 position wide "breadth first" search out of all possible board positions (mirror images were eliminated). With a “breadth width” of 17,000,000, you could waste the first 8 moves (return to the original start position) and this original start position would still be included in the search patterns.
In designing the algorithm, we note that the final position (triangle on the right hand side of the board) forms a mirror image of the start position. i.e. An efficient way of starting a solution must be followed by an efficient way of finishing a solution. Thus, the logic of the program takes advantage of the fact that the final 13 moves of a solution would have to be a mirror image match of one of the other first 13-move positions (26-move solution), or would have to match one of the 14-move positions (27-move solution).
The algorithm used looks like:
Initialize the system. The
starting board position is the only "new" position
For each of 14 iterations
Copy all the "new" board positions to the "old" board positions
For each of the "old" board positions (increases to 17,000,000 on the 9th iteration)
For each of the 10 marbles in the current "old" position
For each possible move of each of these marbles
Calculate the "Score" for the resulting new position
If this "new" position candidate is not already listed in the "new" positions
and either there are less than 17,000,000 "new" positions or the score
for this new candidate is better than the worst of the other
17,000,000 "new" positions, then add this new candidate to the
current list of the "new" positions. (Also keep track of the
historical move sequence)
End If
End of loop "For each possible move"
End of loop "For each of the 10 marbles"
End of loop "For each of the old board positions"
End of loop "For each of 14 iterations"
// At this point the best 17,000,000 13-move positions and the best 17,000,000
// 14-move positions are available to be compared.
Compare all 13-move positions (there are 17,000,000 of them) with the mirror image
of all the other 13-move positions. If there is a match, then a 26-move solution
has been found. (There weren't any.)
Compare all 13-move positions with the mirror image of all the 14-move positions.
If there is a match, then a 27-move solution has been found.
For each of 14 iterations
Copy all the "new" board positions to the "old" board positions
For each of the "old" board positions (increases to 17,000,000 on the 9th iteration)
For each of the 10 marbles in the current "old" position
For each possible move of each of these marbles
Calculate the "Score" for the resulting new position
If this "new" position candidate is not already listed in the "new" positions
and either there are less than 17,000,000 "new" positions or the score
for this new candidate is better than the worst of the other
17,000,000 "new" positions, then add this new candidate to the
current list of the "new" positions. (Also keep track of the
historical move sequence)
End If
End of loop "For each possible move"
End of loop "For each of the 10 marbles"
End of loop "For each of the old board positions"
End of loop "For each of 14 iterations"
// At this point the best 17,000,000 13-move positions and the best 17,000,000
// 14-move positions are available to be compared.
Compare all 13-move positions (there are 17,000,000 of them) with the mirror image
of all the other 13-move positions. If there is a match, then a 26-move solution
has been found. (There weren't any.)
Compare all 13-move positions with the mirror image of all the 14-move positions.
If there is a match, then a 27-move solution has been found.
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)