Tower of Hanoi : Algorithm

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.

The problem can be easily solved using recursion.
Algo:
moveDisks(int n, Tower origin, Tower destination, Tower buffer) {

/* Base case */
if (n <= 0) return;

/* move top n - 1 disks from origin to buffer, using destination as a buffer. */
moveDisks(n - 1, origin, buffer, destination);

/* move top from origin to destination
moveTop(origin, destination);

/* move top n - 1 disks from buffer to destination, using origin as a buffer. */

moveDisks(n - 1, buffer, destination, origin);
}

// n : Number of plates
// Origin: 1st tower, Buffer: Tower that will be used as buffer , Destination: Tower on which all plates has to transferred.
void moveTowers(int n, Tower destination, Tower buffer) {
       if(n>0) {
	      moveTowers(n-1, buffer, destination);
		  moveTopElement(destination);
		  moveTowers(n-1, destination, origin)
	   }
}
// This is a method in Tower class
 void moveTopTo(Tower t) { 
         int top= disks.pop(); 
         t.add(top);
 }
Comments (24)