Towers of Hanoi using stack

This is a discussion on Towers of Hanoi using stack within the C++ Programming forums, part of the General Programming Boards category; Hi, i am trying to convert the basic recursive function for hanoi into a non recursive function using a stack ...

  1. #1
    Registered User
    Join Date
    Jun 2011
    Posts
    1

    Towers of Hanoi using stack

    Hi, i am trying to convert the basic recursive function for hanoi into a non recursive function using a stack to hold the pending moves.
    The recursive function for moving all discs from tower a to b is:
    Code:
    void hanoi(int n, char a, char b, char c)
              {
                if(n==1)
                 {
                   cout << "Move disc from tower " << a << " to " << b << endl;
                 }
                   else {
                            hanoi(n-1, a, c, b);
                            cout << "Move disc from tower " << a << " to " << b << endl;
                            hanoi(n-1, c, b, a);
                          }
              }
    the output for n = 3 is:

    move disk from tower a to b
    move disk from tower a to c
    move disk from tower b to c
    move disk from tower a to b
    move disk from tower c to a
    move disk from tower c to b
    move disk from tower a to b

    My "work in progress" code using stack is:
    Code:
    int main()
    {
    	vector <char> stack;
    	int n = 3;
    	int rings = 3;
    	char from = 'a';
    	char to = 'b';
    	char with = 'c';
    	char temp = ' ';
    	
    	int ret = 1;
    	int w = 0;    //moves
    	int moves = (pow (2, n) - 1);  //expected moves(2^n) - 1
    	
            while(w <= moves)              
    	{
    		if(ret == 1)
    		{
    	       	   do
             	   {  
    		    stack.push_back(to);
                        stack.push_back(from);
    		     temp = to;
    		     to = with;
    		     with = temp;
    		     from = from;
    		    
    		     ret = 2;
    		     n--;
    		   }while(n >= 1);
    	 	   
    		 }
    
    		 if( ret == 2)
    		  {
    		     
    	  	        cout << "move ring from tower " << stack.back();
    		        stack.pop_back();
    		        cout << " to tower " << stack.back() << endl;
    		       stack.pop_back();
    		        w++;
    			if(w >= moves)
    			{
    			  break;
    			}
    		        ret = 3;
    		       
    		   }   
    		  
    		  if(ret == 3)
    		   {
    		     cout << "move ring from tower " << stack.back();
    		     stack.pop_back();
    		     cout << " to tower " << stack.back() << endl;
    		     stack.pop_back();
    		     w++;
    		     temp = with;
    		     with = from;
    		     from = temp;
    		    
    		     to = to;
    		     n = rings;
    		     ret = 1;
    		    }
    		}
    	}
    I get an output of:

    move ring from tower a to tower b
    move ring from tower a to tower c
    move ring from tower b to tower c
    move ring from tower b to tower a
    move ring from tower c to tower a
    move ring from tower c to tower b
    move ring from tower a to tower b

    Could somebody point out what i'm doing wrong, or point me in the right direction? I can't figure this problem out for the life of me. THANKS!

  2. #2
    Password:
    Join Date
    Dec 2009
    Location
    NC
    Posts
    587
    You may want to try using a stack. :P stack - C++ Reference

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Towers of Hanoi (need help)
    By Loudan in forum C++ Programming
    Replies: 3
    Last Post: 01-30-2006, 09:17 PM
  2. Towers of Hanoi
    By cyberCLoWn in forum C++ Programming
    Replies: 6
    Last Post: 01-15-2004, 03:28 PM
  3. Help on The Towers of Hanoi
    By momegao in forum C++ Programming
    Replies: 3
    Last Post: 04-13-2003, 03:40 PM
  4. The Towers of Hanoi
    By awkeller in forum C Programming
    Replies: 7
    Last Post: 01-07-2002, 06:07 AM
  5. Towers of Hanoi
    By janehung in forum C Programming
    Replies: 12
    Last Post: 01-07-2002, 05:40 AM

Tags for this Thread


1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21