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.
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
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 4,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 4,000,000 position wide
"breadth first" search out of all possible board positions (mirror
images were eliminated). 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
4,000,000 on the 8th 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 4,000,000 "new" positions or the score
for this new candidate is better than the worst of the other
4,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 4,000,000 13-move positions and the
best 4,000,000
// 14-move positions are available to be compared.
Compare all 13-move positions (there are 4,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
KompoZer