﻿ Towers of Hanoi ~ Programming Tutorials by SourceTricks
Friday, January 3, 2014

Towers of Hanoi

Approach to solve the Towers of Hanoi game

1. We need to move the n rings from the first pole to target third pole using the second pole as buffer.

2. First move the n-1 rings from first to a second pole using the third.

3. Then move the remaining big ring from first to the third.

4. Now move all the n-1 rings from the second pole to the target third pole on top of the nth (which is big).

5. For moving the n-1 rings from one pole to another pole, use the remaining pole as a buffer using recursion.

C++ program to to solve the Towers of Hanoi game

```#include <iostream>
using namespace std;

#define MAX 4
int fromPoleMain[MAX] = {4,3,2,1};
int tmpPoleMain[MAX];
int toPoleMain[MAX];

void printPole(int *pole)
{
if (fromPoleMain == pole)
{
cout << "ONE ";
return;
}
if (tmpPoleMain == pole)
{
cout << "TWO ";
return;
}
if (toPoleMain == pole)
{
cout << "THREE ";
return;
}

}

void move(int* fromPole, int* toPole)
{
int i,j;
for(i = 0; i<MAX;i++)
{
if(fromPole[i] == 0)
break;
}

for(j = 0; j<MAX;j++)
{
if(toPole[j] == 0)
break;
}
toPole[j] = fromPole[i-1];
printPole(fromPole);
cout << ": posi " << i << " to --> ";
printPole(toPole);
cout << ": at posi " << j ;
cout << " moving  " << toPole[j] <<endl;
fromPole[i-1] = 0;

}

void TowersOfHanoi(int n, int* fromPole, int* toPole, int* tmpPole )
{
if (n==0) return;  // no more rings to move.
TowersOfHanoi(n-1, fromPole, tmpPole, toPole);
move(fromPole,toPole);
TowersOfHanoi(n-1, tmpPole, toPole, fromPole);
}

int main()
{
printPole(fromPoleMain); printPole(toPoleMain); printPole(tmpPoleMain); cout << ": " << endl;

TowersOfHanoi(MAX,fromPoleMain,toPoleMain,tmpPoleMain);
cout << "Finally target  POLE: ";
for(int i = 0; i<MAX;i++)
{
cout << toPoleMain[i] << " ";
}
cout << endl;
return 0;
}```
Output:-
```ONE THREE TWO :
ONE : posi 4 to --> TWO : at posi 0 moving  1
ONE : posi 3 to --> THREE : at posi 0 moving  2
TWO : posi 1 to --> THREE : at posi 1 moving  1
ONE : posi 2 to --> TWO : at posi 0 moving  3
THREE : posi 2 to --> ONE : at posi 1 moving  1
THREE : posi 1 to --> TWO : at posi 1 moving  2
ONE : posi 2 to --> TWO : at posi 2 moving  1
ONE : posi 1 to --> THREE : at posi 0 moving  4
TWO : posi 3 to --> THREE : at posi 1 moving  1
TWO : posi 2 to --> ONE : at posi 0 moving  2
THREE : posi 2 to --> ONE : at posi 1 moving  1
TWO : posi 1 to --> THREE : at posi 1 moving  3
ONE : posi 2 to --> TWO : at posi 0 moving  1
ONE : posi 1 to --> THREE : at posi 2 moving  2
TWO : posi 1 to --> THREE : at posi 3 moving  1
Finally target  POLE: 4 3 2 1
```

Name

Email *

Message *