/* 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 JN;
= search1 N (I+1) 1 (P++[(I,J)]) || fail if safe (I,J) P;
= search1 N I (J+1) P if J