How to solve Tower of Hanoi iteratively?

Question

It may seem obvious to many but i am having a hard time figuring out the iterative solution to the Tower of Hanoi problem. There are some solutions on the Internet but without explanations. So can anybody give a sound explanation so that it becomes more intuitive and easy to reason.

Answer 1

You can transform the recursive solution to an iterative solution. To do this, create a stack that will contain items consisting of quadruples ("from", "to", "via", "num_disks"). For every function "call" in your recursive algorithm, push the parameters to a stack in the iterative algorithm. For every function "return" in your recursive algorithm, pop the parameters from the stack in the iterative algorithm.

Wikipedia has the complete iterative solution.

Answer 2

The iterative solution can be figured out analyzing the recursive solution. Two things worth notice are that:

1. Total no. of moves required are $2^n - 1$ where n is the number of disks. This can be evaluated by the recurrence of the recursive solution.

2. If the poles are arranged in space as:

   

then for the even number of disks the movement of disks will start in clockwise direction and if the number of disks is odd then the movement will start in anticlockwise direction.

With the help of above two observations we can devise the algorithm as:

TowerOfHanoi(source, destination, auxiliary, numDisks)

1. Calculate total no. of moves as pow(2, numDisks) - 1. numDisks is no. of disks. 

2. If numDisks is even then interchange the destination pole with the auxiliary pole. (This is to ensure that moves are in clockwise for even disks and anticlockwise for odd disks)

3. for i = 1 to number of moves calculate in step 1:

   a. if i%3 == 1:
      legal movement of top disk b/w source pole and destination pole.
   b. if i%3 == 2:
      legal movement of top disk b/w source pole and auxiliary pole.
   c. if i%3 == 0:
      legal movement of top disk b/w auxiliary pole and destination pole.

What is legal movement b/w two poles?

The legal movement must respect the constraints of the TOH problem i.e. no larger disk should be placed on smaller disk and we must move only the top disk at a time.

Cases for legal movement:

1. When one of the two poles is empty we must move the disk from non empty pole to the empty pole.

2. When the top disk of one pole is smaller than the other we move the smaller of two disks to the pole with larger disk.

Why the sub cases a, b, c of step 3 of the algorithm work?

We can think of them by starting the trivial cases when i = 1, 2 and 3.

For i = 1, since we have appropriately decided the sense of movement in step 2 of algorithm, we can safely make a legal movement b/w source and destination.

For i = 2, since the auxiliary pole is empty we can shift the disk to it and have a legal movement b/w source and auxiliary pole.

For i = 3, we need to make space for the remaining disks of source so that they could be shifted to the destination. To make space we must have a legal movement b/w auxiliary and destination pole.

After these three trivial steps, if we run through the algorithm we will notice that after every three moves, the destination pole is in a state that it can accept a new disk. So after every three moves, we can go with the other three moves and so on till we exhaust all our moves.

I know that more formally it may be proved with induction but it is enough to get an idea.

Answer 3

Try to visualize the solution mentioned in Navjot Singh's Answer.

Answer 4

I saw one solution to how to attack The problem here : https://www.equato.dk/hanoi.html