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

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:

Test your program as follows:

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

Complete the following files:

DiskMover.java

DiskMoverTester2.java

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");
   }
}