Tower of Hanoi

The Tower of Hanoi (also called the Tower of Brahma or Lucas’ Tower, and sometimes pluralised) is a mathematical game or puzzle. It consists of three rods, and a number of disks of different sizes which can slide onto any rod. The puzzle starts with the disks in a neat stack in ascending order of size on one rod, the smallest at the top, thus making a conical shape.Tower_of_Hanoi

The objective of the puzzle is to move the entire stack to another rod, obeying the following simple rules:

  1. Only one disk can be moved at a time.
  2.  Each move consists of taking the upper disk from one of the stacks and placing it on top of another stack i.e. a disk can only be moved if it is the uppermost disk on a stack.
  3. No disk may be placed on top of a smaller disk.

The key idea for solving tower of hanoi problem is to first break down the problem in terms of the lowermost disc and (n-1) discs on top of it. That is, treat (n-1) discs from the top as one entity. This would be out recursive step. We would keep on breaking the number of discs into 1 and (n-1) discs, till the number of discs reduce to 1. This is our base condition and the solution of one disc is simply moving the lone disc from start to finish.

For example:

  • label the pegs A, B, C — these labels may move at different steps
  • let n be the total number of discs
  • number the discs from 1 (smallest, topmost) to n (largest, bottommost)

To move n discs from peg A to peg C:

  1. move n−1 discs from A to B. This leaves disc n alone on peg A
  2. move disc n from A to C
  3. move n−1 discs from B to C so they sit on disc n

The Java program for the solving the Tower of Hanoi problem is as follows:

class Hanoi{
    public static void main( String args[] ){
        moveDisc( 4, 'A', 'B', 'C' );
    }
    public static void moveDisc( int n, char start, char finish, char temp ){
        if( n == 1 ){
            System.out.println( start + " > " + finish );
        }else{
            moveDisc( n-1 , start, temp, finish );
            System.out.println( start + " > " + finish );
            moveDisc( n-1 , temp, finish, start );
        }
    }
}

The output of the above program, would be the solution of Tower of Hanoi problem for 4 discs, as follows:

A > C
A > B
C > B
A > C
B > A
B > C
A > C
A > B
C > B
C > A
B > A
C > B
A > C
A > B
C > B

As usual, the main function has purposely been kept to minimum and its expected that students will write appropriate input/output statements as per the requirement.

Leave a Reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.