views:

508

answers:

2

Possible Duplicate:
How does this work? Weird Towers of Hanoi Solution

Hello, while surfing google, i found this interesting solution to Tower Of Hanoi which doesn't even use stack. Can anybody explain me in brief, what is it actually doing? And this solution really acceptable?

#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;
}

Update :- what is the hardcoded number 3 doing in here?

+3  A: 

It is one of the binary solutions to Tower of Hanoi, there is a detailed explanation of this algorithm on Wikipedia.

Link for your convenience: http://en.wikipedia.org/wiki/Tower_of_Hanoi#Binary_solutions

ZelluX
+3  A: 

Might be easier to see in PSEUDOCODE:

GET NUMBER OF DISKS AS n
WHILE x BETWEEN 1 INCLUSIVE AND 1 LEFT-SHIFTED BY n BITS
    SUBTRACT 1 FROM n, DIVIDE BY 3 AND TAKE THE REMAINDER AS A
    OR x WITH x-1, ADD 1 TO THAT, DIVIDE BY 3 AND TAKE THE REMAINDER AS B
    PRINT "MOVE FROM TOWER " A " TO TOWER " B
    ADD 1 TO x

1 LEFT SHIFTED BY n BITS is basically 2 to the power of n, 16 in the case of 4 disks.

If you walk through this sequence manually, you should see the progression of movement of the disks.

Robert Harvey
Thanks Harvey, this pseudocode is indeed easy to understand :). Great answer !
Ankit Rathod
Uh, "BETWEEN 1 AND n" is not at all the same as "for (x=1; x < (1 << n); x++)"
David Gelhar
@David: Thanks, fixed.
Robert Harvey