The Tower of Hanoi game relies on recursion to successfully simulate the directions. While the code isn't difficult to write, picturing and understanding the recursive calls may be more challenging. The recursive method written in Java is as follows:
public static void hanoi(int disks, String source, String destination, String temp)
{
if(disks!=0)
{
hanoi(disks-1, source, temp, destination);
System.out.println("Move disk " + disks + " from " + source + " to " + destination);
hanoi(disks-1, temp, destination, source);
}
}
To start out with the simplest case of 3 discs, picture the following memory stacks, illustrated horizontally with the indentation of bullet points. Call the smallest piece at the top disk 1, and so forth. Currently, the discs are on the left tower. The ultimate destination is the right tower.
- hanoi(3, left, right, middle) //from an outside main method
- hanoi(2, left, middle, right)
- hanoi(1, left, right, middle)
- "Move disk 1 from left to right"
- "Move disk 2 from left to middle"
- hanoi(1, right, middle, left)
- "Move 1 disk from right to middle"
- "Move disk 3 from left to right"
- hanoi(2, middle, right, left)
- hanoi(1, middle, left, right)
- "Move disk 1 from middle to left"
- "Move disk 2 from middle to right"
- hanoi(1, left, right, middle)
- "Move disk 1 from left to right"
Collecting the direction displays:
- Move disk 1 from left to right
- Move disk 2 from left to middle
- Move 1 disk from right to middle
- Move disk 3 from left to right
- Move disk 1 from middle to left
- Move disk 2 from middle to right
- Move disk 1 from left to right
In general, while moving n disks from tower A to tower B (using tower C as temporary holder):
- If n is even, begin by moving disk 1 from A first to C
- If n is odd, begin by moving disk 1 from A first to B
Source:
