Program:Tower.c
Author :Jiltin
Date   :Feb 8,1994
Result :Successful

************************************************************/
#include <stdio.h>
#include <stdlib.h>
#include <dos.h>

#define MAX  50
#define EMPTY 0
#define DONE (pos_matrix[0][disks-1]==pos_matrix[1][disks-1])

char names[3] = { ‘A’,‘B’,‘C’ };
int disks;
int pos_matrix[3][MAX];
int smallest_location = 0;
unsigned move_no = 0;

int main(int, char **);
void move_disk(int,int);
void itowers(int disks);
int next_disk(void);
char *g_time(void);
char *g_date(void);
char *time_diff(char *t1, char *t2);

int main(int argc, char *argv[])
{
int i,j;

char *run_date  ="        ";
char *start_time="        ";
char *finish_time  ="        ";
char *time_difference="           ";

if(argc!=2)
   {
   printf("Usage: %s [n] – where1 < n < %d\n",argv[0],MAX+1);
   return(1);
   }
disks=atoi(argv[1]);

if(disks < 2  ” disks > MAX)
   {
   printf("1 < disks < %d. Please try again. \n",MAX+1);
   return(1);
   }

printf("Solving Towers of Honoi\n");
printf("problem for %d disks   \n",disks);
printf("Using the iterative method… \n\n");

/* Initialize the towers and posts */
for(i=0; i < 3; i++)
   for(j=0; j < disks; j++)
      if(i==0)
         pos_matrix[i][j]=j+1;
      else
         pos_matrix[i][j]=EMPTY;

strcpy(run_date,g_date());
strcpy(start_time,g_time());
itowers(disks);
strcpy(finish_time,g_time());
time_difference=time_diff(finish_time,start_time);
printf("\nSolved in %u moves.\n",move_no);
printf("\nRun date    = %s",run_date);
printf("\nStart Time  = %s",start_time);
printf("\nFinish Time = %s",finish_time);
printf("\nTime taken  = %s",time_difference);
return(0);
}

void itowers(int disks)
{
int   direction,temp;

direction=( disks & 1 ) ? -1 : 1;

while(!DONE)
   {
   if(++move_no & 1)
      {
      temp = smallest_location;
      smallest_location  += direction;
      if(smallest_location < 0)
         smallest_location = 2;
      if(smallest_location > 2)
         smallest_location = 0;

      move_disk(temp,smallest_location);
      }
      else
      {
      temp=next_disk();
      move_disk(temp,3-temp-smallest_location);
      }
   }
}

int next_disk(void)
{
#define SIZE 0
#define POST 1

register location;
int post, avl[2][2],disk=0;

for(post=0;post< 3;post++)
   {
   if(post == smallest_location)
      continue;
   location=0;
   while((pos_matrix[post][location] == EMPTY) && (location < disks))
      location++;
   if(location == disks)
      continue;
   avl[disk][SIZE] = pos_matrix[post][location];
   avl[disk++][POST]=post;
   }
if(disk==1)
   return(avl[0][POST]);
return(avl[0][SIZE] < avl[1][SIZE] ? avl[0][POST] : avl[1][POST]);
}

void move_disk(int src, int dst)
{
register i=0,j=0;

while(pos_matrix[src][i] == EMPTY)
   i++;
while(pos_matrix[dst][j]==EMPTY && j < disks)
   j++;
j–;
printf("Move disk %d from   %c to %c. \n",pos_matrix[src][i],names[src],names[dst]);
pos_matrix[dst][j]=pos_matrix[src][i];
pos_matrix[src][i]=EMPTY;
}

char *g_time()
{
struct time st;
char *sys_time="               ";
   gettime(&st);
   sprintf(sys_time,"%2d:%2d:%2d",(int)st.ti_hour,(int)st.ti_min,(int)st.ti_sec);
   return(sys_time);
}

char *g_date()
{
struct date dt;
char *sys_date="               ";
   getdate(&dt);
   sprintf(sys_date,"%2d-%2d-%-2d",(int)dt.da_day,(int)dt.da_mon,((int)dt.da_year-1900));
   return(sys_date);
}

char *time_diff(char *t1, char *t2)
{
int h1,h2,m1,m2,s1,s2;
char temp[3]="  ";
int f1,f2,df;
char *diff_time="               ";
     temp[0]=t1[0]; temp[1]=t1[1]; temp[2]=‘\0‘; h1=atoi(temp);
     temp[0]=t2[0]; temp[1]=t2[1]; temp[2]=‘\0‘; h2=atoi(temp);
     temp[0]=t1[3]; temp[1]=t1[4]; temp[2]=‘\0‘; m1=atoi(temp);
     temp[0]=t2[3]; temp[1]=t2[4]; temp[2]=‘\0‘; m2=atoi(temp);
     temp[0]=t1[6]; temp[1]=t1[7]; temp[2]=‘\0‘; s1=atoi(temp);
     temp[0]=t2[6]; temp[1]=t2[7]; temp[2]=‘\0‘; s2=atoi(temp);
     f1=h1*3600+m1*60+s1; f2=h2*3600+m2*60+s2;
     df=f1-f2;
     h1=df/3600; m1=df/60 – h1*60; s1 = df – m1*60 – h1*3600;
     sprintf(diff_time,"%2d:%2d:%2d",h1,m1,s1);
     return(diff_time);
}