/*****************
 * q8.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 1:
 *   brute force.  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.
 *
 *     Jim Mahoney 10/19/98
 *****************************/

#include <stdio.h>

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

/* The board will be N x N */
#define N 8
/* Save up to this many solutions */
#define MaxSolns 200
/* 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 1


/*  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[N][N];

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

int solutions[N][N][MaxSolns];  /* saved board_prints */
int symmetries[MaxSolns];  /* record symmetry of each sol'n */
int IsThisAVariation[MaxSolns];  /* 0 if 1st of its kind; 1 if seen */

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

#define empty 0

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

/* Number of unique solutions found */
int unique_count = 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 one of of solutions */
int IsEqual(int sy, int so){
  int r,c;
  for (r=0;r<N;r++){
    for (c=0;c<N;c++){
      if ( sign(symm[r][c][sy]) != sign(solutions[r][c][so]) ) 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(int i){ /* which in solutions list */
  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]    =solutions[r][c][i];
      symm[r][N-c-1][1]  =solutions[r][c][i];
      symm[c][r][2]    =solutions[r][c][i];
      symm[c][N-r-1][3]  =solutions[r][c][i];
      symm[N-r-1][c][4]  =solutions[r][c][i];
      symm[N-r-1][N-c-1][5]=solutions[r][c][i];
      symm[N-c-1][r][6]  =solutions[r][c][i];
      symm[N-c-1][N-r-1][7]=solutions[r][c][i];
    }
  }
  for (p=0; p<8; p++){
    if (IsEqual(p,i)) n_symm++;

    for (q=i+1;q<=solution_count;q++){
      if (IsThisAVariation[q]==0)
	if (IsEqual(p,q)){
	  IsThisAVariation[q]=1;
	  break;
	}
    }
  }
  return(NumSymmetries/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");
  }
}

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


/* ------------------------------------------------------------ */
/* do the right thing with what we've found */
void found_solution(){
  int r,c;
  solution_count++;
  if (print_flag) {
    printf(" \n ----- sol'n %d -------- \n", solution_count);
    print_it();
    printf("\n");
  }

  if (solution_count<MaxSolns){
    /* save solution */
    for (r=0;r<N;r++){	/* loop over rows */
      for (c=0;c<N;c++){	/*  and columns  */
	solutions[r][c][solution_count]=board_print[r][c];
      }
    }
  }
}

/* ------------------------------------------------------------ */
/* 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() */


/* ----------------------------------------------*/
/*   loop over saved postions,
/*   finding what's unique */
void do_analysis(){
  int a; /* index for analysis */

  /* zero the "we've seen this one" array.*/
  for (a=0;a<MaxSolns;a++) IsThisAVariation[a]=0;

  for (a=1;a<=solution_count;a++) {
    if (IsThisAVariation[a]==0) {
      unique_count++;
      symmetries[a]=analysis(a);
      if (PrintAnalysis)
	printf(" \n Position %d has symmetry %d \n", a, symmetries[a]);
      if (PrintAnalysis) print_soln(a);
    }
  }

}

/* --------------------------------------------------------*/
/* --- main ------------ */
int main(){

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

  init_board();		/* set things up */

  do_a_column(0);	/* recursive call that finds solutions. */
  printf("\n Done.\n");
  printf("  Number of solutions found = %d \n\n",solution_count);  

  printf(" analysis...\n");
  do_analysis();	/* check symmetries */
  printf("\n Done.\n");
  printf("  Number of unique positions = %d .\n\n", unique_count);

}