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)

Answer 3

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)

Answer 4

The standard towers of hanoi problem deals with 3 pegs.

However, if we have k-pegs, the time complexity would be O(2^(n/(k-2))).

I have solved this problem with 4 pegs and 5 pegs and time complexities resulted is O(2^(n/2)) and O(2^(n/3)) respectively

Answer 5

This one is about 7% faster than the recursive one. It store the moves in a list so you can use it after otherwise, you can put a print if you prefer and remove the container.

```
unsigned long i;  
static const int MAXNUMBEROFDISKS = 32;
vector<int> pow2Vec;
uint_fast32_t mPinFrom    = 0;
uint_fast32_t mNumDisk    = 0;
unsigned long numDiskLong = 0;
uint_fast32_t mOffset[MAXNUMBEROFDISKS];
uint_fast32_t mDir[MAXNUMBEROFDISKS]          = { 0 };
uint_fast32_t mPositionDisk[MAXNUMBEROFDISKS] = { 0 };
const uint_fast32_t mRedirectArr[5] = { 2, 0, 1, 2, 0 };




Algos::Algos()
{ 
  for (int i = 0; i < MAXNUMBEROFDISKS; ++i)
  {
    pow2Vec.push_back(pow(2, i));
    mOffset[i] = 1;
  }

  for (int i = 1; i < MAXNUMBEROFDISKS; i += 2)
  {
    mDir[i] = 2;
  }

  mOffset[0] = 0;
}




void Algos::calculListBinExperiment(vector<tuple<int, int, int>>& listeFinale, int nbDisk)
{
  listeFinale.resize(pow2Vec[nbDisk] - 1);
  _BitScanForward(&i, nbDisk);
  for (int noCoup = 1; noCoup < pow2Vec[nbDisk] ; ++noCoup)
  {
    _BitScanForward(&numDiskLong, noCoup);
    mNumDisk = numDiskLong;
    mPinFrom = mPositionDisk[mNumDisk];
    mPositionDisk[mNumDisk] = mRedirectArr[mPositionDisk[mNumDisk] + mDir[mNumDisk + 
    mOffset[i]]];
    listeFinale[noCoup - 1] = make_tuple(mNumDisk, mPinFrom, mPositionDisk[mNumDisk]);
  }
}
```