/******************************************************************/
/*                                                                */
/* Program: queens.c                                              */
/*                                                                */
/* Description:                                                   */
/*                                                                */
/* This program finds all the possible ways that N queens can     */
/* be placed on an NxN chessboard so that the queens cannot       */
/* capture one another. The code makes no attemt to               */
/* eliminate symmetrical solutions, so the number of solutions    */
/* reported will always be higher than the actual number of       */
/* distinct solutions.                                            */
/*                                                                */
/*                                                                */
/* Algorithm and program by: Stefan Spaennare, Lund, Sweden       */
/*                                                                */
/* E-mail:                   stefan@spaennare.se                  */
/*                                                                */
/* Latest update:            2003-02-19                           */
/*                                                                */
/******************************************************************/

/********************************************************************************/
/*                                                                              */
/* Notice                                                                       */
/* ======                                                                       */
/*                                                                              */
/* I make no warranties that this program is (1) free of errors, (2) consistent */
/* with any standard merchantability, or (3) meeting the requirements of a      */
/* particular application. This software shall not, partly or as a whole,       */
/* participate in a process, whose outcome can result in injury to a person or  */
/* loss of property. It is solely designed for analytical work. Permission to   */
/* use, copy and distribute is hereby granted without fee, providing that the   */
/* header above including this notice appears in all copies.                    */
/*                                                                              */
/*                                                            Stefan Spaennare  */
/*                                                                              */
/********************************************************************************/


#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <time.h>

double timetic=(double)(CLOCKS_PER_SEC);

void printboard(ss,d,n)
char *ss;
int *d;
int n;
{
   int i,j,k,n2;

   n2=2*n;

   for (i=0; i<n2; i=i+2) {
      ss[i]='-';
      ss[i+1]=' ';
   } /* for i */

   ss[n2]='\0';

   for (j=1; j<=n; j++) {
      k=2*(d[j]-1);
      ss[k]='Q';
      printf("%s\n",ss);
      ss[k]='-';
   } /* for j */

} /* printboard */



int main(argc,argv) 
int argc;
char *argv[];

{

   int i,k,s,c,n;

   double ftime;

   int *d;

   char *ss;

   clock_t time1,timediff;

   if (argc != 2) {
      printf("Usage: %s ni\n",argv[0]);
      exit(0);
   } /* if */

   n=atoi(argv[1]);

   if (n < 4) {
      n=4;
   } /* if */


   d=(int *)calloc(n+1,sizeof(int));

   ss=(char *)calloc(2*n+3,sizeof(char));


   s=0;
   i=2;

   d[1]=1;
   d[2]=1;

   time1=clock();

   while (i > 0) {
      
      d[i]++;
      k=0;

      do {
         k++;
         c=d[i]-d[k];
      } while ((c != 0) && (abs(c) != abs(i-k)));

      if ((i == n) && (k == i)) {
         s++;
         printf("\n%6d\n\n",s);
         
         printboard(ss,d,n); 
      }
      else if (k == i) {
         i++;
      } /* if */

      while (d[i] == n) {
         d[i]=0;
         i--;
      } /* while */

   } /* while */


   timediff=clock()-time1;

   ftime=(double)(timediff)/timetic;

   printf("\n\n");

   printf("Total: %6d %10.2f\n\n",s,ftime);
      

} /* End */