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

A disk mover that moves a single disk from one peg to another simply has a nextMove method that returns a string

Move disk from peg
source to peg target

A disk mover with more than one disk to move must work harder. It needs another DiskMover to help it. In the constructor, construct a DiskMover(source, other, disks - 1) where other is the peg other than from and target.

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.

Test your program as follows:

DiskMover mover = new DiskMover(1, 3, n);
while (mover.hasMoreMoves())
{
System.out.println(mover.nextMove());
}

Complete the following files:

### DiskMoverTester3.java

Use the following file:

DiskMoverTester.java

```public class DiskMoverTester
{
public static void main(String[] args)
{
int n = 3;
DiskMover mover = new DiskMover(1, 3, n);
System.out.println(mover.nextMove());
System.out.println("Expected: Move disk from peg 1 to peg 3");
System.out.println(mover.nextMove());
System.out.println("Expected: Move disk from peg 1 to peg 2");
System.out.println(mover.nextMove());
System.out.println("Expected: Move disk from peg 3 to peg 2");
System.out.println(mover.nextMove());
System.out.println("Expected: Move disk from peg 1 to peg 3");
System.out.println(mover.nextMove());
System.out.println("Expected: Move disk from peg 2 to peg 1");
System.out.println(mover.nextMove());
System.out.println("Expected: Move disk from peg 2 to peg 3");
System.out.println(mover.nextMove());
System.out.println("Expected: Move disk from peg 1 to peg 3");
System.out.println(mover.hasMoreMoves());
System.out.println("Expected: false");
}
}
```