Thread: 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!

You may want to try using a stack. :P stack - C++ Reference