3

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?

Rome_Leader
  • 381
  • 1
    I don't know if I understand you correctly but legal configuration does not imply that it has to a intermediate configuration of the optimal path from the standard initial configuration where all discs are on the left stack. Legal configuration only implies that no larger disc is placed on a smaller one but there are still many legal configurations that do not occur as an intermediate step. – hickslebummbumm Nov 04 '14 at 15:59
  • You are correct. It simply means that no larger disk is atop a small one, but may not necessarily be a step in the traditional recursive solution. The picture below has helped me in understanding that, but I'm still not sure how the algorithm would look exactly. – Rome_Leader Nov 04 '14 at 21:01
  • There might be something more elegant, but you could always try a breadth first search. – Randy E Nov 05 '14 at 01:58

2 Answers2

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

enter image description here

(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?

Randy E
  • 989
  • 5
  • 10
  • This isn't exactly a Tower of Hanoi problem anymore, though. In the original ToH problem, you just have to move all of the disks from one peg to another peg. The way I described it, a destination peg is specified. To make it closer to the original puzzle, you would be given some legal configuration and just have to put all disks onto some peg (legally, of course), but it doesn't matter which one. – Randy E Nov 04 '14 at 16:11
  • Your description should be close enough though, and I think makes the point clearly - the algorithm will move you from one corner of the triangle to another in a straight line, but your picture explicitly shows the $6$ (at least once you label the pegs) legal configurations that don't occur as a stage in the traditional recursive solution. (And if you increase the number of disks, more such arrangements exist). – mdp Nov 04 '14 at 16:26
2

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.

Arthur
  • 199,419