/*
 * Program to generate a knight's tour
 *
 * As parameters, provide size of board and starting square.
 * knight 8 a1    are the defaults.
 *
 * Written by Warren Porter
 */
#pragma check_pointer(off)
#include <stdio.h>
#include <string.h>

int bdsize=8;
int bdsquare=64;
int ranksep=2;
int filesep=3;
int **b=NULL;
char *scan=NULL;
int solved=0;
int move[8][2] = { {2,1}, {1,2}, {-1,2}, {-2,1},
                 {-2,-1}, {-1,-2}, {1,-2}, {2,-1} };
typedef struct {
   int  rank, file;
   int  order;
} rf;

void write_scr(int col, int row, int color, int background, char *text)
{
   unsigned char attrib, tab[16] = {0, 4, 2, 6, 1, 5, 3, 7, 8, 12, 10,
       14, 9, 13, 11, 15};
   char far *ptr;
   attrib = (tab[background] << 4) + tab[color];
   ptr = (char far *) 0xb8000000L + row * 160 + (col << 1);
   while (*text) {
      *(ptr++) = *(text++);
      *(ptr++) = attrib;
   }
}
void cls()
{
   int i;
   char _far *ptr;
   ptr = (char far *) 0xb8000000L;
   for (i=0;i<4000;i+=2) {
      *(ptr + i) = 0;
      *(ptr + i + 1) = 15;
   }
}

int find_order(file,rank)
{
   int ranksum, rank1, filesum, file1;
   if (file < 0 || file >= bdsize || rank < 0 || rank >= bdsize)
      return(32767); // Square is off the board
   rank1= bdsize - 1 - rank;
   file1= bdsize - 1 - file;
   return((rank < rank1? rank:rank1) + (file < file1? file:file1));
}

void try(x,y,seq)
{
   int i,j;
   rf trys[8],temp;
   char buff[5], space[3]="  ";

   b[x][y]=seq;
   if (seq == bdsquare) { /* Filled up the board */
      solved=1;
      return;
   }

   sprintf(buff,scan,seq);
   write_scr(x*filesep,y*ranksep,15,(x+y)%2,buff);
   for (i=0;i < 8; i++) {
      trys[i].file = x + move[i][0];
      trys[i].rank = y + move[i][1];
      trys[i].order = find_order(trys[i].file,trys[i].rank); }
   for (i=0; i < 7; i++)
      for (j=i+1;j < 8; j++)
         if (trys[i].order > trys[j].order) {
            memcpy(&temp,&trys[j],sizeof(rf));
            memcpy(&trys[j],&trys[i],sizeof(rf));
            memcpy(&trys[i],&temp,sizeof(rf));   }

   for (i=0; i<8; i++)
      if (trys[i].order < 10000 && b[trys[i].file][trys[i].rank] == 0) {
         try(trys[i].file,trys[i].rank,seq+1);
         if (solved)
            return;
         if (trys[i].order == 0)
            continue;   }

   write_scr(x*filesep,y*ranksep,15,(x+y)%2,space);
   b[x][y]=0;  // Reset the square after trying it
   return;
}
//void main()
 void main(int argc,char **argv)
{
   int i, j, begrank=7,begfile=0;
// int argc=3; char *tempi[] = {"knight", "8", "b3" }, **argv=NULL;
// argv=tempi;
   argc--,argv++;
   if (argc) {
      bdsize=atoi(*argv);
      if (bdsize < 6 || bdsize > 19) {
         fprintf(stderr,"Board size out of range\n");
         exit(1);
      }
      bdsquare=bdsize*bdsize;
      argc--,argv++;
   }
   if (argc) {
      if (islower(**argv)) {
         begfile= **argv - 'a';
         if (begfile < 0 || begfile >= bdsize) {
            fprintf(stderr,"file out of range\n");
            exit(1);
         }
         	 begrank=bdsize  - atoi(&argv[0][1]);
             if (begrank < 0 || begrank >= bdsize) {
               fprintf(stderr,"rank out of range\n");
               exit(1);
            }
         }
      }
   if (bdsize % 2 && (begfile + begrank) % 2) {
      fprintf(stderr,"Unsolvable from that square\n");
      exit(1);
   }

   b=(int **)calloc(bdsize,sizeof(int *));
   for (i=0; i < bdsize; i++)
      b[i]=(int *)calloc(bdsize,sizeof(int)) ;
   if (bdsize < 10 )
      scan="%3i";
   else
      scan="%4i";
   cls();
   try(begfile,begrank,1);
   if (solved) {
      for (i=0;i < bdsize;i++) {
         printf("\n");
         for (j=0;j < bdsize;j++) {
            printf(scan,b[j][i]);
            printf(" ");
         }
      }
   }
}