7

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

While surfing Google, i found this interesting solution to Tower Of Hanoi which doesn't even use stack as data structure.

Can anybody explain me in brief, what is it actually doing?

Are this solution really acceptable?

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 is the hard-coded number 3 doing in here?

EsmaeelE
  • 2,331
  • 6
  • 22
  • 31
TCM
  • 16,780
  • 43
  • 156
  • 254
  • 2
    It is using the standard 3 rods. – Matthew Flaschen May 20 '10 at 02:42
  • 1
    Does it report the correct sequence of moves? If so, it works, and there's no reason why it shouldn't be acceptable. However, you need to understand it before offering it as a solution to your homework, or you will be in trouble if you are called on to explain it, as you might very well be since it is so different from normal. – Jonathan Leffler May 20 '10 at 02:44
  • It is not my homework. I just accidently found this algorithm and thought to ask how does it actually work. – TCM May 20 '10 at 02:48
  • 2
    Exact duplicate: http://stackoverflow.com/questions/2209860/how-does-this-work-weird-towers-of-hanoi-solution – ergosys May 20 '10 at 02:53

2 Answers2

11

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. http://library.ust.hk/images/highlights/Tower_of_Hanoi_4.gif

Robert Harvey
  • 178,213
  • 47
  • 333
  • 501
6

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

chappjc
  • 30,359
  • 6
  • 75
  • 132
ZelluX
  • 69,107
  • 19
  • 71
  • 104