Iterative Towers of Hanoi

[Mister C]

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

[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

[Nick]

There is an iterative non stack solution.

[Mister C]

Stacks will work! Thanks

[Stoned_Coder]

#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!

[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.

[*ClownPimp*]

I wanna be like Stoned_Coder when I grow up!

[*ClownPimp*]

>found in 30 secs with google!
oops, didnt notice that the first time...

[tonn]

#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 .

[BuzzBuzz]

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:

C version: printf( "move from tower %i to tower %i.\n"

C++: cout << "move from tower" tower[i] << "to tower" << tower[i] << endl;

[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?