The Towers of Hanoi is an ancient puzzle consisting of a number of disks placed on three columns, the disks all have different diameters and holes in the middle so they will fit over the columns. All the disks start out on column A. The object of the puzzle is to transfer all the disks from column A to column C. Only one disk can be moved at a time, and no disk can be placed on a disk that’s smaller than itself. There’s an ancient myth that somewhere in India, in a remote temple, monks labor day and night to transfer 64 golden disks from one of three diamond-studded towers to another. When they are finished, the world will end. Any alarm you may feel, however, will be dispelled when you see how long it takes to solve the puzzle for far fewer than 64 disks.
Moving Subtrees
Let’s call the initial tree-shaped (or pyramid-shaped) arrangement of disks on tower A a tree. (This kind of tree has nothing to do with the trees that are data storage struc- tures) . Let’s call these smaller trees, containing fewer than the total number of disks, subtrees. For example, if you’re trying to transfer four disks, you’ll find that one of the intermediate steps involves a subtree of three disks on tower B,
These subtrees form many times in the solution of the puzzle. This happens because the creation of a subtree is the only way to transfer a larger disk from one tower to another: All the smaller disks must be placed on an intermediate tower, where they naturally form a subtree.
Here’s a rule of thumb that may help when you try to solve the puzzle manually. If the subtree you’re trying to move has an odd number of disks, start by moving the topmost disk directly to the tower where you want the subtree to go. If you’re trying to move a subtree with an even number of disks, start by moving the topmost disk to the intermediate tower.
The Recursive Algorithm
The solution to the Towers of Hanoi puzzle can be expressed recursively using the notion of subtrees. Suppose you want to move all the disks from a source tower (call it S) to a destination tower (call it D). You have an intermediate tower available (call it I). Assume there are n disks on tower S. Here’s the algorithm:
Move the subtree consisting of the top n-1 disks from S to I.
Move the remaining (largest) disk from S to D.
Move the subtree from I to D.
When you begin, the source tower is A, the intermediate tower is B, and the destination tower is C.
First, the subtree consisting of disks 1, 2, and 3 is moved to the intermediate tower B. Then the largest disk, 4, is moved to tower C. Then the subtree is moved from B to C.
Of course, this solution doesn’t solve the problem of how to move the subtree consisting of disks 1, 2, and 3 to tower B, because you can’t move a subtree all at once; you must move it one disk at a time. Moving the three-disk subtree is not so easy. However, it’s easier than moving four disks.
As it turns out, moving three disks from A to the destination tower B can be done with the same three steps as moving four disks. That is, move the subtree consisting of the top two disks from tower A to intermediate tower C; then move disk 3 from A to B. Then move the subtree back from C to B.
How do you move a subtree of two disks from A to C? Move the subtree consisting of only one disk (1) from A to B. This is the base case: When you’re moving only one disk, you just move it; there’s nothing else to do. Then move the larger disk (2) from A to C, and replace the subtree (disk 1) on it.
The towers.java Program
The towers.java program solves the Towers of Hanoi puzzle using this recursive approach. It communicates the moves by displaying them; this approach requires much less code than displaying the towers. It’s up to the human reading the list to actually carry out the moves.
The code is simplicity itself. The main() routine makes a single call to the recursive method doTowers(). This method then calls itself recursively until the puzzle is solved. There are initially only three disks, but you can recompile the program with any number.
// towers.java
// solves the towers of Hanoi puzzle
class TowersApp{
static int nDisks = 3;
public static void main(String[] args) {
doTowers(nDisks, ‘A’, ‘B’, ‘C’);
} //-----------------------------------------------------------
public static void doTowers(int topN, char from, char inter, char to){
if(topN==1)
System.out.println(“Disk 1 from “ + from + “ to “+ to);
else{
doTowers(topN-1, from, to, inter); // from-->inter
System.out.println(“Disk “ + topN + “ from “ + from + “ to “+ to);
doTowers(topN-1, inter, from, to); // inter-->to
}
}
//----------------------------------------------------------
} // end class TowersApp
Remember that three disks are moved from A to C. Here’s the output from the program:
Disk 1 from A to C
Disk 2 from A to B
Disk 1 from C to B
Disk 3 from A to C
Disk 1 from B to A
Disk 2 from B to C
Disk 1 from A to C
The arguments to doTowers() are the number of disks to be moved, and the source (from), intermediate (inter), and destination (to) towers to be used. The number of disks decreases by 1 each time the method calls itself. The source, intermediate, and destination towers also change.
Here is the output with additional notations that show when the method is entered and when it returns, its arguments, and whether a disk is moved because it’s the base case (a subtree consisting of only one disk) or because it’s the remaining bottom disk after a subtree has been moved:
Enter (3 disks): s=A, i=B, d=C Enter (2 disks): s=A, i=C, d=B
Enter (1 disk): s=A, i=B, d=C Base case: move disk 1 from
Return (1 disk)
Move bottom disk 2 from A to B Enter (1 disk): s=C, i=A, d=B
Base case: move disk 1 from Return (1 disk)
Return (2 disks)
Move bottom disk 3 from A to C Enter (2 disks): s=B, i=A, d=C
Enter (1 disk): s=B, i=C, d=A Base case: move disk 1 from
Return (1 disk)
Move bottom disk 2 from B to C Enter (1 disk): s=A, i=B, d=C
Base case: move disk 1 from Return (1 disk)
Return (2 disks) Return (3 disks)
A to C
C to B
B to A
A to C
If you study this output along with the source code for doTower(), it should become clear exactly how the method works. It’s amazing that such a small amount of code can solve such a seemingly complicated problem.