Java Reference
In-Depth Information
All the disks are initially placed on tower A.
■
Only one disk can be moved at a time, and it must be the smallest disk on a tower.
■
The objective of the problem is to move all the disks from A to B with the assistance of C. For
example, if you have three disks, the steps to move all of the disks from A to B are shown in
Figure 20.6.
0
4
2
3
1
2
3
A
B
C
A
B
C
Original position
Step 4: Move disk 3 from A to B
1
5
2
3
3
1
1
2
A
B
C
A
B
C
Step 1: Move disk 1 from A to B
Step 5: Move disk 1 from C to A
2
6
2
3
1
2
1
3
A
B
C
A
B
C
Step 2: Move disk 2 from A to C
Step 6: Move disk 2 from C to B
3
7
1
1
2
3
2
3
A
B
C
A
B
C
Step 3: Move disk 1 from B to C
Step 7: Move disk 1 from A to B
F
IGURE
20.6
The goal of the Towers of Hanoi problem is to move disks from tower A to
tower B without breaking the rules.
Note
The Towers of Hanoi is a classic computer-science problem, to which many websites are
In the case of three disks, you can find the solution manually. For a larger number of disks,
however—even for four—the problem is quite complex. Fortunately, the problem has an
inherently recursive nature, which leads to a straightforward recursive solution.
The base case for the problem is
n = 1
. If
n == 1
, you could simply move the disk from
A to B. When
n > 1
, you could split the original problem into the following three subprob-
lems and solve them sequentially.
1. Move the first
n - 1
disks from A to C with the assistance of tower B, as shown in Step
1 in Figure 20.7.
2. Move disk
n
from A to B, as shown in Step 2 in Figure 20.7.
3. Move
n - 1
disks from C to B with the assistance of tower A, as shown in Step 3 in
Figure 20.7.
