Recursion - Java Software Solutions: Foundations of Program Design - page 596

FIGURE 12.5 The Towers of Hanoi puzzle

The Towers of Hanoi
The Towers of Hanoi puzzle was invented in the 1880s by Edouard Lucas, a
French mathematician. It has become a favorite among computer scientists,
because its solution is an excellent demonstration of recursive elegance.
The puzzle consists of three upright pegs and a set of disks with holes in
the middle so that they slide onto the pegs. Each disk has a different diameter.
Initially, all of the disks are stacked on one peg in order of size such that the larg-
est disk is on the bottom, as shown in Figure 12.5.
The goal of the puzzle is to move all of the disks from their original (first) peg
to the destination (third) peg. We can use the “extra” peg as a temporary place to
put disks, but we must obey the following three rules:

We can move only one disk at a time.

■

We cannot place a larger disk on top of a smaller disk. ■

All disks must be on some peg except for the disk in transit between pegs.
These rules imply that we must move smaller disks “out of the way” in order to
move a larger disk from one peg to another. Figure 12.6 shows the step-by-step
solution for the Towers of Hanoi puzzle using three disks. In order to ultimately
move all three disks from the first peg to the third peg, we first have to get to the
point where the smaller two disks are out of the way on the second peg so that
the largest disk can be moved from the first peg to the third peg.
The first three moves shown in Figure 12.6 can be thought of as moving the
smaller disks out of the way. The fourth move puts the largest disk in its final
place. The last three moves then put the smaller disks to their final place on top
of the largest one.
Let's use this idea to form a general strategy. To move a stack of N disks from
the original peg to the destination peg:

■

Move the topmost N −1 disks from the original peg to the extra peg.

■

Move the largest disk from the original peg to the destination peg.

■

Move the N −1 disks from the extra peg to the destination peg.

■