Solving Towers of Hanoi
 

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 ?

Re: Solving Towers of Hanoi
 

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.

Re: Solving Towers of Hanoi
 

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):

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.

Re: Solving Towers of Hanoi
 

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:

#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 :D :D :D

A tested output is: