Enumerate all N-Queens solutions

nqueens-cl.clj

(ns nqueens-cl
  (:refer-clojure :exclude [==])
  (:use [clojure.core.logic]))

(defmacro def-subo
  "Generate subtraction algebra"
  [name n]
  (let [xn 'x, yn 'y, rn 'r
        gen-association (fn [x y] 
                          `[(== ~xn ~x) (== ~yn ~y) (== ~rn ~(- x y))])
        gen-row (fn [x]
                  (->> (range n)
                       (map #(gen-association x %))
                       concat))
        gen-all (fn []
                  (->> (range n)
                       (map #(gen-row %))
                       (apply concat)))]
    `(defn ~name [~xn ~yn ~rn]
       (conde
         ~@(gen-all)))))

(declare subo)

(defn safeo
  "Are 2 queens threatening each ohter?"
  [[x1 y1] [x2 y2]]
  (fresh [d1 d2 d3 d4]
         (subo x2 x1 d1)
         (subo y2 y1 d2)
         (subo x1 y2 d3)
         (subo x2 y1 d4)         
         (!= x1 x2)
         (!= y1 y2)
         (!= d1 d2)
         (!= d3 d4)))

(defmacro queens-run
  "Search for all N queens solutions"
  [n]
  (let [xnames (->> (range n) (map (fn [_] (gensym "x"))) (into []))
        gen-safes (fn []
                    (->> (range (dec n))
                         (map (fn [x] [x (range (inc x) n)]))
                         (map (fn [[s ts]]
                                (map (fn [t] `(safeo [~(nth xnames s) ~s]
                                                    [~(nth xnames t) ~t])) ts)))
                         (apply concat)))
          ]
    `(run* [r#]
           (fresh [~@(map #(nth xnames %) (range n))]
                  ~@(gen-safes)
                  (== r# [~@(map (fn [x] [(nth xnames x) x])
                                 (range n))])))))

(def-subo subo 7)
(time (count (queens-run 7)))

nqueens-cl2.clj

(ns nqueens-cl
  (:refer-clojure :exclude [==])
  (:use [clojure.core.logic]))

(defne safeo [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 [l n]
  ([() _])
  ([[[x y] . t] _]
     (nqueenso t n)
     (membero x (range n))
     (safeo [x y] t)))

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

nqueens.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))

(for [i (range 1 10)]
   (count (search i)))
;; (1 0 0 2 10 4 40 92 352)