Recursion and "Towers of Hanoi"

Figure 1: rules of the Hanoi puzzle. Click to enlarge

I was thinking of my first algorithms class and remembered the "Towers of Hanoi" problem. This problem is used to introduce the concept of recursion. It can also use the stack data structure (LIFO) quite naturally, making it a universal favorite in assignments. An Internet search yields 1000's of websites discussing the problem. Heres adding yet another discussion to this timeless classic!

Problem Setup
Here is the setup and the rules of the Hanoi puzzle

1. There are 3 towers labeled 0,1, and 2.
2. There are N circular discs, each of different radius, that are initially placed around tower 0.
3. Any circular disc can only be placed above a disc of larger radius, or as the first disc of the tower.

The objective is to move the N discs from tower 0 to tower 2 following the rules mentioned above.

Figure 1 explains the problem graphically and shows the rules of the Hanoi puzzle.

Solution
In order to solve the puzzle recursively, look at Figure 2. The first requirement on moving the largest (red) disc from tower 0 (source tower) to tower 2 (destination tower) is that there should be no discs over this red disc. This means that the other 2 discs (green and yellow) should be moved to tower 1 (auxiliary tower) and the setup should be in state 1. Then, the red disc can be moved to tower 2 (state 2).

Now the problem is reduced to one with just 2 discs (yellow and green). These need to be moved from tower 1 (the source) to tower 3 (the destination) using tower 0 as a temporary go-between (auxiliary tower).

Figure 2: Top level steps. Click to enlarge

But wait, how do we accomplish the transition from state 0 to state 1?
Figure 3 shows the intermediate steps to accomplish this. The aim is to move the green and yellow discs from tower 0 (source) to tower 1 (destination) using tower 2 as the auxiliary tower.

Figure 3: Mini-steps from state 0 to state 1. Click to Enlarge

So the high-level idea is to have a function that recursively places the discs in the appropriate towers. This will be clear in the C++ "Hanoi" function shown below. I have used STL data-structures (vector and stack) in order to simplify the explanation.

#include <stack>
#include <vector>

#include <iostream>

using namespace std;

//Each Tower is a Stack (LIFO)
vector <stack <int>*> towers; //Vector of pointers to stacks

//Printing the tower contents. This is only for eye-candy.

void PrintTowers()
{
stack <int> tempStack;
for (int ii=0;ii<towers.size();ii++) {

 cout << std::endl<< "Tower " << ii <<": ";
 while (!towers[ii]->empty()) {

  tempStack.push(towers[ii]->top());
  towers[ii]->pop();
 }

 while (!tempStack.empty()) {
  towers[ii]->push(tempStack.top());

  cout <<tempStack.top()<<"  "; 
  tempStack.pop();
 }
 cout << " <-- TOP";
}
}

//Move from Tower "from" to Tower "to"
void MoveDisc(int from, int to)
{
towers[to]->push(towers[from]->top());

towers[from]->pop();
}

//Recursive function Hanoi - the most interesting function
//When this function exits, it has moved the lowest
//Tower (as specified by numDiscs) from the sourceTower to the
//destTower using the auxTower as a temporary holder
void Hanoi(int sourceTower, int destTower, int auxTower, int numDiscs)
{

if (numDiscs==0)
 return;
Hanoi(sourceTower, auxTower, destTower, numDiscs-1);

MoveDisc(sourceTower,destTower);
Hanoi(auxTower,destTower,sourceTower,numDiscs-1);
}

int main()
{
int numDiscs;

cout << "Please enter the number of discs: ";

cin >> numDiscs;

//Initialize the Towers by allocating 3 stacks
 for (int ii=0;ii < 3;ii++)

 towers.push_back(new stack<int>);

//Initial condition: all the discs are on Tower 0
 for (int jj=numDiscs-1;jj >=0 ;jj--)

 towers[0]->push(jj);

//Print setup of towers
 cout <<std::endl<<"Initially";

PrintTowers();

//Enter recursive function here
 Hanoi(0, 2, 1, numDiscs);

//Print setup of towers
 cout <<std::endl<<"Finally";
PrintTowers();

//Don't forget to delete the vector of stacks.

 for (int ii=0;ii < 3; ii++)

 delete towers[ii];

cout << std::endl << "Done.";


return 0;
}