Program for solving Towers of Brahma

Towers of Brahma solved by a C program

Hi friends, while I was referring a book I saw something interesting and wanted to share it with my readers. This would make you believe that Gods may have existed and had an eternal knowledge based on science. That is the Tower of Brahma or Lucas' Tower.

Don't worry I'm not going to have any spiritual stuff here, I'll  show a C program designed to solve the Hanoi towers with minimum number of moves.

Origin of Hanoi towers puzzle:

Origin of Hanoi towers has been after Tower of Brahma ritual. Brahma designed these towers . Story starts in an ancient temple of Kashi which contains a large room with three towers in it surrounded by 64 golden disks.
According to legend,  

  • At the time the world was created, there was a diamond tower with 64 golden disks. The disks were of decreasing size and were stacked on the tower in an order (the largest will be at the bottom and the next smaller in size will be above the last and so on).
  • Besides this tower there were two other diamond towers. Since the time of creation, Brahman priests have been attempting to move the disks from tower A to tower B using tower C for intermediate storage.
  • As the disks are very heavy, they can be moved only one at a time. 
  • In addition, at no time can a larger disk be on top of a smaller disk. According to Brahma, the world will come to an end when the priests have completed their task.
The most fascinating thing about this puzzle is the legend can be proved scientifically true. If the priests were able to move disks at a rate of one per second, using the smallest number of moves, it would take them 2^(64)−1 seconds (same no.of moves) or nearly 585 billion years to finish, or about 127 times the current age of the sun.

C program For solving the Tower of Brahma 

Before we analyze the program, I would explain some points regarding the conceptual model of the towers. I've chosen the problem to solve using a non recursive model as it would be rather simple to explain and understand.
We have three towers named t1, t2, and t3. They are represented using arrays such that the first element of every tower is zero. If the tower is empty it will be consisting of all -1's except the first elements.
You can look at the image to get a detailed view of the towers.
hanoi-tower-snap
Value at index represents the disk size(towers 2 and 3 have -1 as elements)

so, the declaration of towers goes as follows.

int t1[5],t2[5],t3[5],i=1,x=pow(2,4)-1;
int n1=4,n2=0,n3=0;

'x' denotes the no.of moves required. I've discussed this formula in the origin.

Initializing the towers

The first tower t1 will be having all the 4 disks( I've chosen only 4 to depict the program). The rest of them will be empty represented as -1. The initialization code is as follows.

void initt(int *t, int a){
 int i=5;
 if(a){
  *t=0;
  t++;
  while(i>0){
   *t=i;
   t++;
   i--;
  }
 }
 else{
  *t=0;
  t++;
  while(i>0){
   *t=empty;
   t++;
   i--;
  }
 }

}
we will call the functions in main as follows.

initt(t1,1);// 1 suggests that it is the initial diamond tower
initt(t2,0);
initt(t3,0);
Now Algorithm for moving the towers

For an even number of disks:
  • make the move between t1 and t2.
  • make the move between t1 and t3.
  • make the move between t2 and t3.
  • repeat until complete.
For an odd number of disks:
  • make the move between t1 and t3.
  • make the move between t1 and t2.
  • make the move between t3 and t2.
  • repeat until complete.
The above can be implemented as follows

if(n1%2!=0){ 
  while(i<=x){
   switch(i%3){
    case 1:
    move(t1,&n1,t3,&n3);
    break;
    case 2:
    move(t1,&n1,t2,&n2);
    break;
    case 0:
    move(t2,&n2,t3,&n3);
    break;
   }
   i++;
   printf("\nnext call\n");
   write(t1,n1,t2,n2,t3,n3);
  } 
 }
 else{
  while(i<=x){
   switch(i%3){
    case 1:
    move(t1,&n1,t2,&n2);
    break;
    case 2:
    move(t1,&n1,t3,&n3);
    break;
    case 0:
    move(t2,&n2,t3,&n3);
    break;
   }
   i++;
   printf("\nnext call\n");
   write(t1,n1,t2,n2,t3,n3);
  }
 }

The next thing is the printing the contents of tower for every move. This can be accomplished by the following function.

void write(int *t1,int n1,int *t2,int n2,int *t3,int n3){
 int i=1;
 t1++;t2++;t3++;
 if(i<=n1)
 while(i<=n1){
  printf("t1[%d]=%d\t",i,*t1);
  i++;t1++;
 }
 i=1;
 if(i<=n2)
 printf("\n\n");
 while(i<=n2){
  printf("t2[%d]=%d\t",i,*t2);
  i++;t2++;
 }
 i=1;
 if(i<=n3)
 printf("\n\n");
 while(i<=n3){
  printf("t3[%d]=%d\t",i,*t3);
  i++;t3++;
 }
}
Output for the complete program will be as follows

t1[1]=5 t1[2]=4 t1[3]=3 t1[4]=2 t1[5]=1
next call
t1[1]=5 t1[2]=4 t1[3]=3 t1[4]=2

t3[1]=1
next call
t1[1]=5 t1[2]=4 t1[3]=3

t2[1]=2

t3[1]=1
next call
t1[1]=5 t1[2]=4 t1[3]=3

t2[1]=2 t2[2]=1
next call
t1[1]=5 t1[2]=4

t2[1]=2 t2[2]=1

t3[1]=3
next call
t1[1]=5 t1[2]=4 t1[3]=1

t2[1]=2

t3[1]=3
next call
t1[1]=5 t1[2]=4 t1[3]=1

t3[1]=3 t3[2]=2
next call
t1[1]=5 t1[2]=4

t3[1]=3 t3[2]=2 t3[3]=1
next call
t1[1]=5

t2[1]=4

t3[1]=3 t3[2]=2 t3[3]=1
next call
t1[1]=5

t2[1]=4 t2[2]=1

t3[1]=3 t3[2]=2
next call
t1[1]=5 t1[2]=2

t2[1]=4 t2[2]=1

t3[1]=3
next call
t1[1]=5 t1[2]=2 t1[3]=1

t2[1]=4

t3[1]=3
next call
t1[1]=5 t1[2]=2 t1[3]=1

t2[1]=4 t2[2]=3
next call
t1[1]=5 t1[2]=2

t2[1]=4 t2[2]=3

t3[1]=1
next call
t1[1]=5

t2[1]=4 t2[2]=3 t2[3]=2

t3[1]=1
next call
t1[1]=5

t2[1]=4 t2[2]=3 t2[3]=2 t2[4]=1
next call


t2[1]=4 t2[2]=3 t2[3]=2 t2[4]=1

t3[1]=5
next call
t1[1]=1

t2[1]=4 t2[2]=3 t2[3]=2

t3[1]=5
next call
t1[1]=1

t2[1]=4 t2[2]=3

t3[1]=5 t3[2]=2
next call


t2[1]=4 t2[2]=3

t3[1]=5 t3[2]=2 t3[3]=1
next call
t1[1]=3

t2[1]=4

t3[1]=5 t3[2]=2 t3[3]=1
next call
t1[1]=3

t2[1]=4 t2[2]=1

t3[1]=5 t3[2]=2
next call
t1[1]=3 t1[2]=2

t2[1]=4 t2[2]=1

t3[1]=5
next call
t1[1]=3 t1[2]=2 t1[3]=1

t2[1]=4

t3[1]=5
next call
t1[1]=3 t1[2]=2 t1[3]=1

t3[1]=5 t3[2]=4
next call
t1[1]=3 t1[2]=2

t3[1]=5 t3[2]=4 t3[3]=1
next call
t1[1]=3

t2[1]=2

t3[1]=5 t3[2]=4 t3[3]=1
next call
t1[1]=3

t2[1]=2 t2[2]=1

t3[1]=5 t3[2]=4
next call


t2[1]=2 t2[2]=1

t3[1]=5 t3[2]=4 t3[3]=3
next call
t1[1]=1

t2[1]=2

t3[1]=5 t3[2]=4 t3[3]=3
next call
t1[1]=1

t3[1]=5 t3[2]=4 t3[3]=3 t3[4]=2
next call


t3[1]=5 t3[2]=4 t3[3]=3 t3[4]=2 t3[5]=1 31
--------------------------------
I've not explained the entire program, Coding can be fun only if you have a challenge. Trace it by yourself and comment below if you have any doubts.
Recursive one will be much shorter than this but it is little complex to understand. Try to develop a recursive program by yourself.

Completely commented program can be found at
https://github.com/prathapreddy18/Towers-of-brahma

0 comments:

Post a Comment

Please DO NOT SPAM. You're not allowed to use links in comments unless it's necessary.

I Appreciate your valuable Feedback.

Regards,

www.TricksStar.com