I heard of this problem before and this is the solution I remember:
Suppose there are ‘n’ disks then we know the number of movements
needed are f(n) = 2*f(n-1)+1 = 2n – 1.
Now let’s see the pattern of movements for different ‘n’. The
disk that is moved is printed out.
n = 1 1
n = 2 1 2 1
n = 3 1 2 1 3 1 2 1
n = 4 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1
We note that the n’th disk will be moved only once and that too to
the right. But the (1…n-1) group is moved twice and hence (n-1)th
disk is moved twice, similarly (n-2)th disk is moved 4 times etc.
So we have disk 1 moved 2^(n-1) times and disk 2 moved 2^(n-2) times
… disk n moved 2^0 times.
We also observe that n’th disk is moved only after the (1…n-1)
group is moved and then this group is moved again. So n’th disk will
be in the middle of the all the disks moved. Similarly, (n-1)th disk
will be in the middle of both groups to the left and right of n’th
disk etc. Take the example of n=4, and we have 4, at the middle and 3
at the middle of list to the left of 4 and in the middle of the list to
the right of 4.
So nth disk is moved at step 2^(n-1)
(n-1)th disk is moved at steps 2^(n-2) and 2^(n-1)+2^(n-2)
(n-2)th disk is moved at steps 2^(n-3), 2^(n-2)+2^(n-3),
2^(n-1)+2^(n-3), 2^(n-1)+2^(n-2)+2^(n-3)
etc
Which put in another way,
nth disk is moved at step 2^(n-1)
(n-1)th disk is moved at steps 2^(n-2)*1, 2^(n-2)*3
(n-2)th disk is moved at steps 2^(n-3)*1, 2^(n-3)*3, 2^(n-3)*5,
2^(n-3)*7
etc
And hence this:
At k’th step disk ‘l+1’ is moved where ‘l’ is the largest
number such that 2^l divides k.
Now the question is where the disk is moved. Since there are only three
towers, we can denote the movement to be either to the left or to the
right. Also observe that n’th disk which is the largest is moved to
the right if we want final solution to be from A to B, the n’th disk
is moved from A to B which is to the right. If we wanted to move the
whole group to the left say from A to C, the n’th disk would have
been moved to the left. Now in order to solve (1…n) group problem
we’ll move n’th disk to right but before that the sub problem of
moving (1…n-1) from A to C needs to be solved, applying same argument
we move (n-1)th disk left, similarly (n-2)th right etc. Observe that
after (1…n-1) is solved and n’th disk moved, we need to solve
(1…n-1) again but this time from disk C to B which is to the left
again and hence (n-1)th disk will be moved to the left again. So the
result is that d’th disk is moved right if (n-d) is even and moved
left if (n-d) is odd.
The pseudo code looks like this:
for (int I = 0; I < 2^n-2; ++I )
{
Find ‘k’ such that 2^(k-1) divides I.
Direction to be moved : right if (n-k) is even else left
Move disk ‘k’ to the direction above
}
To find the greatest m such that 2^(m-1) divides given 'i', note that
mth digit of 'i' is 1 and all the 1 ... (m-1) digits of 'i' are 0.
Hence 2^(m-1) = i & (~i + 1).
