/* 
 * A small program to solve the n-queens problem.
 * It was a programming exercise to do some c-programming gain 
 * -- so I did no try to optimize except for obvious things.
 * 
 * However, you can get some stats on the distribution of queens for the
 * board sizes. 
 * As it is well-known, run-time increases quickly; you can use it for board
 * sizes up to 15, 16, or 17 in a reasonable amount of time.
 *
 * Example usage: "queens 8 verbose".
 * 
 * Enjoy. Martin Borriss, April 2007.
 */ 

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

#define EMPTY 0
#define QUEEN 1
#define CONTROLLED 2

#define DEFAULT_SIZE 8
#define NQ_MIN 1
#define NQ_MAX 20

typedef struct board_struct_tag  { 
  int *sq;
} board_t; 

board_t *boards, stats_board;

int nq = DEFAULT_SIZE;
int solution_cnt = 0;
int add_queen_cnt = 0;

time_t start_time, now;

/* prototypes */

void print_stats(void);
int init(void);
int reset_boards(void);
int add_queen(int rank);
int mark_solution(void);
void print_stats(void);
void usage(char *);

int 
main(int argc, char** argv)
{
  int verbose = 0;

  if(argc < 2) usage(argv[0]);
  else {
    if ((argc >= 3) && (strncmp(argv[2], "verbose", 7) == 0))
      verbose = 1;
    nq = atoi(argv[1]);

    if ((nq < NQ_MIN) || (nq > NQ_MAX)) 
      nq = 8;
  }
  
  printf("%d queens problem. Hold on...\n", nq);
  
  init();
  
  reset_boards();
  add_queen(0);

  printf("\n\n Done: (%d solutions, %d recursive calls.\n", 
	 solution_cnt, add_queen_cnt);
  if (verbose) print_stats();
  return 0;
}

/* set up boards */
int init()
{
  int i;

  boards = malloc(sizeof(board_t) * nq);
  for (i = 0; i < nq; i++) 
    boards[i].sq = malloc(sizeof (int) * nq * nq);
  stats_board.sq = malloc(sizeof (int) * nq * nq);

  start_time = time((time_t *) NULL);
  

  return 0;
}

void 
usage(char * s)
{
  printf("Usage: %s [Queens] [verbose]\n", s);
  printf("\nFor example, '%s 8 verbose' will solve the famous 8-queens problem\n and print stats.\n", s);
}

int 
reset_boards()
{
  int i = 0;

  while(i < nq) {
    memset(( void * ) boards[i].sq, 0, sizeof(int)*nq*nq);
    i++;
  }
  memset(( void * ) stats_board.sq , 0, sizeof(int)*nq*nq);

  return 0;
}

#if 0
/* unused, just for debugging or to print out solutions */
int 
print_board(board_t *b)
{
  int i,j;
  char er[5] = "+---";

  for(i = 0; i < nq; i++) printf("%s", er);
  printf("|\n");
  for (j = nq - 1; j >= 0; j--) {
    for (i = 0; i < nq; i++) {
      if (b->sq[j*nq + i] == EMPTY) 
	printf("|   ");
      else if (b->sq[j*nq + i] == QUEEN)
	printf("| Q ");	
      else 
	printf("| ! ");
    }
    printf("|\n");
    for(i = 0; i < nq; i++) printf("%s", er);
    printf("|\n");
  }
  return 0;
}
#endif

/* uses the following "strategy":
   First, a queen is added to the first rank.
   The next queen is added to the second rank, but not to an invalid square.
   Squares are marked (upwards only) as invalid, when a queen is added. If we
   reach the final depth, we have found a solution.
*/

int 
add_queen(int rank)
{
  int i,j;
  board_t *b; 
  
  add_queen_cnt++;

  for (i = nq*rank; i < nq*(rank + 1); i++) {
    if(boards[rank].sq[i] != EMPTY) continue;
    
    if(rank == (nq - 1)) { 
      boards[rank].sq[i] = QUEEN;
      mark_solution();
      boards[rank].sq[i] = EMPTY;
    }
    else {
      /* copy board to next level and mark controlled squares */
      memcpy(boards[rank + 1].sq, boards[rank].sq, 
	     sizeof(int) * nq * nq);

      b = &boards[rank + 1];
      b->sq[i] = QUEEN;
      
      /* mark it here */
      for(j = i + nq; j < nq*nq; j+= nq) b->sq[j] = CONTROLLED; 
      for(j = i + nq-1; j < nq*nq; j+= (nq-1)) { 
	if(j % nq == (nq - 1)) break;
	b->sq[j] = CONTROLLED; 
      }
      for(j = i + nq + 1; j < nq*nq; j+= (nq + 1)) { 
	if(j % nq == 0) break;
	b->sq[j] = CONTROLLED; 
      }

      /* recursive call */
      add_queen(rank +1);

      /* progress indicator */
      if(rank == 0) {
	double d;

	now = time((time_t *) NULL);
	d = difftime(now, start_time);

	printf("\r%3d %% done (%.0f seconds) (queen %c%d, solutions: %d)", 
	       ((i+1) * 100) / ((nq+1)/2), d, 
	       i % nq + 'a', (i / nq) +1, solution_cnt); 
	fflush(stdout);

	/* skip right-hand side of board -- due to symmetry we already 
	   got it */
	if(i >= (nq-1)/2) break;
      }
    }
  }

  return 0;
}

int 
mark_solution(void)
{
  int i;
  int symmetric = 0;

  solution_cnt++;

  /* skip extra count only if nq uneven and queen sits in the bottom middle row */
  if (!((nq & 1)  && (boards[nq-1].sq[nq/2] == QUEEN))) {
    solution_cnt++;
    symmetric = 1;
  }

  /* update solutions stats */
  for(i = 0; i < nq*nq; i++)
    if(boards[nq-1].sq[i] == QUEEN) { 
      stats_board.sq[i]++;
      if(symmetric) {
	int k = ((nq-1) - (i%nq)) + ((i/nq) * nq);
	stats_board.sq[k]++;
      }
    }

  return 1;
}

void 
print_stats(void)
{
  int i,j;
  char er[5] = "+---";
  board_t *b = &stats_board;


  printf("I have needed %d calls to add_queen.\n", add_queen_cnt);
  printf("Frequency distribution of the %d solutions:\n", solution_cnt);

  for(i = 0; i < nq; i++) printf("%s", er);
  printf("|\n");
  for (j = nq-1; j >= 0; j--) {
    for (i = 0; i < nq; i++) {
      printf("|%3d",b->sq[j*nq + i]);
    }
    printf("|\n");
    for(i = 0; i < nq; i++) printf("%s", er);
    printf("|\n");
  }
}