Friday, January 3, 2014

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

0 comments :

Post a Comment

Contact Form

Name

Email *

Message *

Back to Top