/* N-QUEENS problem, Fork95 (V1.7) implementation 9710 C. Kessler */ #include #include #include #include #include #include #include /** 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=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 fail*/ if (q[i]-j == n-i) return; /* -> fail*/ } if (ncol; 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 fail*/ if (q[i]-j == n-i) return; /* -> fail*/ } if (nsize(taskpool) < TASK_QUEUE_LENGTH_THRESHOLD) { qq = (int *)shmalloc( n+1 ); for (l=0; l