/*
 * queens.c
 * File revision 0
 * Find solutions to the Searching in Wonderland problem.
 * (c) 2000 Jacob Lundberg, jacob@chaos2.org
 */


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


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


/* Two states for board locations.  empty `.' and queen `Q' */
#define  EMPTY          '.'
#define  QUEEN          'Q'


/* The flat size of the board in bytes. */
#define  BOARD_SIZE     size * size * sizeof(char)


/*
 * Two dimension -> One dimension converters.
 * There are eight isomorphic transformations.
 * They are:
 *   FX_FY  Identity
 *   RX_FY  Mirror image over X axis
 *   FX_RY  Mirror image over Y axis
 *   RX_RY  Mirror image over both axes (or two rotations)
 *   RL_XY  Rotate left
 *   RR_XY  Rotate right
 *   FL_FW  Flip top-right and bottom-left corners
 *   FL_RV  Flip top-left and bottom-right corners
 */
#define  FX_FY(x, y)    ((x) + (y) * size)
#define  RX_FY(x, y)    (size - (x) - 1 + (y) * size)
#define  FX_RY(x, y)    ((x) + (size - (y) - 1) * size)
#define  RX_RY(x, y)    (size - (x) - 1 + (size - (y) - 1) * size)
#define  RL_XY(x, y)    FX_RY((y), (x))
#define  RR_XY(x, y)    RX_FY((y), (x))
#define  FL_FW(x, y)    FX_FY((y), (x))
#define  FL_RV(x, y)    RX_RY((y), (x))


/* Define a light linked list to hold valid boards. */
typedef struct _boardlist {
   struct _boardlist *next;
   char *board;
} boardlist;


/* Board info is public to reduce copies. */
boardlist *head = NULL;
boardlist *tail = NULL;
unsigned int size;
char *board;


void garbage(void) {
/*
 * garbage()
 * Garbage in, garbage out.
 */

   boardlist *temp = head;

   /* Toss the working board. */
   free(board);

   /* Clear out the entire list. */
   while(head != NULL) {
      head = head->next;
      free(temp->board);
      free(temp);
      temp = head;
   }

}


void display(void) {
/*
 * display()
 * Write out the list.
 */

   boardlist *temp = head;
   int counter;

   if(head == NULL)
      printf("no safe arrangements of %i queens on %i by %i board\n\n", size, size, size);

   while(temp != NULL) {
      for(counter = 0; counter < size * size; ++counter) {
         if(counter % size == size - 1)
            printf("%c\n", temp->board[counter]);
         else
            printf("%c ", temp->board[counter]);
      }
      printf("\n");
      temp = temp->next;
   }

}


char *duplicate(char *src) {
/*
 * duplicate()
 * Create a duplicate or empty board.
 */

   char *board;

   /* Allocate the new board. */
   board = (char *)malloc(BOARD_SIZE);
   if(board == NULL) {
      printf("queens: size %i memory allocation failed\n", BOARD_SIZE);
      garbage();
      errno = ENOMEM;
      exit(true);
   }

   /* Scribble data on the new board. */
   if(src == NULL)
      memset(board, EMPTY, BOARD_SIZE);
   else
      memcpy(board, src, BOARD_SIZE);

   return(board);

}


void add_winner(void) {
/*
 * add_winner()
 * Add a winner to the chain.
 */

   boardlist *temp;

   /* Allocate a new list entry. */
   temp = (boardlist *)malloc(sizeof(boardlist));
   if(temp == NULL) {
      printf("queens: size %i memory allocation failed\n", sizeof(boardlist));
      garbage();
      errno = ENOMEM;
      exit(true);
   }

   /* Duplicate the board. */
   temp->board = duplicate(board);

   /* Append onto the list. */
   temp->next = NULL;
   if(head == NULL)
      tail = head = temp;
   else
      tail->next = temp;
   tail = temp;

}


bool safe(unsigned int x, unsigned int y) {
/*
 * safe()
 * Test whether (x, y) is safe for a queen.
 * THIS TEST ONLY TESTS THE LEFTWARD TRIANGLE!
 * Below, in testing Q, only . will be tested.
 *   . _ _ _
 *   _ . _ _
 *   . . Q _
 *   _ . _ _
 */

   int lx, ly;

   /* Test for Queens left. */
   for(lx = x - 1; lx >= 0; --lx)
      if(board[FX_FY(lx, y)] == QUEEN)
         return(false);

   /* Test for Queens up left. */
   for(lx = x - 1, ly = y - 1; lx >= 0 && ly >= 0; --lx, --ly)
      if(board[FX_FY(lx, ly)] == QUEEN)
         return(false);

   /* Test for Queens down left. */
   for(lx = x - 1, ly = y + 1; lx >= 0 && ly < size; --lx, ++ly)
      if(board[FX_FY(lx, ly)] == QUEEN)
         return(false);

   /* No conflicts. */
   return(true);

}


bool is_new(void) {
/*
 * is_new()
 * True if the working board is not a morph of an old board.
 * Note that no test is made for equivalence here.
 */

   char subchar;
   unsigned int row, col;
   boardlist *list = head;
   bool revx, revy, revxy, rotr, rotl, flfw, flrv;

   /* Search and search and search. */
   while(list != NULL) {
      revx = revy = revxy = rotr = rotl = flfw = flrv = true;
      for(row = 0; row < size; ++row) {
         for(col = 0; col < size; ++col) {
            /* Remember the subject char so things go faster. */
            subchar = board[FX_FY(row, col)];
            /* Reversal of X. */
            if(revx && subchar != list->board[RX_FY(row, col)])
               revx = false;
            /* Reversal of Y. */
            if(revy && subchar != list->board[FX_RY(row, col)])
               revy = false;
            /* Reversal of X and Y (double rotation). */
            if(revxy && subchar != list->board[RX_RY(row, col)])
               revxy = false;
            /* Leftwards rotation. */
            if(rotl && subchar != list->board[RL_XY(row, col)])
               rotl = false;
            /* Rightwards rotation. */
            if(rotr && subchar != list->board[RR_XY(row, col)])
               rotr = false;
            /* Flip along forward slash. */
            if(flfw && subchar != list->board[FL_FW(row, col)])
               flfw = false;
            /* Flip along backward slash. */
            if(flrv && subchar != list->board[FL_RV(row, col)])
               flrv = false;
         }
         /* Check at each row to see if we can short-circuit. */
         if(!(revx || revy || revxy || rotr || rotl || flfw || flrv))
            break;
      }
      /* If we have a winner then we need to stop. */
      if(revx || revy || revxy || rotr || rotl || flfw || flrv)
         return(false);
      list = list->next;
   }

   /* If we never broke out with a morph then there isn't one. */
   return(true);

}


void column(int col) {
/*
 * column()
 * Test the queen locations in columns starting at a given level.
 */

   unsigned int step;

   /* Search each position in this column. */
   for(step = 0; step < size; ++step) {
      board[col + size * step] = QUEEN;
      if(safe(col, step)) {
         /* This is a safe position in this column. */
         if(col == size - 1) {
            /* We've found a safe board! */
            if(is_new())
               add_winner();
         } else {
            /* Check the next column. */
            column(col + 1);
         }
      }
      board[col + size * step] = EMPTY;
   }

}


int main(int argc, char **argv) {
/*
 * main()
 * Slurp up the args and find the queens.
 */

   /* Make sure we have been told the board size. */
   if(argc != 2) {
      printf("queens: exactly one numerical arg giving the board size is accepted\n");
      errno = EINVAL;
      exit(true);
   }

   /* Get the board size. */
   size = atoi(argv[1]);

   /* Check bounds on the board size. */
   if(size < 1 || size > 4096) {
      printf("queens: board size of %u is too %s\n", size, size ? "large" : "small");
      errno = EINVAL;
      exit(true);
   }

   /* Allocate the board space. */
   board = duplicate(NULL);

   /* Brute force locate all the valid unique solutions. */
   column(0);

   /* Display the list of winning boards. */
   display();

   /* Done. */
   garbage();
   return(false);

}