Tower Of Hanoi Without Recursion

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:

If n is even If n is odd
perform a legal move between src and aux perform a legal move between src and dst
perform a legal move between src and dst perform a legal move between src and aux
perform a legal move between aux and dst perform a legal move between aux and dst

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 2n – 1
Let’s assume our algorithm works for any natural number n and prove for n+1:

Steps 1 thru 2n – 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 2n – 1 is

If n is even If n is odd
perform a legal move between src and dst perform a legal move between src and aux
perform a legal move between src and aux perform a legal move between src and dst
perform a legal move between aux and dst perform a legal move between aux and dst

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 2n

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

Steps 2n + 1 Thru 2n+1 – 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`
If n is even If n is odd
perform a legal move between aux and src
(step 2 for odd n+1)
perform a legal move between aux and dst
(step 3 for even n+1)
perform a legal move between aux and dst
(step 3 for odd n+1)
perform a legal move between src and aux
(step 1 for even n+1)
perform a legal move between src and dst
(step 1 for odd n+1)
perform a legal move between src and dst step 2 for even n+1)

In this table we see the steps that follow step 2n.
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.

Advertisements