#include <iostream.h>
#include <math.h>
#define ARRAYSIZE 100
/*************************************************************************************************
PROGRAMMED BY : REHAN AHMED KHAN
PAKISTAN- KARACHI
BS student in FAST University
(foundation for advancement of science and technology)
this program is free ware and anyone can use it.
/************************************************************************************************/
/*************************************************************************************************
* THE ALGORITHM USED IS AS FOLLOWS *
* *
* Because the tree is complete it can be stored in an array of 2^n-1. *
* The root of the tree is in position 2^(n-1)-1 *
* for any level j, the first node at that level is in position 2^(n-1-j)-1 *
* and each successive node at that level is 2^(n-j) elements beyond the previous element *
* at that level *
* So the sequential traversal of the array produces the solution of Towers of Hanoi Problem *
* *
*************************************************************************************************/
class TowersHanoi
{
private:
struct //node structure
{
char chToPeg;
char chFromPeg;
int iDiskNo;
}node[ARRAYSIZE]; //Array of Nodes
char except(char chFromPeg, char chToPeg); //returns peg other than provided as parameter
public:
TowersHanoi(); //constructor
//generates the tree
void generateTree(char chFromPeg,char chToPeg, int iDiskNo);
};
//////////////////////////////////////////////////////////////////////////////////////////////////
TowersHanoi::TowersHanoi()
{
int iDiskNo;
cout << "\nENTER THE NUMBER OF DISKS >> ";
cin >> iDiskNo;
generateTree('A','B',iDiskNo);
int cMoves=(int)pow(2,iDiskNo)-1;
cout << "THE MOVES ARE AS FOLLOWS\n";
for(int i=0;i<cMoves;i++)
cout << i+1 << ": " <<"Move Disk " << node[i].iDiskNo << " From " << node[i].chFromPeg
<< " To " << node[i].chToPeg << endl;
}
//////////////////////////////////////////////////////////////////////////////////////////////////
void TowersHanoi::generateTree(char chFromPeg, char chToPeg, int iDiskNo)
{
int j, iLevel=1, iDistance, iDistance2;
int iNodeIndex;
node[(int)pow(2,iDiskNo-1)-1].chToPeg=chToPeg;
node[(int)pow(2,iDiskNo-1)-1].chFromPeg=chFromPeg;
node[(int)pow(2,iDiskNo-1)-1].iDiskNo=iDiskNo;
for(int i=1;i<=iDiskNo-1;i++)
{
iDistance=0;
iDistance2=(int)pow(2,iDiskNo-i);
for(j=0;j<(int)pow(2,i);j++)
{
if(j%2==0)
{
iNodeIndex=iDistance+(int)pow(2,iDiskNo-1-i)-1;
node[iNodeIndex].chToPeg=
except(node[iNodeIndex+iDistance2/2].chFromPeg,
node[iNodeIndex+iDistance2/2].chToPeg);
node[iNodeIndex].chFromPeg=
node[iNodeIndex+iDistance2/2].chFromPeg;
node[iNodeIndex].iDiskNo=iDiskNo-iLevel;
}
else
{
iNodeIndex=iDistance+(int)pow(2,iDiskNo-1-i)-1;
node[iNodeIndex].chFromPeg=
except(node[iNodeIndex-iDistance2/2].chFromPeg,
node[iNodeIndex-iDistance2/2].chToPeg);
node[iNodeIndex].chToPeg=
node[iNodeIndex-iDistance2/2].chToPeg;
node[iNodeIndex].iDiskNo=iDiskNo-iLevel;
}
iDistance+=(int)pow(2,iDiskNo-i);
}
iLevel++;
}
}
//////////////////////////////////////////////////////////////////////////////////////////////////
char TowersHanoi::except(char chFromPeg, char chToPeg)
{
if(chFromPeg=='A' && chToPeg=='B' || chFromPeg=='B' && chToPeg=='A')
return 'C';
if(chFromPeg=='A' && chToPeg=='C' || chFromPeg=='C' && chToPeg=='A')
return 'B';
if(chFromPeg=='B' && chToPeg=='C' || chFromPeg=='C' && chToPeg=='B')
return 'A';
}
//////////////////////////////////////////////////////////////////////////////////////////////////
/*ostream& operator << (ostream& s,nodeHanoi node)
{
return s <<"Move Disk " << node.iDiskNo << " From " << node.chFromPeg
<< " To " << node.chToPeg << endl;
}*/
//////////////////////////////////////////////////////////////////////////////////////////////////
void main(void)
{
cout << "A represents FROM PEG,\nB represents TO PEG,\nC represents AUXILLARY PEG\n";
TowersHanoi towersHanoi;
}