How does this work? Weird Towers of Hanoi Solution

Question

I was lost on the internet when I discovered this unusual, iterative solution to the towers of Hanoi:

for (int x = 1; x < (1 << nDisks); x++)
{
     FromPole = (x & x-1) % 3;
     ToPole = ((x | x-1) + 1) % 3;
     moveDisk(FromPole, ToPole);
}

This post also has similar Delphi code in one of the answers.

However, for the life of me, I can't seem to find a good explanation for why this works.

Can anyone help me understand it?

Answer 1

the recursive solution to towers of Hanoi works so that if you want to move N disks from peg A to C, you first move N-1 from A to B, then you move the bottom one to C, and then you move again N-1 disks from B to C. In essence,

hanoi(from, to, spare, N):
  hanoi(from, spare, to, N-1)
  moveDisk(from, to)
  hanoi(spare, to, from, N-1)

Clearly hanoi( _ , _ , _ , 1) takes one move, and hanoi ( _ , _ , _ , k) takes as many moves as 2 * hanoi( _ , _ , _ , k-1) + 1. So the solution length grows in the sequence 1, 3, 7, 15, ... This is the same sequence as (1 << k) - 1, which explains the length of the loop in the algorithm you posted.

If you look at the solutions themselves, for N = 1 you get

FROM   TO
          ; hanoi(0, 2, 1, 1)
   0    2    movedisk

For N = 2 you get

FROM   TO
          ; hanoi(0, 2, 1, 2)
          ;  hanoi(0, 1, 2, 1)
   0    1 ;   movedisk
   0    2 ;  movedisk
          ;  hanoi(1, 2, 0, 1)
   1    2 ;   movedisk

And for N = 3 you get

FROM   TO
          ; hanoi(0, 2, 1, 3)
          ;  hanoi(0, 1, 2, 2)
          ;   hanoi(0, 2, 1, 1)
   0    2 ;    movedisk
   0    1 ;   movedisk
          ;   hanoi(2, 1, 0, 1)
   2    1 ;    movedisk
   0    2 ;  movedisk ***
          ;  hanoi(1, 2, 0, 2)
          ;   hanoi(1, 0, 2, 1)
   1    0 ;    movedisk
   1    2 ;   movedisk
          ;   hanoi(0, 2, 1, 1)
   0    2 ;    movedisk

Because of the recursive nature of the solution, the FROM and TO columns follow a recursive logic: if you take the middle entry on the columns, the parts above and below are copies of each others, but with the numbers permuted. This is an obvious consequence of the algorithm itself which does not perform any arithmetics on the peg numbers but only permutes them. In the case N=4 the middle row is at x=4 (marked with three stars above).

Now the expression (X & (X-1)) unsets the least set bit of X, so it maps e.g. numbers form 1 to 7 like this:

   1 ->  0
   2 ->  0
   3 ->  2
   4 -> 0 (***)
   5 ->  4 % 3 = 1
   6 ->  4 % 3 = 1
   7 ->  6 % 3 = 0

The trick is that because the middle row is always at an exact power of two and thus has exactly one bit set, the part after the middle row equals the part before it when you add the middle row value (4 in this case) to the rows (i.e. 4=0+4, 6=2+6). This implements the "copy" property, the addition of the middle row implements the permutation part. The expression (X | (X-1)) + 1 sets the lowest zero bit which has ones to its right, and clears these ones, so it has similar properties as expected:

   1 ->  2
   2 ->  4 % 3 = 1
   3 ->  4 % 3 = 1
   4 -> 8 (***) % 3 = 2
   5 ->  6 % 3 = 0
   6 ->  8 % 3 = 2
   7 ->  8 % 3 = 2

As to why these sequences actually produce the correct peg numbers, let's consider the FROM column. The recursive solution starts with hanoi(0, 2, 1, N), so at the middle row (2 ** (N-1)) you must have movedisk(0, 2). Now by the recursion rule, at (2 ** (N-2)) you need to have movedisk(0, 1) and at (2 ** (N-1)) + 2 ** (N-2) movedisk (1, 2). This creates the "0,0,1" pattern for the from pegs which is visible with different permutations in the table above (check rows 2, 4 and 6 for 0,0,1 and rows 1, 2, 3 for 0,0,2, and rows 5, 6, 7 for 1,1,0, all permuted versions of the same pattern).

Now then of all the functions that have this property that they create copies of themselves around powers of two but with offsets, the authors have selected those that produce modulo 3 the correct permutations. This isn't an overtly difficult task because there are only 6 possible permutations of the three integers 0..2 and the permutations progress in a logical order in the algorithm. (X|(X-1))+1 is not necessarily deeply linked with the Hanoi problem or it doesn't need to be; it's enough that it has the copying property and that it happens to produce the correct permutations in the correct order.