DaniWeb Forum Index > Software Development > C++

C++ RSS

Solving Towers of Hanoi

Please support our C++ advertiser: Intel Parallel Studio Home

•

Join Date: May 2007

Posts: 62

Reputation: minigweek is on a distinguished road

Solved Threads: 4

minigweek

Offline

Junior Poster in Training

Solving Towers of Hanoi

Oct 12th, 2008

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

 Help with Code Tags 
 cpp Syntax (Toggle Plain Text) 
class pole
{
public:
int data;
pole *next;
 
pole()
{
data=999;
next=NULL;
}
 
/*And Some Methods*/
};
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!

 Help with Code Tags 
 cpp Syntax (Toggle Plain Text) 
#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;
}
#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 ?

Attached Files

	Hanoi_4pegs_Output.txt (1.5 KB, 1 views)
	Hanoi_5pegs_Output.txt (2.3 KB, 1 views)

I was born Genius, but some loser Leeched it.

•

Join Date: Nov 2007

Posts: 390

Reputation: skatamatic will become famous soon enough

Solved Threads: 39

skatamatic skatamatic is offline

Offline

Posting Whiz

Re: Solving Towers of Hanoi

Oct 12th, 2008

I think you need to isolate your issue a little better, and post as little code as possible. That's too much code! Step through/into the code (F10 and F11 in VS05) and keep an eye on the values of your locals to find where it actually fails.

•

Join Date: Jan 2008

Posts: 3,811

Reputation: VernonDozier has a reputation beyond repute

Solved Threads: 501

VernonDozier VernonDozier is offline

Offline

Senior Poster

Re: Solving Towers of Hanoi

Oct 12th, 2008

Almost assuredly your problem is that your stack keeps changing withing the move function and situations that were intended to be caught originally in one of the higher if statements are getting PAST that point and the calls are being made assuming stacks that USED to be there, but have been moved since by move1 and move2. The code is hard to file because PoleA, PoleB, and PoleC keep changing. I'd say you need to document better exactly what the move function does and what each section of the move code does. I sort of see where I think you are trying to go with this, but like I said, I'm not completely sure. I'm not sure what assumptions the move function makes and exactly what it does, but if it assumes that all the rings on PoleA are less than all the rings on PoleB and PoleA is to be moved on top of PoleB, that isn't the case here. You have a call from this line (in red):

Help with Code Tags

(Toggle Plain Text)

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;
	   }
   }

where PoleC contains {4} and PoleB contains {3, 2, 1}. So if move is intended to put the first argument on top of the second argument, that's a problem. It ends up eventually putting the {3, 2, 1} on top of the 4 on PoleC, as it should, then you move 5 over correctly to the destination peg, then you start moving the pegs back, but eventually you put a 5 on top of a 3 instead of putting the {2, 1} on top of the 3. Stepping through the program on the debugger, it seemed like a lot calls went through the function without doing anything when I thought it was supposed to. Again, I don't know what move does and what it expects, but if it expects that PoleA elements are always smaller than PoleB elements and PoleA is supposed to go on top of PoleB, you have a problem because the calls don't do that and the first call that passes parameters like that is considerably before the first problem shows up on the display. It's only a guess that that is the problem since you have not documented what move expects its parameters to be. If that's the assumption, you may want to write a function that tests for that and call it from the top of move, which will zone in right away on what the problem is and when.

Last edited by VernonDozier; Oct 12th, 2008 at 10:52 pm.

•

Join Date: Feb 2008

Posts: 114

Reputation: sidatra79 is an unknown quantity at this point

Solved Threads: 8

sidatra79

Offline

Junior Poster

Re: Solving Towers of Hanoi

Oct 13th, 2008

Hello
the fact that your code doesn't work for more than 3 pegs implies that u defined either the recursion base case or the recursion step wrong.

Therefore I post u the following working code:

 Help with Code Tags 
 c++ Syntax (Toggle Plain Text) 
#include <iostream>
 
void GetCorrectMoveSequence (int n, char startT, char goalT, char tempT)
{
	if (n == 1) //the base case of the recursion
	{
		std::cout<<"Move peg 1 from Tower: "<<startT
			<<" to Tower: "<< goalT <<std::endl;
	}
	else		//The recursive part
	{
		GetCorrectMoveSequence(n-1, startT, tempT, goalT); //WATCH HOW THE ORDER CHANGES
		std::cout<<"Move peg "<< n <<" from Tower: "<<startT
			<<" to Tower: "<< goalT <<std::endl;
		GetCorrectMoveSequence(n-1, tempT, goalT, startT); //WATCH HOW THE ORDER CHANGES AGAIN..
	}
}
 
int main()
{
	//The number of pegs
	int noPegs;
	//A letter representing the starting Tower: Could be any Tower
	char startTower;	
	//A letter representing the goal Tower: Must be different from startTower
	char goalTower;
	//A letter representing a temporary Tower: Must be different from startTower & goalTower	
	char tempTower;	
 
	std::cout<<"How many pegs should the starting Tower have?" <<std::endl;
	std::cin>>noPegs;
	std::cout<<"\nEnter the staring Tower (e.g. S): "<<std::endl;
	std::cin>>startTower;
	std::cout<<"\nEnter the goal Tower (e.g. G): "<<std::endl;
	std::cin>>goalTower;
	std::cout<<"\nEnter the temporary Tower (e.g. T): "<<std::endl;
	std::cin>>tempTower;
 
	//Find the right sequence to solve the towers of Hanoi problem using a recursive function
	GetCorrectMoveSequence(noPegs,startTower,goalTower,tempTower);
 
	return 0;
}
#include <iostream>

void GetCorrectMoveSequence (int n, char startT, char goalT, char tempT)
{
	if (n == 1) //the base case of the recursion
	{
		std::cout<<"Move peg 1 from Tower: "<<startT
			<<" to Tower: "<< goalT <<std::endl;
	}
	else		//The recursive part
	{
		GetCorrectMoveSequence(n-1, startT, tempT, goalT); //WATCH HOW THE ORDER CHANGES
		std::cout<<"Move peg "<< n <<" from Tower: "<<startT
			<<" to Tower: "<< goalT <<std::endl;
		GetCorrectMoveSequence(n-1, tempT, goalT, startT); //WATCH HOW THE ORDER CHANGES AGAIN..
	}
}

int main()
{
	//The number of pegs
	int noPegs;
	//A letter representing the starting Tower: Could be any Tower
	char startTower;	
	//A letter representing the goal Tower: Must be different from startTower
	char goalTower;
	//A letter representing a temporary Tower: Must be different from startTower & goalTower	
	char tempTower;	
	
	std::cout<<"How many pegs should the starting Tower have?" <<std::endl;
	std::cin>>noPegs;
	std::cout<<"\nEnter the staring Tower (e.g. S): "<<std::endl;
	std::cin>>startTower;
	std::cout<<"\nEnter the goal Tower (e.g. G): "<<std::endl;
	std::cin>>goalTower;
	std::cout<<"\nEnter the temporary Tower (e.g. T): "<<std::endl;
	std::cin>>tempTower;

	//Find the right sequence to solve the towers of Hanoi problem using a recursive function
	GetCorrectMoveSequence(noPegs,startTower,goalTower,tempTower);

	return 0;
}

and I am leaving it to u to find how the recursion function works in this code, and thus should work in yours too.
Have fun

A tested output is:

•

How many pegs should the starting Tower have?
5

Enter the staring Tower (e.g. S):
S

Enter the goal Tower (e.g. G):
G

Enter the temporary Tower (e.g. T):
T
Move peg 1 from Tower: S to Tower: G
Move peg 2 from Tower: S to Tower: T
Move peg 1 from Tower: G to Tower: T
Move peg 3 from Tower: S to Tower: G
Move peg 1 from Tower: T to Tower: S
Move peg 2 from Tower: T to Tower: G
Move peg 1 from Tower: S to Tower: G
Move peg 4 from Tower: S to Tower: T
Move peg 1 from Tower: G to Tower: T
Move peg 2 from Tower: G to Tower: S
Move peg 1 from Tower: T to Tower: S
Move peg 3 from Tower: G to Tower: T
Move peg 1 from Tower: S to Tower: G
Move peg 2 from Tower: S to Tower: T
Move peg 1 from Tower: G to Tower: T
Move peg 5 from Tower: S to Tower: G
Move peg 1 from Tower: T to Tower: S
Move peg 2 from Tower: T to Tower: G
Move peg 1 from Tower: S to Tower: G
Move peg 3 from Tower: T to Tower: S
Move peg 1 from Tower: G to Tower: T
Move peg 2 from Tower: G to Tower: S
Move peg 1 from Tower: T to Tower: S
Move peg 4 from Tower: T to Tower: G
Move peg 1 from Tower: S to Tower: G
Move peg 2 from Tower: S to Tower: T
Move peg 1 from Tower: G to Tower: T
Move peg 3 from Tower: S to Tower: G
Move peg 1 from Tower: T to Tower: S
Move peg 2 from Tower: T to Tower: G
Move peg 1 from Tower: S to Tower: G