(recall that given a configuration A, we denote by A' the configuration A with the smallest disk removed. A path from A to B yields a path from A' to B' by ignoring the smallest disk, and a path from A' to B' yields a path from A to B by inserting moves of the smallest disk between every two moves as needed, possibly starting and/or ending with a move of the smallest disk)

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.

Unfortunately, this is false. There are sensible paths from (12, , 3) to (3,1,2) of lengths 6 and 7. The lemma that is true is this: Any path from A to B that is either a shortest path, or within 1 in length from a shortest path, is derived from a path from A' to B' that is either shortest, or within 1 of being shortest. Since a path from A' to B' of length N produces a path from A to B of length N, N+1, or N+2, a path from A' to B' that is two longer than the shortest path produces a path from A to B that is also at least two longer than the shortest path. This proves the lemma. So instead of "try to find the shortest path from A to B", the correct task is "try to find all paths that are within 1 of being the shortest path from A to B". Since these can be quickly produced out of all the paths that are within 1 of being the shortest path from A' to B', the shortest and near-shortest paths can be found by a simple recursive algorithm (and the near-shortest paths that you didn't care about can then be discarded). -- Andy.Latto@pobox.com