1
$\begingroup$
    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:

  1. 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=k and 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 k and is itself 3 times more than that in the base case

  2. Induction on the number of iterations in the for loop.I tried to show that if disc movements for some k,k+1 and k+2 iterations occur as stated by the algorithm, then the k+3 iteration should execute the same condition as was executed by the k+1 iteration. 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?

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.