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

enum { FALSE, TRUE };

int valid( int *board, int size );
int *gridSearch(int n);

int nTrials = 0;

/**
 * Main program allows for either command-line arguments or user dialog
 * to determine the number of queens and the number of parallel threads
 * to work on the problem.
 */
int main ( int argc, char* argv[] )
{
   int   *solution;
   int    nQueens;
   double elapsed;
   FILE  *fp = fopen ("Grid.csv", "a");

   printf ("Number of queens:   ");
   if ( argc < 2 )
   {
      scanf ("%d", &nQueens);
      while ( getchar() != '\n' )
         ;
   }
   else
   {  nQueens = atoi(argv[1]);
      printf("%d\n", nQueens);
   }
   srand(time(NULL));

   // Timed computation of ONE solution:

   elapsed = clock();
   solution = gridSearch(nQueens);
   elapsed = (clock() - elapsed) / CLOCKS_PER_SEC;

   if ( valid(solution, nQueens) )
      printf("Valid solution found in %3.3f sec.\n", elapsed);
   else
      printf("ERROR --- invalid solution took %3.3f sec.\n", elapsed);
   printf ("%d pass(es) required.\n", nTrials);
   
   if ( fp != NULL )
   {
      fprintf (fp, "%d,%3.3f,%d\n", nQueens, elapsed, nTrials);
      fclose(fp);
   }
}

int nextInt(int n)
{
   double rtn;

   rtn = n * ( rand() / (1.0 + RAND_MAX) );
//printf ("%d in, computed %3.3f going to %d\n", n, rtn, (int) rtn); exit(0);
   if (rtn >= n )
      return n-1;
   else
      return (int) rtn;
}


int *gridSearch(int n)
{
   int   *solution = (int*) calloc (n, sizeof *solution);
   int    fail = TRUE;
   short *blocked = NULL;

   while ( fail )
   {
      int row, col, k, d;

      if ( blocked )
         free(blocked);
      blocked = (short*) calloc (n*n, sizeof *blocked);   // Initially all false
      nTrials++;

      for ( row = 0; row < n; row++ )
      {
         col = nextInt(n);
//printf ("%-4d", col);
         for ( k = 0; blocked[row*n+col] && k < n ; k++ )
            col = (col+1) % n;
         if ( blocked[row*n+col] )
            break;
         solution[row] = col;
         for ( k = row+1; k < n; k++ )
         {
            blocked[k*n+col] = TRUE;
            // row - col
            d = k - (row - col);
            if ( d >= 0 && d < n )
               blocked[k*n+d] = TRUE;
            // row + col
            d = (row + col) - k;
            if ( d >= 0 && d < n )
               blocked[k*n+d] = TRUE;
         } // end for k
      } // end for row
      fail = row < n;
//if ( fail ) printf ("%d trial fails in row %d.\n", nTrials, row);
   } // end while fail
   return solution;
}

// Verify (or reject) the validity of the board of indicated size.
int valid( int *board, int size )
{
   int row;
   // Take advantage of initialization to false
   int *diagChk = (int*) calloc (2*size-1, sizeof *diagChk),
       *antiChk = (int*) calloc (2*size-1, sizeof *antiChk);

//    mark (0, board[0], TRUE);
   diagChk[0-board[0]+size-1] = TRUE;
   antiChk[0+board[0]] = TRUE;

   for ( row = 1; row < size; row++ )
      if ( (diagChk[row-board[row]+size-1]||antiChk[row+board[row]]) )
         return FALSE;
      else
//          mark (row, board[row], TRUE);
         diagChk[row-board[row]+size-1] =
            antiChk[row+board[row]] = TRUE;
   return TRUE;
}