The iterative solution can be figured out analyzing the recursive solution. Two things worth notice are that:
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.
If the poles are arranged in space as:
[![Tower of Hanoi poles in space][1]][1]
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:
When one of the two poles is empty we must move the disk from non empty pole to the empty pole.
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.
