/*
 * knights.c
 * File revision 0
 * Find a solution to the Knight's Tour problem.
 * (c) 2000 Jacob Lundberg, jacob@chaos2.org
 */


#include <errno.h>
#include <string.h>


/* Boolean logic. */
typedef enum boolean {
   false = 0,
   true = !false
} bool;


/* The boards. */
char *board;
unsigned short *moves;


/* Public board characteristics. */
int wdt, hgt, pos, mov;


/* Conversions. */
#define  C2_1D(x, y)    ((x) + wdt * (y))
#define  C1_2X(z)       ((z) % wdt)
#define  C1_2Y(z)       ((z) / wdt)


/* Moves, with boundary checking (out of bounds ... -1). */
#define  M1x2y(x, y)    (((x) - 1 < 0) ? -1 : ((y) - 2 < 0) ? -1 : C2_1D((x) - 1, (y) - 2))
#define  M2x1y(x, y)    (((x) - 2 < 0) ? -1 : ((y) - 1 < 0) ? -1 : C2_1D((x) - 2, (y) - 1))
#define  M1x2Y(x, y)    (((x) - 1 < 0) ? -1 : ((y) + 2 >= hgt) ? -1 : C2_1D((x) - 1, (y) + 2))
#define  M2x1Y(x, y)    (((x) - 2 < 0) ? -1 : ((y) + 1 >= hgt) ? -1 : C2_1D((x) - 2, (y) + 1))
#define  M1X2y(x, y)    (((x) + 1 >= wdt) ? -1 : ((y) - 2 < 0) ? -1 : C2_1D((x) + 1, (y) - 2))
#define  M2X1y(x, y)    (((x) + 2 >= wdt) ? -1 : ((y) - 1 < 0) ? -1 : C2_1D((x) + 2, (y) - 1))
#define  M1X2Y(x, y)    (((x) + 1 >= wdt) ? -1 : ((y) + 2 >= hgt) ? -1 : C2_1D((x) + 1, (y) + 2))
#define  M2X1Y(x, y)    (((x) + 2 >= wdt) ? -1 : ((y) + 1 >= hgt) ? -1 : C2_1D((x) + 2, (y) + 1))


void init_board(void) {
/*
 * init_board()
 * Prep a board by determining the degrees of each square.
 */

   int iter, curx, cury;

   /* Check each move from each square and count. */
   for(iter = 0; iter < wdt * hgt; ++iter) {
      curx = C1_2X(iter);
      cury = C1_2Y(iter);
      if(M1x2y(curx, cury) >= 0)
         ++(board[iter]);
      if(M2x1y(curx, cury) >= 0)
         ++(board[iter]);
      if(M1x2Y(curx, cury) >= 0)
         ++(board[iter]);
      if(M2x1Y(curx, cury) >= 0)
         ++(board[iter]);
      if(M1X2y(curx, cury) >= 0)
         ++(board[iter]);
      if(M2X1y(curx, cury) >= 0)
         ++(board[iter]);
      if(M1X2Y(curx, cury) >= 0)
         ++(board[iter]);
      if(M2X1Y(curx, cury) >= 0)
         ++(board[iter]);
   }

}


void init_moves(void) {
/*
 * init_moves()
 * Set up the moves list.
 */

   /* Clear the moves table. */
   memset(moves, 0, wdt * hgt * sizeof(unsigned short));

}


void set_pos(int newpos) {
/*
 * set_pos()
 * Move the current location.
 * No bounds checking, and _don't_ call it twice on the same location...
 */

   int ipos;
   int curx = C1_2X(newpos), cury = C1_2Y(newpos);

   /* Move. */
   pos = newpos;
   moves[pos] = mov;

   /* Reduce degrees of adjacent squares. */
   ipos = M1x2y(curx, cury);
   if(ipos >= 0 && board[ipos])
      --(board[ipos]);
   ipos = M2x1y(curx, cury);
   if(ipos >= 0 && board[ipos])
      --(board[ipos]);
   ipos = M1x2Y(curx, cury);
   if(ipos >= 0 && board[ipos])
      --(board[ipos]);
   ipos = M2x1Y(curx, cury);
   if(ipos >= 0 && board[ipos])
      --(board[ipos]);
   ipos = M1X2y(curx, cury);
   if(ipos >= 0 && board[ipos])
      --(board[ipos]);
   ipos = M2X1y(curx, cury);
   if(ipos >= 0 && board[ipos])
      --(board[ipos]);
   ipos = M1X2Y(curx, cury);
   if(ipos >= 0 && board[ipos])
      --(board[ipos]);
   ipos = M2X1Y(curx, cury);
   if(ipos >= 0 && board[ipos])
      --(board[ipos]);

}


bool move_knight() {
/*
 * move_knight()
 * Scan for another move, via the heuristic.
 */

   int minpos = -1, mindeg = 9;
   int curx = C1_2X(pos), cury = C1_2Y(pos);
   int newpos;

   /* Find the move with the minimum degree. */
   newpos = M1x2y(curx, cury);
   if(newpos >= 0 && moves[newpos] == 0 && board[newpos] < mindeg) {
      mindeg = board[newpos];
      minpos = newpos;
   }
   newpos = M2x1y(curx, cury);
   if(newpos >= 0 && moves[newpos] == 0 && board[newpos] < mindeg) {
      mindeg = board[newpos];
      minpos = newpos;
   }
   newpos = M1x2Y(curx, cury);
   if(newpos >= 0 && moves[newpos] == 0 && board[newpos] < mindeg) {
      mindeg = board[newpos];
      minpos = newpos;
   }
   newpos = M2x1Y(curx, cury);
   if(newpos >= 0 && moves[newpos] == 0 && board[newpos] < mindeg) {
      mindeg = board[newpos];
      minpos = newpos;
   }
   newpos = M1X2y(curx, cury);
   if(newpos >= 0 && moves[newpos] == 0 && board[newpos] < mindeg) {
      mindeg = board[newpos];
      minpos = newpos;
   }
   newpos = M2X1y(curx, cury);
   if(newpos >= 0 && moves[newpos] == 0 && board[newpos] < mindeg) {
      mindeg = board[newpos];
      minpos = newpos;
   }
   newpos = M1X2Y(curx, cury);
   if(newpos >= 0 && moves[newpos] == 0 && board[newpos] < mindeg) {
      mindeg = board[newpos];
      minpos = newpos;
   }
   newpos = M2X1Y(curx, cury);
   if(newpos >= 0 && moves[newpos] == 0 && board[newpos] < mindeg) {
      mindeg = board[newpos];
      minpos = newpos;
   }

   /* We halt when we have no moves. */
   if(minpos == -1)
      return(false);

   /* Change our current position. */
   ++mov;
   set_pos(minpos);

   /* Return success. */
   return(true);

}


void out_board(void) {
/*
 * out_board()
 * Output the current board.
 */

   int iter;

   /* Print out the board, properly shaped. */
   for(iter = 0; iter < wdt * hgt; ++iter) {
      if(iter % wdt == wdt - 1)
         printf("%i\n", board[iter]);
      else
         printf("%i ", board[iter]);
   }
   printf("\n");

}


void out_moves(void) {
/*
 * out_moves()
 * Output the current moves list.
 */

   int iter;

   /* Print out the board, properly shaped. */
   for(iter = 0; iter < wdt * hgt; ++iter) {
      if(moves[iter]) {
         if(iter % wdt == wdt - 1)
            printf("%3i\n", moves[iter]);
         else
            printf("%3i ", moves[iter]);
      } else {
         if(iter % wdt == wdt - 1)
            printf(" %c \n", '.');
         else
            printf(" %c  ", '.');
      }
   }

   /* Indicate if we found a full tour. */
   if(mov < wdt * hgt)
      printf("Failed to find a tour.\n\n");
   else
      printf("\n");

}


int main(int argc, char **argv) {
/*
 * main()
 * Set up the board and run the heuristic.
 */

   /* Check the number of args. */
   if(argc != 5) {
      printf("knights: args should be width, height, starting x, starting y\n");
      return(true);
   }

   /* Get the arg values. */
   wdt = atoi(argv[1]);
   hgt = atoi(argv[2]);
   pos = atoi(argv[3]) + wdt * atoi(argv[4]);

   /* Check the arg values. */
   if(wdt < 1 || hgt < 1 || pos < 0 || pos > (wdt * hgt - 1)) {
      printf("knights: argument(s) out of range\n");
      errno = EINVAL;
      return(true);
   }

   /* Allocate the boards. */
   board = (char *)malloc(wdt * hgt * sizeof(char));
   moves = (unsigned short *)malloc(wdt * hgt * sizeof(unsigned short));
   if(board == NULL || moves == NULL) {
      printf("knights: unable to allocate array(s)\n");
      errno = ENOMEM;
      return(true);
   }

   /* Set up the boards. */
   init_board();
   init_moves();

   /* Move onto the initial square. */
   mov = 1;
   set_pos(pos);

   /* Run the heuristic. */
   while(move_knight()) /* run */;

   /* Print out the results. */
//   out_board();
   out_moves();

   /* Finis. */
   free(board);
   free(moves);
   return(false);

}