1. Calculate the total number of moves required i.e. "pow(2, n)- 1". Here n is number of disks. 2. If number of disks (i.e. n) is even then interchange destination pole and auxiliary pole. 3. for i = 1 to total number of moves: if i%3 == 1: legal movement of top disk between source pole and destination pole if i%3 == 2: legal movement top disk between source pole and auxiliary pole if i%3 == 0: legal movement top disk between auxiliary pole and destination pole
This is an iterative solution to the Towers of Hanoi problem. I tried to prove this algorithm through some ways such as:
Induction on the number of disks(
n) for both the odd and even case: Show correctness for the base case, make the inductive hypothesis for some
n=kand then prove that it is valid when
n=k+2. This would require us to show that the remaining
pow(2,k+2)-pow(2,k)=3*pow(2,k)steps of the algorithm give the correct output for the case
n=k+2.However, the number of steps in the inductive extension depends on the parameter
kand is itself 3 times more than that in the base case
Induction on the number of iterations in the for loop.I tried to show that if disc movements for some
k+2iterations occur as stated by the algorithm, then the
k+3iteration should execute the same condition as was executed by the
k+1iteration. However, proving by this method seemed long and tedious as the
kth iteration can satisfy the first, second or the third condition and we need to prove for both the odd and the even case.
Could you help me out in proving this iterative solution to the Towers of Hanoi problem?