Sunday, September 7, 2014

Towers of Hanoi Recursive Solution [Explanation][Towers of Hanoi][Java]

The Problem:

You are given 3 towers and N disks stacked on one of the towers lets say A.
The larger disks are at the bottom, smaller ones are on the top. So basically, a cone shape is
formed on disk A at the start.

You need to move all the disks from tower A to tower C following the rules:

1. Only one disk can be moved at a time.
2. You can only remove the topmost disk from a tower.
3. You can only place a smaller disk on a larger one.

Use recursion to solve the problem:

[In this case we need to move the stack from Tower A to Tower C]

Source: 

public class TowerOfHanoi {
    public void move(int disk, char source, char dest, char spare){
        if(disk == 1) System.out.println("Moved disk "+disk+" from "+source+" to "+dest);
        else
        {
            move(disk-1, source, spare, dest);
            System.out.println("Moved disk "+disk+" from "+source+" to "+dest);
            move(disk-1, spare, dest, source);
        }
    }
    
    public static void main(String[] args){
        new TowerOfHanoi().move(4, 'A', 'C', 'B');
    }
}

In case of 1 disk: We simply move the disk from source to destination.

In case of 2 disks:
We need to move one disk to tower B and then the last disk to tower C and then the disk on tower B to tower C.

In case of 3 disks:
We need to move 2 disks to tower B (we have already done that in case 2 above - just move them to tower B instead of tower C using C as auxiliary tower). Then move one disk to C and again two disks to C.

Extends for N disks.

1. Whenever some disk needs to be moved, disks above it are moved and then when the current disk gets properly placed at its destination, the disks which were moved are again moved above it.
2. The problem had been divided into sub problems and results are combined to give the solution to the original problem of  moving the disk stack from tower A to tower C.

Recursive calls:


No comments:

Post a Comment