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.

Answer 2

antti.huima's solution is essentially correct, but I wanted something more rigorous, and it was too big to fit in a comment. Here goes:

First note: at the middle step x = 2^N-1 of this algorithm, the "from" peg is 0, and the "to" peg is 2^N % 3. This leaves 2^(N-1) % 3 for the "spare" peg. This is also true for the last step of the algorithm, so we see that actually the authors' algorithm is a slight "cheat": they're moving the disks from peg 0 to peg 2^N % 3, rather than a fixed, pre-specified "to" peg. This could be changed with not much work.

The original Hanoi algorithm is:

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

Plugging in "from" = 0, "to" = 2^N % 3, "spare" = 2^N-1 % 3, we get (suppressing the %3's):

hanoi(0, 2**N, 2**(N-1), N): (a)   hanoi(0, 2**(N-1), 2**N, N-1) (b)   move(0, 2**N) (c)   hanoi(2**(N-1), 2**N, 0, N-1) 

The fundamental observation here is: In line (c), the pegs are exactly the pegs of hanoi(0, 2^N-1, 2^N, N-1) shifted by 2^N-1 % 3, i.e. they are exactly the pegs of line (a) with this amount added to them.

I claim that it follows that when we run line (c), the "from" and "to" pegs are the corresponding pegs of line (a) shifted by 2^N-1 % 3. This follows from the easy, more general lemma that in hanoi(a+x, b+x, c+x, N), the "from and "to" pegs are shifted exactly x from in hanoi(a, b, c, N).

Now consider the functions
f(x) = (x & (x-1)) % 3
g(x) = (x | (x-1)) + 1 % 3

To prove that the given algorithm works, we only have to show that:

• f(2^N-1) == 0 and g(2^N-1) == 2^N
• for 0 < i < 2^N, we have f(2^N - i) == f(2^N + i) + 2^N % 3, and g(2^N - i) == g(2^N + i) + 2^N % 3.

Both of these are easy to show.