Towers of Hanoi

The ‘Towers of Hanoi’ is a classical problem used to illustrate the power of recursion. The puzzle goes as follows.

There are three poles and 64 discs of different sizes. Initially, all the discs are placed on the first pole with the largest disc at the bottom and the smallest one at the top. We need to move all the discs from the first pole to the third pole, with the smallest disc at the top and the largest at the bottom. We can move only one disc at a time (which should be the topmost disc) and at any point of time, a larger disc cannot be placed over a smaller one i.e. all the discs on a pole must be placed in such a way that the smallest is at the top and the largest at the bottom. The second pole can be used as an intermediate pole to help us in transferring the discs.

This puzzle can be solved using recursion. For a moment, assume that there are just two discs (disc 1 and 2; disc 2 being the larger one) on the first pole. The solution consists of three steps.

Step 1: Move disc 1 from pole 1 to pole 2.
Step 2: Move disc 2 from pole 1 to pole 3.
Step 3: Move disc 1 from pole 1 to pole 3.

Now, assume that disc 1 is not a single disc but a collection of discs. The procedure would be similar to the above three steps, but steps 1 and 3 would be a collection of steps. Step 1 would be to move the n-1 discs (assuming that there were a total of n discs) from pole 1 to pole 2. For moving these (n -1) discs, we again follow the same strategy of considering them as 1 disc plus a set of n-2 discs. Step 3 would also be similar. This gives us the recursive solution.

Recursive Algorithm

The recursive solution to move n discs from the start pole to the end pole using an auxiliary pole is given below.

Base Case – When n = 1
Move the disc from start pole to end pole

Recursive Case – When n > 1
Step 1: Move (n-1) discs from start pole to auxiliary pole.
Step 2: Move the last disc from start pole to end pole.
Step 3: Move the (n-1) discs from auxiliary pole to end pole.
Steps 1 and 3 are recursive invocations of the same procedure.

Java Program

The recursive program for the puzzle in Java is given below:

public class TowersOfHanoi {

Public void solve(int n, String start, String auxiliary, String end) {
       if (n == 1) {
           System.out.println(start + ” -> ” + end);
       } else {
           solve(n – 1, start, end, auxiliary);
           System.out.println(start + ” -> ” + end);
           solve(n – 1, auxiliary, start, end);
       }
   }

Public static void main(String[] args) {
       TowersOfHanoi towersOfHanoi = new TowersOfHanoi();
       System.out.print(“Enter number of discs: “);
       Scanner scanner = new Scanner(System.in);
       int discs = scanner.nextInt();
       towersOfHanoi.solve(discs, “A”, “B”, “C”);
   }
}

The method solve() takes four arguments :

n – the number of discs in the puzzle
start, auxiliary, end -the names of the three poles which will be used for printing the solution

We first check if the number of poles, n is equal to one. If so, the base case solution will be used which consists of moving a disc from the start peg to the end peg. If not, the recursive solution is used which consists of two recursive calls to the same procedure solve(). When we need to move n-1 discs from the start pole to the auxiliary pole, the auxiliary pole becomes the end pole and the end pole becomes the auxiliary pole. That is why we have written

Instead of

Next we print ‘ start -> end ‘ which corresponds to moving the largest disc at the bottom from the start peg to the end peg.

Finally, we have recursive invocation of solve(). Here, the auxiliary peg becomes the start peg and the start peg becomes the auxiliary peg.

Here is a sample output with n = 3.

Enter number of discs: 3
A -> C
A -> B
C -> B
A -> C
B -> A
B -> C
A -> C