The idea is that there are 3 towers, I gonna name them "ini", "temp" and "end" and 'n' disks.

The initial state is defined as all the disks in the "ini" tower.

Each disk has a unique diameter and the goal is to move all the disks from the "ini" to "end" using "temp", if needed.

Some rules are to be honored:

- Only one disk can be moved at the time.
- A disk can never have a bigger disk above.
- The towers are stacks. This is: first in, last out.

This is an animation for 4 disks:

But it has a strong recursive nature. If somehow we could get the problem solved for (n-1) disks shown as follows: Then we only need to move the n-disk from "ini" to "end" to get the configuration: And now again if somehow we could move (n-1) from "temp" to "end" then the game is solved! So to sum up we've moved:

- Step 1: (n-1) disks from "ini" to "temp".
- Step 2: the n-disk (the last one) from "ini" to "end".
- Step 3:(n-1) disks from "temp" to "end".

Therefore our new algorithm will look like:

- Step 1: call hanoi of (n-1) disks from "ini" to "temp".
- Step 2: move disk from "ini" to "end".
- Step 3: call hanoi of (n-1) disks from "temp" to "end".

Finally our code (in Java) would be:

/** * * @author Kriche */ public class Hanoi { private static final int DISKS = 4; private static final String INI_TOWER_NAME = "ini"; private static final String TEMP_TOWER_NAME = "temp"; private static final String END_TOWER_NAME = "end"; /** * * @param args */ public static void main(String[] args) { System.out.println("Hanoi for " + DISKS + " disks!"); hanoi(DISKS, INI_TOWER_NAME, TEMP_TOWER_NAME, END_TOWER_NAME); } /** * * @param disk * @param ini * @param temp * @param end */ private static void hanoi(int disks, String ini, String temp, String end) { // recursive implementation //Base case check if (disks > 0) { hanoi(disks - 1, ini, end, temp); // Our contribution to get closer to the base case: // Just for demo, use StringBuffer or StringBuilder in actual programs! System.out.println("\tMove disk: " + disks + " from " + ini + " to " + end + "."); hanoi(disks - 1, temp, ini, end); } } }Running this program will produce this output:

Hanoi for 4 disks! Move disk: 1 from ini to temp. Move disk: 2 from ini to end. Move disk: 1 from temp to end. Move disk: 3 from ini to temp. Move disk: 1 from end to ini. Move disk: 2 from end to temp. Move disk: 1 from ini to temp. Move disk: 4 from ini to end. Move disk: 1 from temp to end. Move disk: 2 from temp to ini. Move disk: 1 from end to ini. Move disk: 3 from temp to end. Move disk: 1 from ini to temp. Move disk: 2 from ini to end. Move disk: 1 from temp to end.

We've done a lot of progress! The problem is solved but there is much more to see!

Later in "Recursion Removal" we will see a nonrecursive solution to this fascinating problem!!