Tower of Hanoi problem - linear planning

Question

I'm doing an assignment about planning for tower of Hanoi problem using linear planning and I'm not allowed to use any recursive functions. The matter is that my solution is not optimal like the one from recursive method. It produces redundant steps. For example:

I have 3 rods named A, B, C respectively and there are 2 disks named 1, 2 (disk 1 is smaller than disk 2, disk 1 is on disk 2), then there are 2 ways to move all the disks from rod A to rod C using rod B as intermediate rod as follow:

1. (optimal like the output of recursive algorithm)
   • Move disk 1 to rod B
   • Move disk 2 to rod C
   • Move disk 1 to rod C
2. (non optimal using planning)
   • Move disk 1 to rod C
   • Move disk 2 to rod B
   • Move disk 1 to rod A
   • Move disk 2 to rod C
   • Move disk 1 to rod C

So how do I (more precise: an algorithm which can be programmable) know that disk 1 must move to rod B first instead of moving to disk C to gain optimal solution? I'll really appreciate your help. Thanks!

Answer 1

I wanted to visualize ratchet freak answer.

Example of size 5

Example of size 6

Larger sizes work the same way.

Additional details

• The task is to write Hamilton path algorithm implementation.
• There are 3 rods{initial, spare, destination}. Your starting move depends on reminder of 2 :
  • if n % 2 == 0, start with spare rod
  • if n % 2 == 1, start with destination rod
• It takes 2^n-1 moves, to move the whole stack to destination stack.

Answer 2

the key is knowing how many disks need to be moved:

it there are a even number of disks in the stack you start to the "spare" rod
if there are an odd number of disks in the stack you start to the "destination" rod