#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <windows.h>
 
#define NODEBUG
 
#define TIMEELAPSED {printf("\tTime elapsed: %lu\n", GetTickCount() - startTime);}
 
const int horizontal[8] = {2, 1, -1, -2, -2, -1, 1, 2};
const int vertical[8] = {-1, -2, -2, -1, 1, 2, 2, 1};
 
unsigned int boardsSolved = 0;
unsigned char board[8*8] = {1};
unsigned int startTime;
 
void printBoard(const unsigned char *board){
  unsigned int i, j;
 
  for(i = 0; i < 8; i++){
    for(j = 0; j < 8; j++){
      printf("%02u ", board[i*8+j]);
    }
    putchar('\n');
  }
  putchar('\n');
 
  return;
}
 
int solveit(const unsigned int *knightPos, const unsigned int steps){
  if(steps == 64){
    printf("Board (%u) solved:\n", ++boardsSolved);
    printBoard(board);
    TIMEELAPSED
    return 0;
  }
 
  /*Algo:
    calc xpos
    if xpos is valid:
      calc ypos
      if ypos is valid:
      if board[x][y] is not stepped on
        set board[x][y] to steps
        call self with updated position and board
  */
 
  unsigned int i;
  unsigned int curPos[2];
 
  for(i = 0; i < 8; i++){
    curPos[0] = knightPos[0] + horizontal[i];
    if(curPos[0] > 7){
      continue;
    }
    else{
      curPos[1] = knightPos[1] + vertical[i];
      if(curPos[1] > 7){
        continue;
      }
      else{
        if(board[curPos[0] + curPos[1]*8] == 0){
          board[curPos[0] + curPos[1]*8] = steps+1;
 
#ifdef DEBUG
          printf("Board after %u steps: \n", steps);
          printBoard(board);
#endif
          solveit(curPos, steps+1);
          board[curPos[0] + curPos[1]*8] = 0;
        }
        else{
          continue;
        }
      }
    }
  }
 
#ifdef DEBUG
  else{
    printf("All possibilities tried, returning.\n");
  }
#endif
 
  return -1;
}
 
 
int main(){
  printf("Knights Tour Finder v0.1\n");
  startTime = GetTickCount();
 
  unsigned int startPos[2] = {0};
 
  printf("Starting with this board: \n");
  printBoard(board);
 
  solveit(startPos, 1);
 
  printf("Done");
  return 0;
}