(*nq*)
(* An imperative version of bt. This version prints all solutions *)

fun neq (x,y) = not(x=y);
infix neq

fun nq (r1:int,c1:int) (r2:int,c2:int) = (c1 neq c2) andalso
                                         (abs(r1-r2) neq abs(c1-c2));
 
fun check bp (rk,ck) [] = true
   |check bp (rk,ck) ((rp,cp)::p) = bp (rk,ck) (rp,cp) andalso 
                                    check bp (rk,ck) p;

fun print_pos (r:int,c:int) =
    (print "("; print r; print ","; print c; print ")");

fun print_nq [] = print "\n"
   |print_nq (p::x) = (print_pos p; print_nq x);
  
fun bt k n p =
    if k>n 
    then print_nq p
    else let val j = ref 1
         in while (!j <= n)
            do (if check nq (k,!j) p
                then bt (k+1) n ((k,!j)::p)
                else ();                      (* Deliver nothing *)
                j := !j + 1)
         end;