Assignment 8 - Due Thursday March 11 23:59 by e-mail

# The Towers of Hanoi

For this assignment, the last one before Spring Break, you will have to work out only one problem: the Tower of Hanoi puzzle.

A stack of `n` disks of decreasing size is to be transported from the leftmost peg to the rightmost peg. The middle peg can be used as a temporary storage.

One disk can be moved at one time, from any peg to any other peg. You can only place smaller disks on top of larger ones, not the other way around. Write a procedure that prints the moves necessary to solve the puzzle for `n` disks.

Print moves in the form:

`Move disk from peg One to peg Three`
`Hint`: write a method
`void hanoi(String source, String target, String temp, int n)`
that moves the top `n` disks from the peg `source` to the peg `target` using the peg `temp` as temporary storage peg.

Then figure out how you can achieve that (recursively) by

• first moving the top `n - 1` disks from the first peg (`source`) to the third peg (`temp`),
• then moving the `n`th disk (from `source`) to destination (`target`), and finally
• moving the pile from the third peg (`temp`) to the destination peg (`target`), this time using the original peg (`source`) as the temporary storage.

Here's a possible session with your program:

```school.cs.indiana.edu%javac Hanoi.java
school.cs.indiana.edu%java Hanoi
Solving for 3 disks
Move disk from peg One   to peg Three
Move disk from peg One   to peg Two
Move disk from peg Three to peg Two
Move disk from peg One   to peg Three
Move disk from peg Two   to peg One
Move disk from peg Two   to peg Three
Move disk from peg One   to peg Three
school.cs.indiana.edu%```
The Hanoi Tower on the web (interactive applet and analysis).