Questions:

1. Starting any two of these 3^n states -- say A and B -- can B be reached from A by a sequence of legal moves? (If not, for which A, B is this possible?)

Yes. Proof by induction on the number of disks. Let A' and B' be the states A and B with the smallest disk removed. Take the shortest path from A' to B', which exists by the inductive hypothesis. A path from A to B is given by performing the moves in this path, moving the shortest disk out of the way between every two moves, and possibly moving the smallest disk initially to allow the first move, and possibly moving the smallest disk afterwards to produce configuration B'.

2. When state B can be legally reached from state A, what is an algorithm for using the fewest moves to do this?

Assume that the shortest path from A' to B' takes k moves. The above algorithm will yield a path from A to B that takes either K, K+1, or K+2 moves. Is this minimal? I think so, but I can't quite prove it. Consider the shortest path from A to B. The smallest disk must be moved every other turn, since two consecutive moves that don't touch the smallest disk undo each other, and can be omitted to yield a shorter path. Ignoring the smallest disk yields a path from A' to B'. So we have a bidirectional map from paths from A' to B' to maps from A to B. A longer path from A' to B' can never map to a shorter path from A to B, since if K1 > K2, (K1+N1) >= (K2 + N2) for N1, N2 in {0,1,2}. This is almost, but not quite enough to show that the above construction always produces the shortest path. Can this actually happen?

From (3, , 2) to (2, ,3), there are two different paths of length 3. One produced by ignoring disk 2, and finding the shortest path for disk 3, and one produced from a longer path of disk 3. (in other words, you can move either disk to the center first). So the algorithm "Find the shortest path ignoring the smallest disk, and extend it by moving the smallest disk appropriately" finds *a* shortest path in this case, but it doesn't find *all* shortest paths. But now if we want to find a path from

(3, , 12) to (12, ,3), then the solution produced recursively by the "ignore the smallest disk, and interleave with appropriate moves of the smallest disk" produces a solution of length 7, but there is a solution of length 5. I suspect, though I don't have a proof, that this is the only case where the above recursive algorithm fails. That is, I think that the above recursive procedure, applied until you are down to the 3 largest disks, and finding the shortest path for the three largest disks, will always yield the shortest path. Define a "sensible" path as one that doesn't move the same disk twice in a row. Any shortest path from A to B is always an extension of a sensible path from A' to B'. I guess what I need to prove is this: With 3 or more disks, any sensible path that is not the unique shortest path is at least 2 moves longer than the shortest path. Prove this by tedious enumeration for N=3, and by induction for larger values. So I think that the shortest path is always found by using the inductive argument until N gets down to 3, then finding the shortest path for the biggest 3 disks. The above proof is kind of rambling, since I started out trying to prove something false, and then patched it up as I found the correct statement, but I think it's correct. -- Andy.Latto@pobox.com