How does this iterative Tower of Hanoi work? FROM

Question

Possible duplicate:
How it works? Weird towers of hanoi solution

While surfing Google, I found this interesting solution for Tower Of Hanoi, which does not even use the stack as a data structure.

Can someone explain to me briefly what he is actually doing?

Is this decision acceptable?

the code

#include <stdio.h> #include <stdlib.h> int main() { int n, x; printf("How many disks?\n"); 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 does hardcoded number 3 do there?

Answer 1

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 mainly 2 for power n, 16 for 4 drives.

If you go through this sequence manually, you should see the progress of the disks. http://library.ust.hk/images/highlights/Tower_of_Hanoi_4.gif

Answer 2

This is one of the binary solutions for the Tower of Hanoi, there is a detailed explanation of this algorithm on Wikipedia - read the paragraph "Binary solution" .