/* 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. (This takes 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. */

include print;

private cols, safe, check;
var P, J;

/* 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	= stream [[]] if I<1;
		= streamof (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);