/* queens2.q: a backtracking variation of the N queens algorithm which uses
   exception handling 07-23-01 AG */

/* The basic backtracking technique is the same as in queens.q, but the
   implementation here first pursues a single solution path and then uses the
   fail construct to force backtracking. This is a little bit faster and also
   needs less memory than the stream-based implementation in queens.q. */

/* queens N prints all valid placements of N queens on an NxN board. Note the
   use of `fail' in the recursive branch of the algorithm (where a new
   placement is added to the current list), which forces backtracking. The
   rest of the algorithm is tail-recursive. */

queens N	= search N 1 1 [];

search N I J P	= printf "%s\n" $ str P || flush 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;

/* queens1 N just computes the first solution. This is the same algorithm as
   above, but it employs a catch/throw construct to exit from the algorithm
   and return the result as soon as we have found a solution. Note that the
   "exception handler" in this case is simply the identity function. */

queens1 N	= catch id (search1 N 1 1 []);

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

/* Verify that a queen placement is safe w.r.t. a given list of other
   placements. This is the same as in queens.q. */

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);