# Iterative Towers of Hanoi

• 10-13-2002
Mister C
Iterative Towers of Hanoi
Allright,

It is well known what the Towers of Hanoi (TOH) problem is. It is known to have a recursive solution. I have many programs to demonstrate this. However, I am trying to find a non recursive solution to TOH. I myself have solved this problem in an algorithm analysis class (years ago!) but I cant find my code. Do any of you have a quick solution for this problem.

Thanks
• 10-13-2002
Prelude
>Do any of you have a quick solution for this problem.
The most straightforward solution is to use a stack to iteratively simulate recursion.

-Prelude
• 10-13-2002
Nick
There is an iterative non stack solution.
• 10-13-2002
Mister C
Stacks will work! Thanks
• 10-13-2002
Stoned_Coder
Code:

```#include <stdio.h> #include <stdlib.h> int main() {   int n, x;   printf( "How many disks? " );   scanf( "%d", &n );   printf("\n");   for (x=1; x < (1 << n); x++)       printf( "move from tower %i to tower %i.\n",                 (x&x-1)%3, ((x|x-1)+1)%3 ); return 0; }```
found in 30 secs with google!
• 10-13-2002
Mister C
Thanks- I was trying to use a data structure to solve the problem. A stack is the ideal data structure. Also, your code was in C- doesn't matter though.
• 10-13-2002
*ClownPimp*
I wanna be like Stoned_Coder when I grow up!
• 10-13-2002
*ClownPimp*
>found in 30 secs with google!
oops, didnt notice that the first time...
• 04-10-2009
tonn
Quote:

Originally Posted by Stoned_Coder
Code:

```#include <stdio.h> #include <stdlib.h> int main() {   int n, x;   printf( "How many disks? " );   scanf( "%d", &n );   printf("\n");   for (x=1; x < (1 << n); x++)       printf( "move from tower %i to tower %i.\n",                 (x&x-1)%3, ((x|x-1)+1)%3 ); return 0; }```
found in 30 secs with google!

Hello!
Sry about diving out so old subject, but i need some answers about that code. Could somebody explane what that printf( "move from tower %i to tower %i.\n",
(x&x-1)%3, ((x|x-1)+1)%3 ); exactly mean. I can understand that it writes how rings have to move one pole to another pole but i need to know more of that, how that code knows, when but rings in the second or third pole?
And another questions is, can it works in C too, i mean not only in C++?
I apologize for my bad English and i going to wait to get some answers :).
• 04-10-2009
BuzzBuzz
Quote:

Originally Posted by tonn

And another questions is, can it works in C too, i mean not only in C++?

That is C code.

%i is the C code way of outputting an integer variable value, in C++ you'd write something like:
Code:

``` C version: printf( "move from tower %i to tower %i.\n" C++: cout << "move from tower" tower[i] << "to tower" << tower[i] << endl;```
• 04-11-2009
tonn
Ok thanks! I deduce that too. But still there is a question about: printf( "move from tower %i to tower %i.\n",
(x&x-1)%3, ((x|x-1)+1)%3 ); how the rings move on the poles. I think its something to do with bit operations, like in here Tower of Hanoi - Wikipedia, the free encyclopedia Binary solutions subject. But i really cant understand that text its too complicated to me. Could somebody help?