Solution of "Tower of Hanoi" When all disks are not in A

Question

As you know there are some ways to solve Tower of Hanoi, but they require all disks to be in one tower at the begining.

Now I wanna know is there any way to solve it, where the disks are already spread out randomly among the towers at the start.

Answer 1

Yes, it is still solvable (assuming that there are no large disks on top of smaller disks). For example:

        1
  4     2
  6     5     3
  -------------

Find the largest contiguous stack containing 1. Here, it is {1,2}. Move that stack onto the next largest disk, ignoring any others. You can use the standard Tower of Hanoi algorithm for this step.

              1
  4           2
  6     5     3
  -------------

Repeat steps above. Next contiguous stack containing 1 is now {1,2,3}. Move it onto 4

  1
  2
  3           
  4           
  6     5  
  -------------

Same thing -- move {1,2,3,4} onto 5.

        1
        2
        3     
        4     
  6     5    
  -------------

Move {1,2,3,4,5} onto 6 now, and you're done. If you need to move the whole stack to a specific peg, use the standard solution once more.