/* N-QUEENS problem, Fork95 (V1.7) implementation 9710 C. Kessler */

#include <fork.h>
#include <syscall.h>
#include <assert.h>
#include <io.h>
#include <math.h>
#include <PQueue.h>
#include <TaskQueue.h>

/** the definition of the datatype Task
 *  must be provided by the programmer.
 */
typedef struct task {
  int *col;   // column indices of already positioned queens in rows 0..row-1
  int row;    // row to be examined next
  int pos;    // column position in row row to be examined next
} *Task;

Task new_Task( int *c, int r, int p )    // constructor
{
  Task t = (Task)shmalloc(sizeof(struct task));
  t->col = c;  t->row = r;  t->pos = p;
  return t;
}
  
#define free_Task(t) shfree(t)            // destructor

#define TASK_QUEUE_LENGTH_THRESHOLD (3*__STARTED_PROCS__)

sh simple_lock screen = 0;  /*lock for screen output*/
sh int solutions = 0;   /*counter for number of solutions*/
#define THRESHOLD (2+ilog2(1+ilog2(__STARTED_PROCS__)))  // small problems
#define PRINT_SOLUTIONS 1  // print solutions or not
sh int N;            /* the number of queens */


#if PRINT_SOLUTIONS
/* output an array q of n column indices of the queens ordered by row;
 * with an extra column index k for row n, and count the solutions:
 */
void printQueens( int *q, int n, int k )
{
 int j;
 simple_lockup( &screen );
 syncadd( &solutions, 1 );
 printf("Solution %d:  ", solutions);
 for (j=0; j<n; j++) printf("%d ", q[j]);
 printf("%d\n",k);
 simple_unlock( &screen );
}

/* alternatively: produce simple graphical output by
 * plotting up to eight checkerboards in a line.
 * The join() statement is used to arrange the solutions
 * on-line as they are computed. Same parameters as above.
 */
sh char *str=".....................................................................................\n";

sync void print_p_solutions( int *q, int n, int k )
{
 sh int p = 0;
 sh int i;
 int pos;
 /* farm assert(n==N-1); */
 $ = mpadd(&p,1);
 solutions += p;
 seq printf("-------------------- Next %d solutions (%d..%d): --------------------\n",
            p, solutions-p+1, solutions);
 str[(N+1)*$] = '|';    /*init: draw board boundary symbols*/
 for (i=0; i<N-1; i++) {  /* shared loop: print N lines of str */
   pos = 1+$*(N+1)+q[i];
   str[pos] = 'Q';   /*draw queen on board $ in column q[i]*/
   farm write(1,str+$*(N+1),(N+1)); /*draw line i of all boards*/
   seq write(1,"\n",1);
   str[pos] = '.';   /*reset symbol on board $ in column q[i]*/
 }
 pos = 1+$*(N+1)+k;
 str[pos] = 'Q';   /*draw queen on board $ in column k*/
 farm write(1,str+$*(N+1),(N+1));
 seq write(1,"\n",1); 
 str[pos] = '.';   /*reset symbol on board $ in column k*/
}

void print_up_to_eight_solutions( int *q, int n, int k )
{
 int j;
 int waittime = 0; /* last set of solutions must be printed also if p<8*/
#define maxtime 300    /*empirically determined value for waiting time*/
 join( 400;                                       /* stack size for body */
       (__NUM_PR__>=4 || (waittime++ > maxtime)); /* start-condition */
       __RANK__ < 8 )                             /* stayinside-cond */
      print_p_solutions(q,n,k);            /*body = bus tour*/
 else continue;
}
#endif


/* assume queens in row 0...n-1 have been set, 
 * with their column indices being stored in q[0:n-1].
 * Now test whether queen n may be set on column j in [0:N-1],
 * and do on myself the recursive tests for rows n+1...N-1:
 */
void testQueenMyself( int *q, int n, int j )
{
 int *qq = NULL;
 int i, l, k;
#if DEBUG
 if (q) pprintf("Myself ([%d,%d,%d,%d],%d,%d)\n",
                q[0], (n>1)?q[1]:-1, (n>2)?q[2]:-1, (n>3)?q[3]:-1, n, j );
#endif
 /* it has already been tested whether column index j occurs in q[] */
 for (i=0; i<n; i++) {
   /* two queens are on the same diagonal 
    * iff either row2-row1 == col1-col2 or row2-row1==col2-col1: */
   if (j-q[i] == n-i)  return;   /* -> fail*/
   if (q[i]-j == n-i)  return;   /* -> fail*/
 }
 if (n<N-1) { /* not yet arrived at last row: */
    for (i=0; i<N; i++) { /* try all column indices i */
      int cq, thr;
      for (cq=0,thr=0; cq<n; cq++)    // loop over q[]
        if (q[cq]==i) {thr=1;break;}  // column i threatened by queen cq
      if (!thr && (i!=j)) {  // column i not threatened by a queen
         if (!qq) {
            qq = (int *)shmalloc( n+1 );
            for (l=0; l<n; l++)  qq[l] = q[l];
         }
         qq[n]=j;
         testQueenMyself( qq, n+1, i );
      }
    }
    if (qq) shfree( qq );
 }
 else  /* arrived at last row: print the solution */
#if PRINT_SOLUTIONS
    //printQueens( q, N-1, j );
    print_up_to_eight_solutions( q, N-1, j );
#else
    syncadd( &solutions, 1 );
#endif
}


/* assume queens in row 0...n-1 have been set, 
 * with their column indices being stored in q[0:n-1].
 * Now test whether queen n may be set on column j in [0:N-1],
 * and spawn recursive tests for rows n+1...N-1:
 */
void testQueen( TaskQueue taskpool, void *task )
{
 Task t = (Task)task;
 int *q = t->col;
 int n = t->row;
 int j = t->pos;
 int *qq;
 int i, l, k;

 free_Task( t );
 if (n >= THRESHOLD) {  // task too small to be further split up
    testQueenMyself( q, n, j );
    return;
 }
 /* it has already been tested whether column index j occurs in q[] */
 for (i=0; i<n; i++) {
   /* two queens are on the same diagonal 
    * iff either row2-row1 == col1-col2 or row2-row1==col2-col1: */
   if (j-q[i] == n-i)  return;   /* -> fail*/
   if (q[i]-j == n-i)  return;   /* -> fail*/
 }
 if (n<N-1) { /* not yet arrived at last row: */
    for (i=0; i<N; i++) { /* try all column indices i */
      int cq, thr;
      for (cq=0,thr=0; cq<n; cq++) /* loop over q[] */
        if (q[cq]==i) {thr=1;break;}  /* column i threatened by queen cq */
      if (!thr && (i!=j)) {   /*column i not threatened by a queen */
         // found feasible candidate in column i: spawn task
         Task nt;
         if (taskpool->size(taskpool) < TASK_QUEUE_LENGTH_THRESHOLD) {
            qq = (int *)shmalloc( n+1 );
            for (l=0; l<n; l++)  qq[l] = q[l]; /* make copy of q */
            qq[n]=j;
            nt = new_Task( qq, n+1, i );
            spawn( taskpool, nt );
         }
         else {
            qq = (int *)shmalloc(n+1);
            for (l=0; l<n; l++)  qq[l] = q[l];
            qq[n]=j;
            testQueenMyself( qq, n+1, i);
            shfree(qq);
         }
      }
    }
    if (q) shfree( q );
    // return and take new task if there is one
 }
 else  /* arrived at last row: print the solution */
#if PRINT_SOLUTIONS
    //printQueens( q, N-1, j );
    print_up_to_eight_solutions( q, N-1, j );
#else
    syncadd( &solutions, 1 );
#endif
}


sync void presetQueensTaskQueue( sh TaskQueue taskqueue, sh void *n ) 
{
 farm {
   int i;
   // generate n root tasks: the possibilities for the queen in row 1
   forall(i, 0, (int)n, __STARTED_PROCS__) {
     Task ti = new_Task( NULL, 0, i );
     spawn( taskqueue, ti );
   }
 }
}



sh unsigned int starttime, stoptime;

void main( void )
{
 if (__PROC_NR__==0) {
    printf("Enter N = ");
    scanf("%d", &N );
    if (N < 4) {
      printf("Error: N=%d has no solution\n", N);
      exit(0);
    }
    printf("\nComputing solutions to the %d-Queens problem...\n\n", N);
 }
 start {
   initTracing( 100000 );
   starttime = getct();
   startTracing();
   taskQueue( presetQueensTaskQueue, testQueen, (void *) N );
   stopTracing();
   stoptime = getct();
   seq {
      printf("\nSolutions: %d\nTIME: %d cc\n", 
             solutions,  stoptime - starttime );  
      printf("[Press RETURN to continue]"); scanf("%c", &N );
   }
   writeTraceFile("aqueens.trv", "asynchronous N-Queens program");
 }
 exit(0);
}