Tower Of Hanoi


The description of Tower Of Hanoi problem is given:

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.

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

  • Only one disk may be moved at a time.
  • Each move consists of taking the upper disk from one of the rods and sliding it onto another rod, on top of the other disks that may already be present on that rod.
  • No disk may be placed on top of a smaller disk.

     

This problem is solved by recursion. The following algorithm is used to solve it:

To move n disks from peg X to peg Z, using Y as auxiliary peg:

1. If n = 1, move the single disk from X to Z and stop.
2. Move the top(n – 1) disks from the peg X to the peg Y, using Z as auxiliary.
3. Move nth disk to peg Z.
4. Now move n – 1 disk from Y to Z, using Z as auxiliary.

Now, this algorithm will be implemented in c++:


#include<conio.h>
#include<iostream.h>
class tower
{
int NoDisk;
char FromTower,ToTower,AuxTower;
public:
void hanoi(int,char,char,char);
};
void tower::hanoi(int NoDisk,char FromTower,char ToTower, char AuxTower)
{
//if only one disk, make the move and return
if (NoDisk == 1)
{

cout<<“\nMove from disk 1 from tower ”<<FromTower<<“ to tower ”<<ToTower;

return;
}
//Move top n–1 disks from X to Y, using Z as auxiliary tower
hanoi(NoDisk–1,FromTower,AuxTower,ToTower);
//Move remaining disk from X to Z
cout<<“\nMove from disk ”<<NoDisk<<“ from tower ”<<FromTower<<“ to tower
”<<ToTower;
//Move n–1 disk from Y to Z using X as auxiliary tower
hanoi(NoDisk–1,AuxTower,ToTower,FromTower);
return;
}
void main()
{
int No;
tower Ob;
clrscr();
cout<<“\n\t\t\t--- Tower of Hanoi ---\n”;
//Imput the number of disk in the tower
cout<<“\n\nEnter the number of disks = ”;
cin>>No;
//We assume that the towers are X, Y and Z
Ob.hanoi(No,‘X’,‘Z’,‘Y’);
cout<<“\n\nPress any key to continue...”;
getch();
}

Advertisements

One comment

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s