Hello there,
I am currently trying to solve Towers of Hanoi for N pegs using C++.
I am implementing the towers in the form of a link list.
Suppose there be three towers , TowerA,TowerB,TowerC
Then for
TowerA: 3 2 1
TowerB: -
TowerC:-
shall become
TowerA:
TowerB: 3 2 1
TowerC:
I have taken a class called 'pole' , is
class pole
{
public:
int data;
pole *next;
pole()
{
data=999;
next=NULL;
}
/*And Some Methods*/
};The Methods are as follows :
1. void add(int temp_data) ->
Adds a node to the list of nodes of Calling object with data=temp_data;
2. pole* pop() ->
Returns a pointer to the node popped. Meaning, last node of the calling object's list of nodes is removed and pointer to that node is returned.
3. void move1(pole *PoleB) ->
Removes the last node from Calling Object's list of nodes and adds the node to *PoleB 's list of nodes. This is to move 1 peg from Pole A to Pole B
4. void move2(pole *PoleB,pole *PoleC) ->
Moves top two nodes of Calling Object's list of nodes to *PoleB.
5. Display method to show the nodes.
-----------
Non member methods.
--------------------------
1. void move(pole *PoleA,pole *PoleB,pole *PoleC) ->
A recursive method. Moves all nodes from *PoleA to *PoleB.
if *PoleA has two nodes only then call move2(*PoleA,*PoleB,*PoleC)
else
call move(*PoleA->next,*PoleC,*PoleB)
call move1(*PoleA,*PoleB,*PoleC)
call move(*PoleC,*PoleB,*PoleA)
Well its working for tower with 3,4 pegs but not with pegs more than 4!! For pegs more than 4 , it goes into infinte recursion !! :(
So to get sample outputs i had to put in a cin.get() within move2 function. Hit Enter once to get 2 moves of pegs at a time. :(
My Code Snippet!
#include <iostream>
using namespace std;
class pole;
namespace print
{
void printpoles(pole*,pole*,pole*);
}
class pole
{
public:
int data;
pole *next;
pole()
{
data=999;
next = NULL;
}
pole(int temp_data)
{
data=temp_data;
next = NULL;
}
void add(int temp_data)
{
pole *temp;
temp=this;
while(temp->next!=NULL)
{
temp=temp->next;
}
temp->next=new pole();
temp=temp->next;
temp->data=temp_data;
}
void add(pole *temp_data)
{
pole *temp;
temp=this;
while(temp->next!=NULL)
{
temp=temp->next;
}
temp->next=temp_data;
}
void display()
{
pole *temp;
temp=this;
if(temp->next!=NULL)
{
while(temp->next)
{
temp=temp->next;
cout<<" "<<temp->data;
}
}
else
{
cout<<" -";
}
cout<<endl;
}
pole* pop()
{
pole *temp;
pole *temp1;
temp=this;
temp1=this;
while(temp->next!=NULL)
{
temp1=temp;
temp=temp->next;
}
temp1->next=NULL;
return temp;
}
void move1(pole *PoleB)
{
pole *PoleA;
PoleA=this;
PoleB->add(PoleA->pop());
}
void move2(pole *PoleB,pole *PoleC,pole *A,pole *B, pole *C)
{
cout<<"Hit enter to get another 2 moves of pegs...";
cin.get();
pole *PoleA;
PoleA=this;
cout<<"\nInto Move2 function\n";
print::printpoles(A,B,C);
PoleC->add(PoleA->pop());
print::printpoles(A,B,C);
PoleB->add(PoleA->pop());
print::printpoles(A,B,C);
PoleB->add(PoleC->pop());
print::printpoles(A,B,C);
}
};
void move(pole *PoleA,pole *PoleB, pole *PoleC,pole *A,pole *B, pole *C)
{
if(PoleA!=NULL)
{
if(PoleA->next!=NULL)
{
if(PoleA->next->next!=NULL)
{
if(PoleA->next->next->next==NULL)
{
PoleA->move2(PoleB,PoleC,A,B,C);
return;
}
else
{
if(PoleA->next!=NULL && PoleC!=NULL && PoleB!=NULL)
{
move(PoleA->next,PoleC,PoleB,A,B,C);
cout<<"Move : PoleA->next to PoleC :DONE\n";
print::printpoles(A,B,C);
PoleA->move1(PoleB);
cout<<"Move1 : PoleA to PoleB :DONE\n";
print::printpoles(A,B,C);
move(PoleC,PoleB,PoleA,A,B,C);
cout<<"Move : PoleC to PoleB :DONE\n";
print::printpoles(A,B,C);
}
}
}
}
}
else
{
return;
}
}
pole Pole_A,Pole_B,Pole_C;
void print::printpoles(pole *A,pole *B, pole *C)
{
cout<<"Tower A:";
A->display();
cout<<"Tower B:";
B->display();
cout<<"Tower C:";
C->display();
cout<<endl;
}
int main()
{
cout << "Hello world! Now let us solve the tower of Hanoi!" << endl;
//Pole_A.add(5);
Pole_A.add(4);
Pole_A.add(3);
Pole_A.add(2);
Pole_A.add(1);
Pole_A.display();
cout<<endl;
move(&Pole_A,&Pole_B,&Pole_C,&Pole_A,&Pole_B,&Pole_C);
/*
PoleB.add(PoleA.pop());
cout<<endl;
*/
cout<<"\nFinal state:\n";
print::printpoles(&Pole_A,&Pole_B,&Pole_C);
cin.get();
return 0;
}I am attaching sample output in txt file for 4 pegs and 5 pegs.
If u notice the output for 5 pegs, u will see that for
Tower A: 5 4 3 2 1
Tower B: -
Tower C: -
i am getting
Tower A: -
Tower B: 5
Tower C: 4 3 2 1
which is fine, but problem starts after this!!
instead of
Tower A: 3 2 1
Tower B: 5 4
Tower C: -
after which 3 2 1 can be moved onto TowerB
i am getting :
Tower A: 3
Tower B: 5 2 1
Tower C: 4
Tower A: 3 1
Tower B: 5 2
Tower C: 4
Tower A: 3 1
Tower B: 5
Tower C: 4 2
Tower A: 3
Tower B: 5
Tower C: 4 2 1
:-(
Any help ?
