even more queens

nqueens-cl.clj

(defne safeo
  "Is the queen q safe from all queens in list"
  [q others]
  ([_ ()])
  ([[x1 y1] [[x2 y2] . t]]
     (!= x1 x2)
     (!= y1 y2)
     (project [x1 x2 y1 y2]
       (!= (- x2 x1) (- y2 y1))
       (!= (- x1 y2) (- x2 y1)))
     (safeo [x1 y1] t)))

(defne nqueenso
  "Are no queens in list attacking any other?"
  [l n]
  ([() _])
  ([[[x y] . t] _]
     (nqueenso t n)
     (membero x (range n))
     (safeo [x y] t)))

(defn solve-nqueens [n]
  (run-nc* [q]
    (== q (map vector (repeatedly lvar) (range n)))
    (nqueenso q n)))


(time (count (solve-nqueens 8)))
;; "Elapsed time: 1067.984 msecs"

queens-swi.pro

:- use_module(library(clpfd)).
:- use_module(library(statistics)).

n_queens(N, Qs) :-
        length(Qs, N),
        Qs ins 1..N,
        safe_queens(Qs).

safe_queens([]).
safe_queens([Q|Qs]) :- safe_queens(Qs, Q, 1), safe_queens(Qs).

safe_queens([], _, _).
safe_queens([Q|Qs], Q0, D0) :-
        Q0 #\= Q,
        abs(Q0 - Q) #\= D0,
        D1 #= D0 + 1,
        safe_queens(Qs, Q0, D1).


% time (n_queens(8, Qs)).
% 6,970 inferences, 0.002 CPU in 0.002 seconds (99% CPU, 3443676 Lips)

queens-swi2.pro

queens([]).
 
queens([ Row/Col | Rest]) :-	
    queens(Rest),
    member(Col, [1,2,3,4,5,6,7,8]),
    safe( Row/Col, Rest).
 
safe(Anything, []).
 
safe(Row/Col, [Row1/Col1 | Rest]) :-
    Col =\= Col1, 
    Col1 - Col =\= Row1 - Row, 
    Col1 - Col =\= Row - Row1,
    safe(Row/Col, Rest).
 
member(X, [X | Tail]).     
 member(X, [Head | Tail]) :-
    member(X, Tail).
 
queens([1/C1, 2/C2, 3/C3, 4/C4, 5/C5, 6/C6, 7/C7, 8/C8]).

queens.clj

(defn safe? [[x1 y1] [x2 y2]]
  (and
   (not= x1 x2)
   (not= y1 y2)
   (not= (- x2 x1) (- y2 y1))
   (not= (- x1 y2) (- x2 y1))))

(defn get-possible [n y qs]
  (for [x (range n)
        :let [p [x y]]
        :when (every? #(safe? p %) qs)]
    p))

(defn search [n]
  (let [res (atom [])]
    ((fn sloop [y qs]       
       (if (= y n) (swap! res conj qs)
           (doseq [p (get-possible n y qs)]
             (sloop (inc y) (conj qs p)))))
     0 [])
    @res))


(time (count (search 8)))
;; "Elapsed time: 28.798 msecs"

queens.shen

(define n-queens
  {number --> (list (list number))}
  N -> (n-queens-loop N (initialise N)))

(define initialise
   {number --> (list number)}
   0 -> []
   N -> [1 | (initialise (- N 1))])
 
(define n-queens-loop
  {number --> (list number) --> (list (list number))}
  N Config -> []    where (all_Ns? N Config)
  N Config -> [Config | (n-queens-loop N (next_n N Config))] 
                                       where (and (ok_row? Config) (ok_diag? Config))
  N Config -> (n-queens-loop N (next_n N Config)))
 
(define all_Ns?
  {number --> (list number) --> boolean}
   _ [] -> true
  N [N | Ns] -> (all_Ns? N Ns)
  _ _ -> false)
 
(define next_n
  {number --> (list number) --> (list number)}
  N [N | Ns] -> [1 | (next_n N Ns)]
  _ [N | Ns] -> [(+ 1 N) | Ns])
 
(define ok_row?
  {(list number) --> boolean}
  [] -> true
  [N | Ns] -> false     where (element? N Ns)
  [_ | Ns] -> (ok_row? Ns))
 
(define ok_diag?
  {(list number) --> boolean} 
  [] -> true
  [N | Ns] -> (and (ok_diag_N? (+ N 1) (- N 1) Ns) 
                                (ok_diag? Ns)))
 
(define ok_diag_N?
  {number --> number --> (list number) --> boolean}
  _ _ [] -> true
  Up Down [Up | _] -> false
  Up Down [Down | _] -> false
  Up Down [_ | Ns] -> (on-queens


(time (n-queens 8))
;; run time: 2.921000063419342 secs  (SBCL)
;; run time: 71.48700000000002 secs  (Shen-CLJ)