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

Question

Is there a solution for Towers of Hanoi whose running time is less than O(2ⁿ) where n is the number of disks to move? My solution takes O(2ⁿ) time.

Also, the below solution is with recursion. Can we use Dynamic Programming with the concept of memoization to solve this in a lesser time?

public void towersOfHanoi(
        int num, 
        MyStack<Integer> from,
        MyStack<Integer> to, 
        MyStack<Integer> spare
) {
    if (num == 1) {
        int i = from.pop();
        to.push(i);
        System.out.println("Move "+i+" from "+from.getName()+" to " + to.getName());
        return;
    }
    towersOfHanoi(num - 1, from, spare, to);
    towersOfHanoi(1, from, to, spare);
    towersOfHanoi(num - 1, spare, to, from);
}

MyStack is an extended version of Stack class in Java that adds a name field and accessor.

Also, are there any variations of the same problem?

Answer 1

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.

Answer 2

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)