Month: May 2015

If you’ve taken courses in computer sciences, you probably know the Tower Of Hanoi algorithm. The task is to move a tower of discs from the source rod the the destination using an auxiliary rod. Each disc should be placed on a bigger one all the time.
The solution is to move all discs on top of the biggest one to the auxiliary rod, then move the biggest disc to the destination rod and then move all the rest to the destination (according to the rules of course, and one disc at a time).

The Recursive (and Naive) Solution

The function that moves n discs from src to dst using aux looks like:

function moveDiscs(n, src, dst, aux){
  if (n > 1)
    moveDiscs(n-1, src, aux, dst);
  print("Move from " + src + " to " + dst);
  if (n>1)
    moveDiscs(n-1, aux, dst, src);
}

We’ll use that function later to prove that the non-recursive algorithm does the same.

The Iterative Solution

A naive iterative solution is to use a binary search and find for each move of a disc, the parameters passed to moveDiscs when n=1. This is crazy! We don’t want time complexity o(n) just to move the first disc.
Let’s look at a better solution:
Repeat the 3 steps in table 1 until all discs are moved, depending on the value of n:

Table 1:

Note: perform no more step after all discs have been moved to the destination.

Proof

For n = 1, just move a disc from src to dst
For n = 2, take a look at the recursive function.
For n ≥ 3:
The total number of moves is 2ⁿ – 1
Let’s assume our algorithm works for any natural number n and prove for n+1:

Steps 1 thru 2ⁿ – 1

Let’s look at the first call to moveDiscs inside itself:

moveDiscs(n-1, src, aux, dst); // Remember that we prove for `n+1`, so `n-1` in the function actually means `n`

Let’s look how it is performed:
Per our assumption, the sequence for steps 1 thru 2ⁿ – 1 is

Because if n is odd, n+1 is even and vice versa, we get that the first steps are performed correctly by the iterative algorithm

Step 2ⁿ

This is when we move a disc from src to dst
If n is even, 2ⁿ≡1 mod 3, thus it matches step 1 in Table 1 for odd n+1.
If n is odd, 2ⁿ≡2 mod 3, thus it matches step 2 in Table 1 for even n+1.
Thus, our iterative algorithm is still correct.

Steps 2ⁿ + 1 Thru 2ⁿ⁺¹ – 1

Those steps are performed by the second call to moveDiscs inside itself:

moveDiscs(n-1, aux, dst, src); // Remember that we prove for `n+1`, so `n-1` in the function actually means `n`

In this table we see the steps that follow step 2ⁿ.
Thus, the algorithm works correctly for the last part, and thus our whole algorithm is correct.

You can now watch a working Hanoi animation here.