/* queens3.q: multithreaded implementation of the N queens algorithm
   03-30-02 AG */

/* This is the same algorithm as in queens2.q, but it employs POSIX threads to
   compute the solutions in a background task which sends back results via a
   semaphore instead of printing them directly on the terminal. The semaphore
   queue is then processed by another task which prints the solutions as they
   become available.

   To use this program, simply start the two background tasks as follows:

   ==> def QUEENS = queens 8, PRINT = print

   Note the use of the def statement here which assigns the thread handles to
   corresponding variables. It is important that you keep these variables as
   long as you want the threads to survive. (The interpreter automatically
   cancels a thread as soon as the corresponding thread handle is garbage
   collected.) To stop the threads at any time simply undefine the variables
   using, e.g., the clear command. */

def RES = sem;	// semaphore used to transmit results

private search, safe, check;

queens N	= thread (search N 1 1 [] || post RES ());

search N I J P	= post RES P if I>N;
		= search N (I+1) 1 (P++[(I,J)]) || fail if safe (I,J) P;
		= search N I (J+1) P if J<N;
		= () otherwise;

safe (I1,J1) P	= not any (check (I1,J1)) P;

check (I1,J1) (I2,J2)
		= (I1=I2) or else (J1=J2) or else
		  (I1+J1=I2+J2) or else (I1-J1=I2-J2);

private loop, print1;

print		= thread (loop print1 RES);

print1 ()	= return (); // no more results
print1 P	= write P || writes "\n" otherwise;

/* iterate a function over a semaphore */

loop F SEM	= F (get SEM) || loop F SEM;