Towers of Hanoi Starting From Initial (Legal) Configuration?

Question

I was recently asked in an interview how an algorithm for solving the classic Towers of Hanoi problem would differ if you were given an initial (legal) configuration of the towers, and had to start from there - in the middle so to speak. I could not differentiate the two, as I imagined simply stopping the traditional recursive solution in the middle would yield the correct behaviour. What am I missing?

Answer 1

You want to move the largest disk from, say, pole 1 to pole 2 (and then build the tower on top of that). To do that you need all smaller disks to be on pole 3.

That means, in particular, that you need to move the second largest disk to pole 3 from wherever it is (say pole 2). Therefore all smaller disks need to be on pole 1. And so on.

Answer 2

What if the given initial configuration wasn't a configuration in the sequence of configurations from the traditional recursive solution? For example, consider the graph of legal configurations for three disk game

(from http://en.wikipedia.org/wiki/Tower_of_Hanoi#Graphical_representation)

If you are trying to go from aaa to bbb, then the optimal solution takes you through the configurations along the side of the triangle connecting aaa and bbb. What would you do if you started at a configuration not one of the sides and you needed to get to bbb?