#include<stdlib.h>
#include <stdio.h>
#include <bios.h>
#include<string.h>

/* Defination of all moves */
#define TL 0x01 // top left i.e., 2 squares up & 1 square left
#define TR 0x02
#define RT 0x04
#define RB 0x08
#define BR 0x10
#define BL 0x20
#define LB 0x40
#define LT 0x80

// stack which holds the position
typedef struct visited {
  char place ; // varies from  0 to 63 representing a square
  char moves ; // availabe moves -> every bit represents a possible move
  struct visited *next ; // link to previous move
} VISIT ;

VISIT *head ; // contains the latest move made by the horse

#define removMov(mov) head->moves &= ~(mov) // removes an available move
#define isMove(mov) (head->moves&(mov))	   // checks if the move is available

unsigned int number = 0 ; // number of answers written in the current file
unsigned int fno = 0 ;    // file number

int count ; // number of places the horse has covered at any point

FILE *sol ; /* pointer to the file in which the answer is written
	"SOLXXXXX.txt" where XXXXX is an unsigned integer  */

void newPlace    ( char ) ;// pushes a new move to the stack VISIT
void undo        ( void ) ;// pops the stack i.e., undos the last move
char isKnown     ( char ) ;// checks if a place has been visited by the horse
void copystack   ( void ) ;// copies the answer to the sol file
void initProg    ( void ) ;// resumes from previous run
char availability( char ) ;// checks if it is possible to move to a square

void newPlace ( char place ) {// push onto the stack
  struct visited *new ;
  new = ( VISIT * ) malloc ( sizeof ( VISIT ) ) ;
  new -> place = place ;
  new -> moves = availability ( place ) ;	// compute availability and store
  new -> next = head ;
  head = new ;
  count ++ ;		// increment count, as a new move has been made
}

void undo ( ) { // pops the stack
  VISIT *temp ;
  if ( head == NULL ) // check if the stack is already empty
    return ;
  temp = head ;
  head = head -> next ;
  free ( temp ) ;
  count -- ;   		// decrement count
}

char isKnown ( char place ) {
  VISIT *temp = head ;
  while ( temp ) { // surf through the stack to check if the place is visited
    if ( temp -> place == place ) return 1 ;
    temp = temp -> next ;
  }
  return 0 ; // executes only if place is not found
}

void copystack ( void ) { // executes when an answer is found
  char move[64], i ;  // to store the moves in order
  VISIT *temp = head ;

  for ( i = 63 ; i >= 0 ; i-- ) {
    move[i] = temp -> place ;
    temp = temp -> next ;
  }

  for ( i = 0 ; i < 64 ; i++ )
    fprintf ( sol, "%d ", move[i] ) ;
  fprintf ( sol, "\n" ) ;
}

void initProg ( ) {
  FILE *recover ;
  count = 0 ;
  head = NULL ;
  
  recover = fopen ( "Recover.txt", "rt" ) ;
/*
	this file contains the no of last file opened say 1 (for sol1.txt)
	number of answers stored in this file
	count of the moves that are to be in the stack
	data that are to be stored in the stack
*/
  if ( recover != NULL ) {
    char temp[10], fname[15] = "Sol", i, j ; // initialize fname
    fscanf ( recover, "%u %u %d", &fno, &number, &count ) ;

  // This block opens the last file created by the application
    itoa ( fno, temp, 10 ) ;
    strcat ( fname, temp ) ; // add sufix
    strcat ( fname, ".txt" ) ; // add extenstion
    sol = fopen ( fname, "a+" ) ; // open the fname

    for ( i = 0 ; i < count ; i ++ ) {
    // This block resumes the movements made
      VISIT *new ;
      int p, m ;
      fscanf ( recover, "%d %d", &p, &m ) ; // data of a node
  // push the data on to the stack
      new = ( VISIT * ) malloc ( sizeof ( VISIT ) ) ;
      new -> place = p ;
      new -> moves = m ;
      new -> next = head ;
      head = new ;
    }
    fclose ( recover ) ;
  }
  else { // start from scrach
    sol = fopen ( "SOL0.TXT", "wt" ) ;
    newPlace ( 0 ) ; // place the horse in the top left corner on the board
  }
  puts ( "\n Press Space or Esc or Enter Key to pause after next result" ) ;
  puts ( " \n Program will resume on next run with the help of recover.txt" ) ;
  printf ( "\n File No: %u Solution No: %-5u", fno, number ) ;
}

// saves the current state in recover.txt
void savestate ( ) {
  FILE *recover ;
  char i, m[64], p[64], c ;
  recover = fopen ( "Recover.txt", "wt" ) ;
  // stores the file no, no of answers writen & count of moves in stack
  fprintf ( recover, " %u %u %d ", fno, number, c=count );
 // stores the moves in reverse order for ( LIFO of stack )
  for ( i = count-1 ; i>-1 ; i-- ) {
    p[i] = head->place;
    m[i] = head->moves;
    undo();
  }
	// stores data in file
  for ( i = 0; i < c ; i++ )
    fprintf ( recover, "\n %d %d",(int) p[i],(int) m[i] ) ;
  fclose ( recover ) ;
}

main ( ) {
  char filename[15] = "sol", temp[10] ;
  void savestate ( void ) ;
  initProg ( ) ;
  while ( head ) { 		// till the horse has no where left to go
    char moves, c ; 	// c checks user input
    if ( count == 64 ) { // if an answer is found
      number ++ ;
      // increment the number of answer in the current file
      copystack ( ) ;
      // save to file
      printf ( "\rFile No: %u Solution No: %-5u", fno, number ) ;
      // update screen
     if ( number == 0x8000 ) { // if 0x8000 answers are writen goto next file
	// Creates a unique file name on which the next result will be stored

        number = 0 ;
        // reset number of answers in the new file
        fclose ( sol ) ;
        // close the old file & open a new one
        itoa( ++fno, temp , 10)  ;
        strcat ( filename, temp ) ;
        strcat ( filename, ".txt" ) ;
        sol = fopen ( filename, "wt" ) ;
        printf ( "\a" ); // to notify that a multiple of 0x8000 answers have been found
      }
      if ( bioskey(1)) {// if user want to stop the prg then save its state
        c = bioskey ( 0 ) ;
        if ( c == ' ' || c == '\x1B' || c == '\r' || c == '\n' )
	savestate () ;
      }
    }
   // Move horse if there is an availability
    if ( isMove ( TL ) ) {
      removMov ( TL ) ;
      newPlace ( head->place - 17 ) ;
    }
    else if ( isMove ( TR ) ) {
      removMov ( TR ) ;
      newPlace ( head->place - 15 ) ;
    }
    else if ( isMove ( RT ) ) {
      removMov ( RT ) ;
      newPlace ( head->place - 6 ) ;
    }
    else if ( isMove ( RB ) ) {
      removMov ( RB ) ;
      newPlace ( head->place + 10 ) ;
    }
    else if ( isMove ( BR ) ) {
      removMov ( BR ) ;
      newPlace ( head->place + 17 ) ;
    }
    else if ( isMove ( BL ) ) {
      removMov ( BL ) ;
      newPlace ( head->place + 15 ) ;
    }
    else if ( isMove ( LB ) ) {
      removMov ( LB ) ;
      newPlace ( head->place + 6 ) ;
    }
    else if ( isMove ( LT ) ) {
      removMov ( LT ) ;
      newPlace ( head->place - 10 ) ;
    }
    else undo ( ) ;
  }
}

char availability ( char place )  {
  char moves = 0 ;
   /*Check Boundary condition*/  /*Check if visited*/
  if( place % 8!=0 && place >15 && !isKnown( place - 17))
    moves |= TL ;
  if( place % 8!=7 && place >15 && !isKnown( place - 15))
    moves |= TR ;
  if( place % 8<=5 && place >7  && !isKnown( place - 6 ))
     moves |= RT ;
  if( place % 8>=2 && place >7  && !isKnown( place - 10))
     moves |= LT ;
  if( place % 8!=0 && place <48 && !isKnown( place + 15))
    moves |= BL ;
  if( place % 8!=7 && place <48 && !isKnown( place + 17))
    moves |= BR ;
  if( place % 8>=2 && place <56 && !isKnown( place + 6 ))
    moves |= LB ;
  if( place % 8<=5 && place <56 && !isKnown( place + 10))
    moves |= RB ;
/* The following may lead to losing some answers
             but it speeds up the process!!*/
/* If the horse is near to the corner then visit the corner since there are just 2 ways to reach a corner '1 way in 1 way out'.*/
	switch ( place ) {
	case 41: if ( !isKnown( 56 ) ) moves &= BL ; break ;
	case 50: if ( !isKnown( 56 ) ) moves &= LB ; break ;
	case 53: if ( !isKnown( 63 ) ) moves &= RB ; break ;
	case 46: if ( !isKnown( 63 ) ) moves &= BR ; break ;
	case 13: if ( !isKnown( 07 ) ) moves &= RT ; break ;
	case 22: if ( !isKnown( 07 ) ) moves &= TR ; break ;
	}
	return moves ;
}