Applications (Abstract Data Type) Part 5 Continue

Towers of Hanoi

Towers of Hanoi

One of the most interesting applications of stacks can be found in solving a puzzle called Tower of Hanoi. According to an old Brahmin story, the existence of the universe is calculated in terms of the time taken by a number of monks, who are working all the time, to move 64 disks from one pole to another. But there are some rules about how this should be done, which are:

1.     move only one disk at a time.

2.     for temporary storage, a third pole may be used.

3.     a disk of larger diameter may not be placed on a disk of smaller diameter.

For algorithm of this puzzle see Tower of Hanoi.

Assume that A is first tower, B is second tower & C is third tower.

Towers of Hanoi step 1

Towers of Hanoi step 2

Towers of Hanoi step 3

Towers of Hanoi step 4

Tower of Hanoi

Output: (when there are 3 disks)

Let 1 be the smallest disk, 2 be the disk of medium size and 3 be the largest disk.

The C++ code for this solution can be implemented in two ways:

First implementation (without using stacks)

void TowersofHanoi(int n, int a, int b, int c)

{

    if(n > 0)

    {

        TowersofHanoi(n-1, a, c, b); //recursion

        cout << " Move top disk from tower " <<

                      a << " to tower " << b << endl ;

        TowersofHanoi(n-1, c, b, a); //recursion

    }

}

Second implementation (using stacks)

// Global variable , tower [1:3] are three towers

arrayStack<int> tower[4];

void TowerofHanoi(int n)

{

    // Preprocessor for moveAndShow.

    for (int d = n; d > 0; d--) //initialize

        tower[1].push(d);              //add disk d to tower 1

    moveAndShow(n, 1, 2, 3);           /*move n disks from tower 1 to tower 3 using

                                       tower 2 as intermediate tower*/

}

void moveAndShow(int n, int a, int b, int c)

{

    // Move the top n disks from tower a to tower b showing states.

    // Use tower c for intermediate storage.

    if(n > 0)

    {

        moveAndShow(n-1, a, c, b); //recursion

        int d = tower[x].top();        //move a disc from top of tower x to top of

        tower[x].pop();                //tower y

        tower[y].push(d);

        showState();                   //show state of 3 towers

        moveAndShow(n-1, c, b, a); //recursion

    }

}

However complexity for above written implementations is O(). So it's obvious that problem can only be solved for small values of n (generally n <= 30).

In case of the monks, the number of turns taken to transfer 64 disks, by following the above rules, will be 18,446,744,073,709,551,615; which will surely take a lot of time.

Notes continue into the next blog:
Applications part 5 Continue (Abstract Data Type (ADT)) 

J.W. PRODUCTION