/* Knight.c
// Chris D'Urso
// chris@durso.org
// 13 July 2004
//
// * Release 1.0, feel free to distribute this code and modify it as
//   you please.  I ask only that you credit me for largely similar  
//   derivations and report any errors you discover. 
//
// * About
//
// The knights travel problem is a simple computer science/applied mathematics
// puzzle to determine the path(s) a chess night may travel through a two 
// dimensional grid such that he lands on every square exactly once.
//
// For those unfamilair with the rules of chess a knight hops to one of the 
// following 8 spaces for each move. Four options are, two spaces vertically 
// (either up or down) with one space horizontal (either left or right).  The
// second four options are, one space vertically (either up or down) and two
// spaces horizontally (either left or right).
//
// * Conventions
//
// Its simplest to form the (2d) grid into a (1d) linier coordinate system.
// I arbitraily chose the bottom left hand corner to be 0, and the top right
// corner to be MAX_GRID*MAX_GRID - 1.  Hence a move of two up and one left
// would translate to currentPosition + 2 - 1*grid;
//
// * Results
// The interesting thing about this problem is that there is no obvious and
// simple solution to even the number of paths.  Using a standard grid of 
// 8 (or an 8x8 chessboard) there are 64* 2**4 * 3**8 * 4**20 * 6**16 * 8**16) 
// or (~5 * 10**45) potential paths and somewhere a correct path is very
// roughly 1 in a million.  One cpu day reveals 1.4 million paths.
//
*/

#include <stdio.h>
#include <memory.h>
#include <stdlib.h>

/* MAX_GRID of 8 is a standard keyboard */
#define MAX_GRID 11


/* GLOBAL VARIABLES */

const char gHelpNotes[] = 
  "\n\nknights [OPTIONS] [SEARCHPATH]"
  "\nknights crossing program (v1.0, 03Aug04), by chris durso, ref. www.durso.org"
  "\n\nOPTIONS"
  "\n\n-v\n--verbose \tprint more information"
  "\n-g=#\n--grid=#\tuse grid of size # (default 8 for 8x8)."
  " Minimum 3, Maximum %d.  "
  "\n\t\tNote no white spaces!"
  "\n\nSEARCHPATH\n"
  "\nThe optional SEARCHPATH is a sequence of positive numbers not longer than"
  "\ngrid x grid in length, and thier numerical values in the range of 0 to "
  "\ngrid x grid and non repeating. Each number is sequence must be a legal "
  "\nchess knights move from the previous number in the SEARCHPATH."
  "\n\nCOORDINATE SYSTEM"
  "\n\nThe bottom left hand corner is noted as 0 and the increment first"
  "\ngoes up and wraps to the right.  The bottom left is 0, the top"
  "\nleft is grid -1, and the top right square is grid x grid -1.\n";

/*
// example of legalMovesMatrix supporting a grid of 8 x 8 squares of the 
// knights travel problem
// * for any square there is at most eight legal destinations
// * each row is '-1' terminated, hence 'MAX_ROW+1' below
// * to simplify the inverse
// matrix format (all chars) 
//     [0]   dest0, dest1, .. destn,-1
//     [1]   dest0, dest1, .. destn,-1
//     ...
//     [63]  dest0, dest1,... destn,-1
//     [64]  0,  0,  0,  0,  0,  0,  0,  0,  0  
//     [65]  1,  1,  1,  1,  1,  1,  1,  1,  1
//     ...  
//     [127]63, 63, 63, 63, 63, 63, 63, 63, 63
*/
char gLegalMovesMatrix[MAX_GRID*MAX_GRID*2][MAX_GRID+1];

/* helpful offset to get the current position from gLegalMovesMatrix */
int  gLegalMoveToIndexOff;

/* track where have we been */
char gTally[MAX_GRID*MAX_GRID];

/* positionStack holds current position of ~5E54 different paths  */
char *gPositionStack[MAX_GRID*MAX_GRID];

/* how may current hits in gPositionStack */
int gHit;


/* how big is our grid */
int gGrid;


/* END GLOBALS */


int rank(int i){
  return i/gGrid + 1;
}

int file( int i){
   return i%gGrid + 1;
}

/*
// using a lookup table instead of integer '/' saves approximately 7%
// of algorithm time
*/
int 
legalMovesToPosition(char* ptr){
  /* return (ptr - &(gLegalMovesMatrix[0][0]))/9; */
  return *(ptr + gLegalMoveToIndexOff); 
}

void printLegalMoves(){
 
  printf("\ngLegalMoveToIndexOff %d \n", gLegalMoveToIndexOff);
  int i;
  int gridSq = gGrid*gGrid;
  for(i = 0; i < gridSq;i++ ){
    int r = rank(i);
    int f = file(i);
  
    printf("%d (r:%d, f:%d) -> ", i, r, f);
    int moveIndex;
    for( moveIndex = 0; moveIndex < 8; moveIndex++){
      if((char)-1 == gLegalMovesMatrix[i][moveIndex])
	break;
      printf(" %d(%d,%d) ", gLegalMovesMatrix[i][moveIndex]
	     ,rank(gLegalMovesMatrix[i][moveIndex])
	     ,file(gLegalMovesMatrix[i][moveIndex]) );
     }
    printf("\n");
  }
  
  /* print the offsets */

  for(i = gridSq; i < 2*gridSq; i++ ){

    printf("%.2d index  ", i - gridSq);
    int col;
    for( col = 0; col < 8; col++){
      printf(" %.2d ", gLegalMovesMatrix[i][col]);
    }
    printf("\n");
  }
  
}

struct intPair{
  int file; 
  int rank;
};

void initLegalMoves(){

  int i;
  struct intPair moves[] = {{-1,-2},  /* ( 1 down 2 left  ) */
		     {+1,-2},  /* ( 1 up   2 left  ) */
		     {-2,-1},  /* ( 2 down 1 left  ) */
		     {+2,-1},  /* ( 2 up   1 left  ) */
		     {-2,+1},  /* ( 2 down 1 right ) */
		     {+2,+1},  /* ( 2 up   1 right ) */
		     {-1,+2},  /* ( 1 down 2 right ) */
		     {+1,+2},  /* ( 1 up   2 right ) */
		     {0,0}    /*  null terminated   */ };
	       

  int gridSq = gGrid*gGrid;
  gLegalMoveToIndexOff = gridSq*9;
  memset(gLegalMovesMatrix, -1, sizeof(gLegalMovesMatrix));
    
  /* for every position define its legal moves */
  for(i = 0; i < gridSq; i++ ){
    int colIndex;
    struct intPair *moveIndex;
    
    for(colIndex = 0,  moveIndex = moves; moveIndex->rank; ++moveIndex ){
      int r,f;
            
      r = rank(i) + moveIndex->rank;
      f = file(i) + moveIndex->file;
      
      if( r > 0 && r <= gGrid && f > 0 && f <= gGrid){
	gLegalMovesMatrix[i][colIndex++]= (r-1)*(gGrid) + (f-1);
      }
    }
      
    memset((char*)(gLegalMovesMatrix[i]) + gLegalMoveToIndexOff , i, 9);
  }
}

/* 
// initTallyAndPosition will test that each member of initialStack
// is really legal and set gTally, gPositionStack, and gHit, such that  
// when entering findSequentialSolutions the search will pick up from
// this point, specifically gPositionStack[gHit] will be ready to record
// a hit.
// 
// return failure (true) if any point in sequence is not accesible from
// previous point else there is any repetition 
// 
*/

int 
initTallyAndPositionStack(char* currentStack){
  int prev = -1;
  int maxIndex = gGrid*gGrid;
  
  memset(gTally, 0, sizeof(gTally));  
  gHit = 0;

  /* enter each of the steps from the initial stack */
  for(;-1 != *currentStack && *currentStack > -1; ++currentStack){
    int i;

    if(-1 == prev ){
      prev = *currentStack;
      continue;
    }

    if(gTally[*currentStack] != 0 || prev == *currentStack){
      printf("\nIllegal, SEARCHPOSITION %d is repeated!", 
	     *currentStack);
      printf("\n");
      return 1;
    }
    
    /* check all 9 potential prev moves to see if it is possible to get here 
    // from there
    */
    for(i = 0; i < 9 && (gLegalMovesMatrix[prev][i] != *currentStack); ++i)
      ;

    if(9 == i){
      int cur = *currentStack;
      printf("\nIllegal, SEARCHPOSITION %d is not accesible from %d. ",
	     cur, prev);
      printf("\n");
      return 2;
    }
    
    gTally[prev]= 1;
    gPositionStack[gHit++] = &gLegalMovesMatrix[prev][i];

    prev = *currentStack;
  }
  
  /* special cases exactly zero or one element on SERCHPOSITION stack */
  if( 0 == gHit ){
    if(-1 == prev)
      prev = 0;

    gTally[prev] = 1;
    gPositionStack[gHit++ ] = &gLegalMovesMatrix[prev][0];
  }
    
#if 0
  int i;
  printf("\ninitial %d", legalMovesToPosition(gPositionStack[0]));
  for(i = 0; i < gHit ; i++)
    printf("\n\t dest %d ", *gPositionStack[i]);
  printf("\n");
#endif
  
  return 0; /* success */
}

int initialize(char *initialStack){
  initLegalMoves();
  return initTallyAndPositionStack(initialStack); 
}


void findSequentialSolutions(){

  int next = 0;
  unsigned long long miss = 0;
  unsigned long long paths = 0;
  int topSq = gGrid*gGrid -1;

  if( 0 == gHit)
    next = *gPositionStack[gHit];
  else
    next = *gPositionStack[gHit - 1];

  
  do {
    if(0 == gTally[next]){

      /* a good hit ! */
      gTally[next] = 1;
      gPositionStack[gHit] = gLegalMovesMatrix[next];
      
      if( topSq == gHit ){
	/* completed the path, print the results */
	printf("\n");
	int i;
	for( i = 0; i <= topSq ; i++)
	  printf("%d ", legalMovesToPosition(gPositionStack[i]));

	paths++;
	printf("\npath %llu found after %llu many mis steps \n", 
	       paths,  miss );
     
	gHit++;
      } else {
	/* record hit
	// push stack,
	// and calculate next position
	*/
	next = *(gPositionStack[gHit++]);
      }

    } else {
	
      /* been there ! go elsewhwere
      // the current value of 'next' is not a valid place
      */

      while(-1 == *(gPositionStack[gHit-1]+ 1) ){
	 gHit--;
	 if(0 == gHit ){
	   printf("\nALL DONE! have exhausted all paths on grid of %d "
		  "starting with %d", 
		  gGrid, legalMovesToPosition(gPositionStack[gHit]));
	   printf("\ntotal paths found %llu with %llu mis steps \n", 
		  paths,  miss );
	   return;
	 }
	 /* erase a position mark */
	 gTally[legalMovesToPosition(gPositionStack[gHit])] = 0;
      }
      
      miss ++;
      /* ok to try next */
      gPositionStack[gHit-1]++;
      next = *(gPositionStack[gHit-1]);
    }
  } while(1);
  
}

/*
// myStrCmp returns match forwarding begin until after "matchStr" 
*/
int myStrCmp( char** begin, const char* matchStr){
  
  int sl = strlen(matchStr);
  if(memcmp(*begin, matchStr, sl))
    return 0;
  *begin += sl;
  
  return 1;
}

int main(int args, char** argv){

  int i, num;
  int verbose = 0;
  gHit = 0;
  gGrid = 8;
  char initialStack[MAX_GRID*MAX_GRID + 1];
  int initialStackCount = 0;
  
  
  memset((void*)initialStack, -1, sizeof(initialStack));
  
  for(++argv, i = 1; i <= (args-1); ++i, argv++){
    char **arg = argv;
    
    if      (myStrCmp(arg, "-v") || myStrCmp(arg, "--verbose")){
      verbose = 1;
    }else if(myStrCmp(arg, "-h") || myStrCmp(arg, "--help")){
      printf(gHelpNotes, MAX_GRID);
      return 0;
    }else if(myStrCmp(arg, "-g=") || myStrCmp(arg, "--grid=")){
      gGrid = atoi(*arg);
      if( gGrid > MAX_GRID || gGrid < 3 ){
	printf("\nValue for grid size %d out of range of 3-%f, exiting.\n", 
	       gGrid, MAX_GRID);
	return -1;
      }
    }
    else if(1 == sscanf(*arg, "%d", &num )){
      if(initialStackCount == gGrid*gGrid ){
	printf("\nToo many elements in the SEARCHPATH only permitted %d"
	       " for grid of size %d\n", 
	       gGrid*gGrid, gGrid);
	return -3;
      }
      initialStack[initialStackCount++] = num;
    } else {
      printf("\nillegal option \"%s\", try --help for options\n", *arg);
      return -2;
    }
  }

  if( initialize(initialStack))
    return -1; /* the initial stack is invalid */

  if(verbose)
    printLegalMoves();
  
  findSequentialSolutions();

  return 0;
}