Code 101: Tower of Hanoi

Question:

Towers of Hanoi: In the classic problem of the Towers of Hanoi, you have 3 towers and N disks of different sizes which can slide onto any tower. The puzzle starts with disks sorted in ascending order of size from top to bottom (i.e., each disk sits on top of an even larger one).

You have the following constraints:

(1) Only one disk can be moved at a time.

(2) A disk is slid off the top of one tower onto another tower.

(3) A disk cannot be placed on top of a smaller disk. Write a program to move the disks from the first tower to the

last using Stacks.

Example 1:

Input: 2

Output: Disk 1 moved from A to B

Disk 2 moved from A to C

Disk 1 moved from B to C

Example 2:

Input: 3

Output: Disk 1 moved from A to C

Disk 2 moved from A to B

Disk 1 moved from C to B

Disk 3 moved from A to C

Disk 1 moved from B to A

Disk 2 moved from B to C

Disk 1 moved from A to C

Solution:

By this time we have done several questions on recursion and I believe we can see the similar pattern. Now talking about the problem statement. I feel the best way to solve this question is to first understand how the rings will move and I believe we can understand it better on pen and paper then on code.

First try it yourself and if it does not help, take a look at this animation which helped me to understand the problem better.

Now coming to solution, As we are considering this as a recursion problem we go back to our approach for recursion.

Base Case (when to stop)

As we know that when all the disks are moved from source to destination. We are arrived at a solution, also whenever we are left with the last ring we will move it from source to destination.

if (n == 1) 

move disk from source to destination

return;

Recursive Call (call ourselves)

As by question we can only move 1 ring at a time and we have 3 pegs so we will use them to interchangeably.

recursion(n - 1, from, to, inter)

&

recursion(n - 1, inter, from, to)

Work needed to move toward Base Case or Solution

public static void towerOfHanoi(int n, char origin, char buffer, char destination) {

    if (n == 1) {

        System.out.println("Move disc 1 from "+origin+" to "+ destination);

        return;

    }
towerOfHanoi(n - 1, origin, destination, buffer);
System.out.println("Move disc " + n + " from " + origin + " to " + destination);
towerOfHanoi(n - 1, buffer, origin, destination);

}

Hope you have a better understanding now, continue with the code101 series, and you'll gain a better understanding.

#HappyCoding