/*****************
 * qN.c 
 *
 *  will solve the "eight queens" problem, 
 *  which is to place eight queens on a chess
 *  board such that no two can see each other
 *  along any row, column, or diagonal.
 *
 *  Approach:
 *   brute force, with recursion.  Place one queen per row, 
 *   marking all spots she can "see" as unavailable.
 *   Check all possible combinations, counting
 *   (and optionally printing out) all that work.
 *
 *   Also find 8 rotations and reflections, and check to see
 *   how many of the 8 look like each solution.  Use this
 *   to calculate how many unique solutions for each N, too.
 *
 * This "qN" version I used to run some other numbers besides the 
 * chessboard N=8.
 *
 *     Jim Mahoney 10/19/98
 *
 * history
 * 
 *   - added elapsed time 2/7/03
 *
 *****************************/

#include <stdio.h>
#include <time.h>

/* =========================================================== */
/* ====== globals =========================================== */
/* ========================================================== */

/*******************
 **  These set the range of N's to look at.  
 **  Set them to 
 ******/
int firstN = 2;
int lastN = 16;		/* MAKE SURE Nsize IS AT LEAST THIS BIG */

/* The board will be N x N */
#define Nsize 24
int N;

/* number of possible symmetries of a square pattern */
#define NumSymmetries 8

/* 1 => yes, print each position as we go;  0=> no, just count  */
/*   and store 'em.  */
#define print_flag 0
/* same; 0 or 1 depending on whether symmetry stuff should be printed. */
#define PrintAnalysis 0

/*  global "chess board". */  
/*  Each entry is 0 for empty; >0 for queen, <0 for "can see it"  */
/*  We keep track of which queen "sees" each square so that we */
/*  can back up easily, column by column.
/*  Indices are [row][column] */
int board[Nsize][Nsize];

int board_print[Nsize][Nsize];	/* only queen postions, not "seeing" parts */

   /* storage for symmetry calculations */
int symm[Nsize][Nsize][NumSymmetries];

#define empty 0

/* Number of distinct solutions found */
int solution_count = 0;

/* Number of unique solutions found */
float unique_count = 0.0;

/* =========================================================== */
/* ====== code ================================================= */
/* =========================================================== */


/* ------------------------------------------------------------ */
/* sign(int j) returns -1,0,1 depending on the sign of j.  */
int sign(int j){
  if (j>0) return(1);
  else if (j==0) return(0);
  else return(-1);
}

/* ------------------------------------------------------------ */
/* check to see if Symm board is same as board_print */
int IsEqual(int sy){
  int r,c;
  for (r=0;r<N;r++){
    for (c=0;c<N;c++){
      if ( sign(symm[r][c][sy]) != sign(board_print[r][c]) ) return(0);
    }
  }
    return(1);
}

/* ------------------------------------------------------------ */
/* symmetry analysis */
/* Figure out how many distinct variations of the given pattern */
/* are also in the list.  Return the "symmetry number", which */
/* is how many times rotations/reflections are in the list. */
int analysis(){ /* analyze board_print */
  int r,c, p, q;
  int n_symm=0;

  /* find the eight symmetric variations of this position */
  for (r=0;r<N;r++){
    for (c=0;c<N;c++){
      symm[r][c][0]    =board_print[r][c];
      symm[r][N-c-1][1]  =board_print[r][c];
      symm[c][r][2]    =board_print[r][c];
      symm[c][N-r-1][3]  =board_print[r][c];
      symm[N-r-1][c][4]  =board_print[r][c];
      symm[N-r-1][N-c-1][5]=board_print[r][c];
      symm[N-c-1][r][6]  =board_print[r][c];
      symm[N-c-1][N-r-1][7]=board_print[r][c];
    }
  }
  for (p=0; p<8; p++){
    if (IsEqual(p)) n_symm++;
  }

  return(n_symm);
}

/* ------------------------------------------------------------ */
/* print out the board */
void print_it(){
  int r,c;
  for (r=0;r<N;r++){	/* loop over rows */
    for (c=0;c<N;c++){	/*  and columns  */
      printf(" %d",board_print[r][c]);
    }
    printf("\n");
  }
}


/* ------------------------------------------------------------ */
/* do the right thing with what we've found */
void found_solution(){
  int r,c;
  int sym_num;

  solution_count++;
  sym_num=analysis(); /* find symmetry number of this solution */
  unique_count += ((float)(sym_num)/NumSymmetries);

  if (print_flag) {
    printf(" \n ----- sol'n %d -------- ", solution_count);
    print("  distinct symm = %d \n", sym_num);
    print_it();
    printf("\n");
  }
}

/* ------------------------------------------------------------ */
/* zero the board */
void init_board(){
  int r,c;
  for (r=0;r<N;r++){	/* loop over rows */
    for (c=0;c<N;c++){	/*  and columns  */
      board[r][c]=0;
      board_print[r][c]=0;
    }
  }
}


/* ------------------------------------------------------------ */
/* Put down a queen at the given row and column.  */
/* Mark the spots in the columns to the right which it can "see", */
/* but only if that spot hasn't been marked before. */
void place_queen(int row, int column){
  int marker = column+1;
  int c; /* column */
  int r; /* row */
  board[row][column] = marker;	/* mark location of this queen */
  board_print[row][column] = marker;
  for (c=column+1, r=row; c<N; c++) { 	/* mark the row to the right */
    if (board[r][c]==empty) board[r][c] = marker;
  }
  for (c=column+1, r=row-1; (r>=0)&&(c<N) ;r--, c++){	/*  up and right */
    if (board[r][c]==empty) board[r][c] = marker;
  }
  for (c=column+1, r=row+1;(r<N)&&(c<N);r++,c++){	/* down &  right */
    if (board[r][c]==empty) board[r][c] = marker;
  }
}

/* -------------------------------------------------------- */
/* undo what place_queen did  */
void erase_queen(int row, int column){
  int marker = column+1;
  int c; /* column */
  int r; /* row */
  board[row][column] = empty;	/* erase original spot */
  board_print[row][column] = empty;
  for (c=column+1;c<N;c++) { 	/* erase row to right */
    if (board[row][c]==marker) board[row][c] = empty; 
  }
  for (c=column+1, r=row-1; (r>=0)&&(c<N) ;r--, c++){	/*  up and right */
    if (board[r][c]==marker) board[r][c] = empty;
  }
  for (c=column+1, r=row+1;(r<N)&&(c<N);r++,c++){	/* down &  right */
    if (board[r][c]==marker) board[r][c] = empty;
  }

}


/* ------------------------------------------------------------ */
/* --- recursively try to put a queen in a each column ------- */
int do_a_column(int column){
  int row; /* which row we're going to try */
  char ans[10];	/* for debugging "pauses" */

  /* the board has columns 0,1,...,(N-1), so if we get */
  /* to column N then we've found a successful solution. */
  /* Just count and print it and go onto the next. */
  if (column==N){
    found_solution();
    return;
  }
  
  /* loop over each possible row position in this column */
  for (row=0;row<N;row++){
    if (board[row][column]==empty) {
      place_queen(row,column);  /* This spot might work; 
				   put a queen here and mark board */
      /* used for debugging */
      /*
  printf(" ---------------------------- \n");
  printf(" Queen %d just placed at %d, %d : \n",(column+1), row, column);
  print_it();
  gets(ans);
      */

      do_a_column(column+1);    /* Examine next column. */
      erase_queen(row,column);  /* Undo the "place_queen" marking */


      /* used for debugging */
      /*
  printf(" ---------------------------- \n");
  printf(" Queen %d now erased from %d, %d : \n",(column+1), row, column);
  print_it();
  gets(ans);
      */

    } /* end if (board[row][column]==empty  */
  } /* end for loop over possible row pistions */

} /* do_a_column() */


/* --------------------------------------------------------*/
/* --- main ------------ */
int main(){
  double lastSec, thisSec;

  printf(" --------- N Queens ---------------------- \n");
  lastSec = ((double)clock())/CLOCKS_PER_SEC;

  for (N=firstN; N<(lastN+1); N++)
    {

  printf(" \n");
  printf(" Board size is %d by %d.  Working...",(N),(N));

  init_board();		/* set things up */
  solution_count=0;
  unique_count=0.0;

  do_a_column(0);	/* recursive call that finds solutions. */

  printf("  done.\n");
  printf("  Number of solutions found = %d \n",solution_count);  
  printf("  Number of unique positions = %d .\n", (int)(unique_count+0.499));

  thisSec =  ((double)clock())/CLOCKS_PER_SEC;
  printf("  Elapsed time = %g seconds.\n", thisSec-lastSec);
  lastSec = thisSec;

    }

}