Software & Finance - Monthly Magazine Online

Volume 1 - Issue 1

Dec 2011

Dec 2011 - Technology - Tower Of Hanoi Algorithm


You can find the complete Visual C++ source code for Tower of Hanoi algorithm. Given the number of discs as input, you can get the print out of the list of steps you need to solve the problem.

 

This program is developed in Visual C++ console application and takes the number of discs as input. It uses recursive logic to find the number of steps required to solve thr problem. I have implemented my own stack. Initially the discs are getting added into the stack. I have 3 stacks A, B and C for 3 towers A, B and C. The function SolveTOH is used to compute all possible steps to solve the problem. Note that it uses the recursive logic and the output after each move is written on the screen.

 

The Big O notation for this problem is: 2^n - 1.

 

The other related links are given below:

 

The complete source code, project file and executable can be found at the end of the page.

 

#include <stdio.h>

#include <tchar.h>

#include <iostream>

#include <stdlib.h>

#include <string.h>

 

template<class T> class MyStack

{

    T *m_data;

    int m_numElements;

 

public:

 

    MyStack() : m_data(NULL), m_numElements(0) { }

 

    ~MyStack()

    {

        free(m_data);

        m_data = NULL;

        m_numElements = 0;

    }

 

    bool empty()

    {

        free(m_data);

        m_data = NULL;

        m_numElements = 0;

        return true;

    }

 

    bool push(T data)

    {

        if(m_data == NULL) // root node

        {

            m_numElements = 1;

            m_data = (T*) malloc(sizeof(T));

        }

        else

        {

            m_numElements++;

            m_data = (T*) realloc(m_data, m_numElements * sizeof(T));

            memmove(&m_data[1], m_data, (m_numElements - 1) * sizeof(T));

        }

        m_data[0] = data;

        return true;

    }

 

 

 

    int pop()

    {

        int result = -1;

        if(m_data == NULL) // root node

        {

            m_numElements = 0;

            return -1;

        }

        else

        {

            result = top();

            if(m_numElements == 1)

            {

                // last item

                m_numElements = 0;

                free(m_data);

                m_data = NULL;

            }

            else

            {

                m_numElements--;

                memmove(m_data, &m_data[1], m_numElements * sizeof(T));

                m_data = (T*) realloc(m_data, m_numElements * sizeof(T));

            }

        }

        return result;

    }

 

    T top()

    {

        if(m_numElements > 0)

            return m_data[0];

    }

 

    int size()

    {

        return m_numElements;

    }

 

    void PrintStack()

    {

        int i = 0;

        printf("[");

        for(i = m_numElements - 1; i >= 0; i--)

        {

            printf("%d", m_data[i]);

        }

        printf("]");

    }

};

 

static int movecount = 0;

static int countA = 0;

static int countB = 0;

static int countC = 0;

 

static MyStack<int> *A = 0;

static MyStack<int> *B = 0;

static MyStack<int> *C = 0;

 

void PrintStacks()

{

    if (countA != A->size() ||

        countB != B->size() ||

        countC != C->size())

    {

        int diffA = A->size() - countA;

        int diffB = B->size() - countB;

        int diffC = C->size() - countC;

        if (diffA == 1)

        {

            if (diffB == -1)

                printf("Move Disc %d From B To A", A->top());

            else

                printf("Move Disc %d From C To A", A->top());

        }

        else if (diffB == 1)

        {

            if (diffA == -1)

                printf("Move Disc %d From A To B", B->top());

            else

                printf("Move Disc %d From C To B", B->top());

        }

        else //if (diffC == 1)

        {

            if (diffA == -1)

                printf("Move Disc %d From A To C", C->top());

            else

                printf("Move Disc %d From B To C", C->top());

        }

        countA = A->size();

        countB = B->size();

        countC = C->size();

        printf("\n");

    }

 

    A->PrintStack();

    printf(" , ");

    B->PrintStack();

    printf(" , ");

    C->PrintStack();

    printf(" , ");

}

 

void Solve2DiscsTOH(MyStack<int> *source, MyStack<int> *temp, MyStack<int> *dest)

{           

    temp->push(source->pop());

    movecount++;

    PrintStacks();

 

    dest->push(source->pop());

    movecount++;

    PrintStacks();

 

    dest->push(temp->pop());

    movecount++;

    PrintStacks();

}

 

int SolveTOH(int nDiscs, MyStack<int> *source, MyStack<int> *temp, MyStack<int> *dest)

{

    if (nDiscs <= 4)

    {

        if ((nDiscs % 2) == 0)

        {

            Solve2DiscsTOH(source, temp, dest);

            nDiscs = nDiscs - 1;

            if (nDiscs == 1)

                return 1;

 

            temp->push(source->pop());

            movecount++;

            PrintStacks();

            //new source is dest, new temp is source, new dest is temp;

            Solve2DiscsTOH(dest, source, temp);

 

            dest->push(source->pop());

            movecount++;

            PrintStacks();

            //new source is temp, new temp is source, new dest is dest;

            SolveTOH(nDiscs, temp, source, dest);

        }

        else

        {

            if (nDiscs == 1)

                return 0;

            Solve2DiscsTOH(source, dest, temp);

            nDiscs = nDiscs - 1;

            dest->push(source->pop());

            movecount++;

            PrintStacks();

            Solve2DiscsTOH(temp, source, dest);

        }

        return 1;

    }

    else if (nDiscs >= 5)

    {

        SolveTOH(nDiscs - 2, source, temp, dest);

        temp->push(source->pop());

        movecount++;

        PrintStacks();

        SolveTOH(nDiscs - 2, dest, source, temp);

        dest->push(source->pop());

        movecount++;

        PrintStacks();

        SolveTOH(nDiscs - 1, temp, source, dest);

    }

    return 1;

}

 

int _tmain(int argc, _TCHAR* argv[])

{

    int sz, i, maxdisc;

    A = (MyStack<int>*) malloc(sizeof(MyStack<int>));

    B = (MyStack<int>*) malloc(sizeof(MyStack<int>));

    C = (MyStack<int>*) malloc(sizeof(MyStack<int>));

 

    while(1)

    {

        printf("\nEnter the number of discs (-1 to exit): ");

        scanf("%d", &maxdisc);

        if(maxdisc == -1)

            break;

        if(maxdisc < 2 || maxdisc > 9)

        {

            printf("Enter between 2 - 9");

            continue;

        }

 

        movecount = 0;

        memset((void*)A, 0, sizeof(MyStack<int>));

        memset((void*)B, 0, sizeof(MyStack<int>));

        memset((void*)C, 0, sizeof(MyStack<int>));

        for (i = maxdisc; i >= 1; i--)

            A->push(i);

        countA = A->size();

        countB = B->size();

        countC = C->size();

        PrintStacks();

        SolveTOH(maxdisc, A, B, C);

        printf("Total Moves = %d", movecount);

        C->empty();

    }

 

    return 0;

}

 

 

 

Click here to download the Visual C++ (VS2005) project and executable

 

 

output

Enter the number of discs (-1 to exit): 0

Enter between 2 - 9

 

 

Enter the number of discs (-1 to exit): 1

Enter between 2 - 9

 

 

Enter the number of discs (-1 to exit): 2

[21] , [] , [] , Move Disc 1 From A To B

[2] , [1] , [] , Move Disc 2 From A To C

[] , [1] , [2] , Move Disc 1 From B To C

[] , [] , [21] , Total Moves = 3

 

 

Enter the number of discs (-1 to exit): 3

[321] , [] , [] , Move Disc 1 From A To C

[32] , [] , [1] , Move Disc 2 From A To B

[3] , [2] , [1] , Move Disc 1 From C To B

[3] , [21] , [] , Move Disc 3 From A To C

[] , [21] , [3] , Move Disc 1 From B To A

[1] , [2] , [3] , Move Disc 2 From B To C

[1] , [] , [32] , Move Disc 1 From A To C

[] , [] , [321] , Total Moves = 7

 

 

Enter the number of discs (-1 to exit): 4

[4321] , [] , [] , Move Disc 1 From A To B

[432] , [1] , [] , Move Disc 2 From A To C

[43] , [1] , [2] , Move Disc 1 From B To C

[43] , [] , [21] , Move Disc 3 From A To B

[4] , [3] , [21] , Move Disc 1 From C To A

[41] , [3] , [2] , Move Disc 2 From C To B

[41] , [32] , [] , Move Disc 1 From A To B

[4] , [321] , [] , Move Disc 4 From A To C

[] , [321] , [4] , Move Disc 1 From B To C

[] , [32] , [41] , Move Disc 2 From B To A

[2] , [3] , [41] , Move Disc 1 From C To A

[21] , [3] , [4] , Move Disc 3 From B To C

[21] , [] , [43] , Move Disc 1 From A To B

[2] , [1] , [43] , Move Disc 2 From A To C

[] , [1] , [432] , Move Disc 1 From B To C

[] , [] , [4321] , Total Moves = 15

 

 

Enter the number of discs (-1 to exit): 5

[54321] , [] , [] , Move Disc 1 From A To C

[5432] , [] , [1] , Move Disc 2 From A To B

[543] , [2] , [1] , Move Disc 1 From C To B

[543] , [21] , [] , Move Disc 3 From A To C

[54] , [21] , [3] , Move Disc 1 From B To A

[541] , [2] , [3] , Move Disc 2 From B To C

[541] , [] , [32] , Move Disc 1 From A To C

[54] , [] , [321] , Move Disc 4 From A To B

[5] , [4] , [321] , Move Disc 1 From C To B

[5] , [41] , [32] , Move Disc 2 From C To A

[52] , [41] , [3] , Move Disc 1 From B To A

[521] , [4] , [3] , Move Disc 3 From C To B

[521] , [43] , [] , Move Disc 1 From A To C

[52] , [43] , [1] , Move Disc 2 From A To B

[5] , [432] , [1] , Move Disc 1 From C To B

[5] , [4321] , [] , Move Disc 5 From A To C

[] , [4321] , [5] , Move Disc 1 From B To A

[1] , [432] , [5] , Move Disc 2 From B To C

[1] , [43] , [52] , Move Disc 1 From A To C

[] , [43] , [521] , Move Disc 3 From B To A

[3] , [4] , [521] , Move Disc 1 From C To B

[3] , [41] , [52] , Move Disc 2 From C To A

[32] , [41] , [5] , Move Disc 1 From B To A

[321] , [4] , [5] , Move Disc 4 From B To C

[321] , [] , [54] , Move Disc 1 From A To C

[32] , [] , [541] , Move Disc 2 From A To B

[3] , [2] , [541] , Move Disc 1 From C To B

[3] , [21] , [54] , Move Disc 3 From A To C

[] , [21] , [543] , Move Disc 1 From B To A

[1] , [2] , [543] , Move Disc 2 From B To C

[1] , [] , [5432] , Move Disc 1 From A To C

[] , [] , [54321] , Total Moves = 31

 

 

Enter the number of discs (-1 to exit): 6

[654321] , [] , [] , Move Disc 1 From A To B

[65432] , [1] , [] , Move Disc 2 From A To C

[6543] , [1] , [2] , Move Disc 1 From B To C

[6543] , [] , [21] , Move Disc 3 From A To B

[654] , [3] , [21] , Move Disc 1 From C To A

[6541] , [3] , [2] , Move Disc 2 From C To B

[6541] , [32] , [] , Move Disc 1 From A To B

[654] , [321] , [] , Move Disc 4 From A To C

[65] , [321] , [4] , Move Disc 1 From B To C

[65] , [32] , [41] , Move Disc 2 From B To A

[652] , [3] , [41] , Move Disc 1 From C To A

[6521] , [3] , [4] , Move Disc 3 From B To C

[6521] , [] , [43] , Move Disc 1 From A To B

[652] , [1] , [43] , Move Disc 2 From A To C

[65] , [1] , [432] , Move Disc 1 From B To C

[65] , [] , [4321] , Move Disc 5 From A To B

[6] , [5] , [4321] , Move Disc 1 From C To A

[61] , [5] , [432] , Move Disc 2 From C To B

[61] , [52] , [43] , Move Disc 1 From A To B

[6] , [521] , [43] , Move Disc 3 From C To A

[63] , [521] , [4] , Move Disc 1 From B To C

[63] , [52] , [41] , Move Disc 2 From B To A

[632] , [5] , [41] , Move Disc 1 From C To A

[6321] , [5] , [4] , Move Disc 4 From C To B

[6321] , [54] , [] , Move Disc 1 From A To B

[632] , [541] , [] , Move Disc 2 From A To C

[63] , [541] , [2] , Move Disc 1 From B To C

[63] , [54] , [21] , Move Disc 3 From A To B

[6] , [543] , [21] , Move Disc 1 From C To A

[61] , [543] , [2] , Move Disc 2 From C To B

[61] , [5432] , [] , Move Disc 1 From A To B

[6] , [54321] , [] , Move Disc 6 From A To C

[] , [54321] , [6] , Move Disc 1 From B To C

[] , [5432] , [61] , Move Disc 2 From B To A

[2] , [543] , [61] , Move Disc 1 From C To A

[21] , [543] , [6] , Move Disc 3 From B To C

[21] , [54] , [63] , Move Disc 1 From A To B

[2] , [541] , [63] , Move Disc 2 From A To C

[] , [541] , [632] , Move Disc 1 From B To C

[] , [54] , [6321] , Move Disc 4 From B To A

[4] , [5] , [6321] , Move Disc 1 From C To A

[41] , [5] , [632] , Move Disc 2 From C To B

[41] , [52] , [63] , Move Disc 1 From A To B

[4] , [521] , [63] , Move Disc 3 From C To A

[43] , [521] , [6] , Move Disc 1 From B To C

[43] , [52] , [61] , Move Disc 2 From B To A

[432] , [5] , [61] , Move Disc 1 From C To A

[4321] , [5] , [6] , Move Disc 5 From B To C

[4321] , [] , [65] , Move Disc 1 From A To B

[432] , [1] , [65] , Move Disc 2 From A To C

[43] , [1] , [652] , Move Disc 1 From B To C

[43] , [] , [6521] , Move Disc 3 From A To B

[4] , [3] , [6521] , Move Disc 1 From C To A

[41] , [3] , [652] , Move Disc 2 From C To B

[41] , [32] , [65] , Move Disc 1 From A To B

[4] , [321] , [65] , Move Disc 4 From A To C

[] , [321] , [654] , Move Disc 1 From B To C

[] , [32] , [6541] , Move Disc 2 From B To A

[2] , [3] , [6541] , Move Disc 1 From C To A

[21] , [3] , [654] , Move Disc 3 From B To C

[21] , [] , [6543] , Move Disc 1 From A To B

[2] , [1] , [6543] , Move Disc 2 From A To C

[] , [1] , [65432] , Move Disc 1 From B To C

[] , [] , [654321] , Total Moves = 63 

 

 

Enter the number of discs (-1 to exit): -1

Good Bye!