Assignment 8 - Solution

The Towers of Hanoi

Here's a minimal solution.

school.cs.indiana.edu%ls -l Hanoi*
-rw-------   1 dgerman       577 Mar 31 16:39 Hanoi.java
school.cs.indiana.edu%cat Hanoi.java
class Hanoi {
  public static void main(String[] args) {
    Hanoi game = new Hanoi(); 
    int numberOfDisks = 3; 
    game.solve("NY", "SF", "DC", numberOfDisks); 
  } 
  void solve(String source, String target, String temp, int n) { 
    if (n == 1) 
      System.out.println("MOVEDISK from peg " + source + " to peg " + target);
    else {
      solve(source, temp, target, n - 1); 
      System.out.println("MOVEDISK from peg " + source + " to peg " + target);
      solve(temp, target, source, n - 1); 
 
    } 
  } 
} 
school.cs.indiana.edu%javac Hanoi.java
school.cs.indiana.edu%java Hanoi
MOVEDISK from peg NY to peg SF
MOVEDISK from peg NY to peg DC
MOVEDISK from peg SF to peg DC
MOVEDISK from peg NY to peg SF
MOVEDISK from peg DC to peg NY
MOVEDISK from peg DC to peg SF
MOVEDISK from peg NY to peg SF
school.cs.indiana.edu%

Now the question, of course, is: once you understand this, what changes do you need to make to obtain the output illustrated in lecture notes 17, similar to the one presented below:

Move 3 from NY to SF using DC 
| Move 2 from NY to DC using SF 
| | Move 1 from NY to SF using DC 
| | | MOVEDISK from peg NY to peg SF
| | End 
| | MOVEDISK from peg NY to peg DC
| | Move 1 from SF to DC using NY
| | | MOVEDISK from peg SF to peg DC
| | End
| End 
| MOVEDISK from peg NY to peg SF
| Move 2 from DC to SF using NY
| | Move 1 from DC to NY using SF
| | | MOVEDISK from peg DC to peg NY
| | End 
| | MOVEDISK from peg DC to peg SF
| | Move 1 from NY to SF using DC
| | | MOVEDISK from peg NY to peg SF
| | End 
| End 
End

Ignore the color, but pay attention to the indentation and the way the sub-tasks are marked as having been solved. It is not hard to make the program output its own trace, but you may need to think about more parameters to be passed down the chain of recursive invocations.