RECURSION - Java Programming: From Problem Analysis to Program Design - page 885

EXAMPLE 13-3 TOWER OF HANOI

In the nineteenth century, a game called the Tower of Hanoi was popular in Europe. This
game is based on a legend regarding the construction of the temple of Brahma. According
to this legend, at the creation of the universe, priests in the temple of Brahma were given
three diamond needles, with one needle containing 64 golden disks. Each golden disk is
slightly smaller than the disk below it. The priests' task was to move all 64 disks from the
first needle to the third needle. The rules for moving the disks are as follows:
1. Only one disk can be moved at a time.
2. The removed disk must be placed on one of the needles.
3. A larger disk cannot be placed on top of a smaller disk.
The priests were told that once they had moved all the disks from the first needle to the
third needle, the universe would come to an end.
Our objective is to write a program that prints the sequence of moves needed to transfer
the disks from the first needle to the third needle. Figure 13-6 shows the Tower of Hanoi
problem with three disks.

1

2

3

FIGURE 13-6 Tower of Hanoi problem with three disks

As before, we think in terms of recursion. Let's consider the case where the first needle
contains only one disk. In this case, the disk can be moved directly from needle 1 to
needle 3. Now let's consider the case when the first needle contains only two disks. In
this case, we move the first disk from needle 1 to needle 2, and then we move the second
disk from needle 1 to needle 3. Finally, we move the first disk from needle 2 to needle 3.
Next, we consider the case where the first needle contains three disks, and then generalize
this to the case of 64 disks (in fact, to an arbitrary number of disks).
Suppose that needle 1 contains three disks. To move disk number 3 to needle 3, the top
two disks must first be moved to needle 2. Disk number 3 can then be moved from
needle 1 to needle 3. To move the top two disks from needle 2 to needle 3, we use the
same strategy as before. This time, we use needle 1 as the intermediate needle. Figure 13-7
shows a solution to the Tower of Hanoi problem with three disks.

1
3