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!
