
/* queens.q: determine valid placements of N queens on an NxN board
   05-08-1993 AG */

/* Say `hd (queens 8)' to obtain the first solution. (On slower computers this
   may take a while.) To print all solutions, evaluate `print (queens 8)'
   (abort with Ctl-C when you get bored). Placements are given as lists of
   (column,row) pairs.  The algorithm enumerates the solutions in
   lexicographic order (first all solutions which place the first queen into
   row 1, then the solutions which place it into row 2, etc.). To determine
   placements on any NxN board, use N as the parameter to queens. */

/* queens N returns the stream of all valid placements of N queens on an
   NxN board: */

queens N	= cols N N;

/* cols N I generates the stream of all valid placements of I queens in
   columns 1..I of an NxN board: */

cols N I	= {[]} if I<1;
		= {P++[(I,J)] : P in cols N (I-1), J in [1..N], safe (I,J) P}
		    otherwise;

/* safe determines whether a queen at position (I1,J1) is safe w.r.t. a given
   placement: */

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

/* check determines whether queens at positions (I1,J1) and (I2,J2) hold
   each other in check: */

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

/* helper function to print a stream */

print		= do (\X.printf "%s\n" $ str X || flush);
