Towers of Hanoi. This is a well-known puzzle. A stack of disks of decreasing size is to be transported from the leftmost peg to the rightmost peg. The middle peg can be used as temporary storage (see Figure 13.5). One disk can be moved at one time, from any peg to any other peg. You can place smaller disks only on top of larger ones, not the other way around.
Write a program that prints the moves necessary to solve the puzzle for n disks. (Ask the user for n at the beginning of the program.) Print moves in the form
Move disk from peg 1 to peg 3
Hint: Implement a class DiskMover. The constructor takes
The source peg from which to move the disks (1, 2, or 3)
The target peg to which to move the disks (1, 2, or 3)
The number of disks to move
The nextMove asks that disk mover for its next move until it is done. The effect is to move the first disks - 1 disks to the other peg. Then the nextMove method issues a command to move a disk from the from peg to the to peg. Finally, it constructs another disk mover DiskMover(other, target, disks - 1) that generates the moves that move the disks from the other peg to the target peg.
Hint: It helps to keep track of the state of the disk mover:
BEFORE_LARGEST: The helper mover moves the smaller pile to the other peg.
LARGEST: Move the largest disk from the source to the destination.
AFTER_LARGEST: The helper mover moves the smaller pile from the other peg to the target.
DONE: All moves are done.