Towers of Hanoi solution better than O(2^n)?

Given that solving Towers of Hanoi always takes 2^n - 1 steps...no, you're not going to find a faster algorithm, because it takes O(2^n) just to print out the steps, much less compute them.

The solution to the Towers of Hanoi is inescapably 2ⁿ. In a dynamic programming solution, however, each subproblem is computed only once, and then the problem is solved by combining the first subproblem solution, the current disk move, and the second subproblem solution.

Thus there are two components in generating each solution: allocating the memory for the present solution, and then filling that memory. Memory allocation is approximately independent of the size of the memory allocated and is the expensive component. Memory copy is linear in the size of memory copied, which, though fast, is exponential in n as a solution to the Towers.

Time = c₁*n + c₂*2ⁿ, where c₁ >> c₂. I.e., it starts linear and ends exponential.

Link to article appearing in ACM's SIGCSE Inroads magazine (September 2012)

I will not prove (as Stephen did), but i will try to explain intuitively that 2^n-1 are min: In every state, there are only three possible moves for the disks. Let represent the current state as ordered seq (1, 1, .. , 1) such that the first number says where the largers disk is, and the last number says where the smallest disk is. (1, 1, .., 1) means all the disks are on at position 1. Also from (1, 1, ..1) there are only two descending states: (1, 1, ... 2) and (1, 1, .... 3). From (1, 1, ... 2) there are three descending states:

1. Go back to (1, 1, .. 1)
2. goto (1, 1, ..., 3)
3. goto (1, 1,...3, 2)

If you continue, you will get graph for which the nodes are the possible states and the edges (transitions) are "disk moves".

You will get image like shown below (if you continue, it will look like triangle and at the vertices will be (1, 1, ...1), (2, 2, ..2), (3, 3, ...3)). The number of steps is actually the path in the graph.

If you walk along the edge on the triangle, the number of steps in 2^n-1. All other paths are the same length or longer.

If you use the strategy: Move all the disks except the largest to place 3, then move the larges to place 2, and finally move all form 3 to 2, formula can be devised in the following way:

f(n) =
f(n -1) // move all except largest from 1 to 3
+ 1 // move largest from 1 to 2
+ f(n -1) // move all from 3 to 2
->
f(n) = 1+ 2 * f(n-1)

the solution of that recurrent equation gives you the number of steps required by that strategy (which happens to be the minimum number of steps)