6 Aug 2013

Solving Tower of Hanoi/Brahma Problem using C Program

Hello friends, recently while reviewing a few C programming fundamentals, I came across the well known “Tower of Hanoi Problem” or the fondly called “Tower of Bramha Puzzle”.

For those who don’t know about this Game/Puzzle/Problem, let me explain it in few lines:
In the standard game, 3 towers or pegs along with a finite number of Disks of different sizes are given. Initially all the disks are mounted on tower 1 with a proper order wherein the largest disk is at the bottom followed by disks of smaller sizes over it. The objective of this game is to put the all the disks in the same order as in Tower 1, in Tower 3 using Tower 2 as an auxiliary tower. Sounds Easy Isn’t It?


Tower of Hanoi/Bramha


But Wait! There is a catch in it. The condition for this game is you can’t put larger disk over any smaller disk and at a time, only one disk can be moved. Now it sounds a little tricky, Isn’t It?

If you want to play this game online you can visit this [link]

Now to solve this game within optimum number of steps, there is a recursive algorithm which I found in “Wikipedia page for Tower of Hanoi”. I successfully tried implementing the algorithm in C, the codes of which can be found below.

In wiki, I found that in India, there is a Hindu Temple in Kashi Vishwanath having 3 towers with 64 golden disks in it. As per the saying, Priests there are moving those disks to finish the puzzle since long time. The mythology says that when the puzzle will solved completely, then the world will end.

Well Don’t worry, Number of steps required to complete the puzzle is given by:

 No. of steps = (2^n)-1,

 Where n represents the number of disks.

So for 64 disks, it will take somewhere around 1.844 x 10^19 steps. Amazing isn’t it! So though not practically possible, consider that the priests are moving disks at the rate of 1 disk per second, then it would take 1.844 x 10^19 seconds amounting to a massive 585 billion years (as per Wikipedia calculations).

The number is quite big! Isn’t It. Well I tried to solve this Tower of Hanoi problem for 64 disks in my Laptop. The program execution took more than 1 hour 30 minutes, so I stopped the execution in between as a result of frustration.

The simple C code can be found below:

/*
C program for solving Tower of Hanoi Problem or Tower of Brahma Puzzle
By: Amit Biswal
URL: www.123mylist.com (Previously http://amitbiswal.blogspot.com)
*/
#include <stdio.h>
#include <conio.h>
int steps_count=0;
int main()
{
    int num_disk;
    printf("Application for solving Tower of Hanoi Problem programmed in C\nEnter the Number of Disks");
    scanf("%d",&num_disk);
    if(num_disk>=1)
    {       printf("\nThe Optimum way to move disks from Tower 1 to Tower 3 is given below:\n");
            function_tower(num_disk,1,2,3); 
            printf("\n\nOptimum Number of Steps = %d",steps_count);
                }
    else
    printf("INVALID!");
    getch();
    return 0;
}
int function_tower(int n, int a, int b, int c)
{
     //this function puts disk from tower a to tower c 
     if(n==1)
     {
               printf("\nTower %d to Tower %d",a,c);
               steps_count++;
               return 0;
     }
     function_tower(n-1,a,c,b); //from tower a to b
     printf("\nTower %d to Tower %d",a,c);
     steps_count++;
     function_tower(n-1,b,a,c);
     return 0;
}



Related Post :


0 comments:

Post a Comment

If you liked this blog then Join me at:
Facebook
Twitter
RSS