;;; queens.clj: Solves the N-Queens problem.
;;;
;;; Adapted from the code written by Mike Meyer.
;;; http://blog.mired.org/2011/03/easy-parallel-processing-in-clojure.html

(defn new-board
  "Create a new empty board of size n."
  [n]
  (vec (repeat n -1)))

(defn attack?
  "Returns true if it's possible from the first position [r1 c1] to atack
  the queen in the second position [r2 c2], otherwise returns false."
  [[r1 c1] [r2 c2]]
  (or
    (= r1 r2)
    (= c1 c2)
    (= (Math/abs (- r1 r2)) (Math/abs (- c1 c2)))))

(defn generate-next-boards
  "Returns a list with all the boards that can be produced starting from board
  and filling the corresponding col with every possible value."
  [board col]
  (for [i (range (count board))]
    (assoc board col i)))

(defn safe?
  "Returns true if all queens on board just before (but not including) col don't
  attack queen on col, otherwise returns false."
  [board col]
  (not (some #(attack? [(board col) col][(board %) %])
             (range col))))

(defn generate-next-safe-boards
  "Returns a list with all safe boards that can be produced starting from board
  and adding a new queen in col."
  [board col]
  (filter #(safe? % col) (generate-next-boards board col)))

(defn find-boards
  "Returns a list with all the solutions for the N-Queens problem starting with
  board already solved just before col. Stops when col is the last column in
  the board."
  [board col]
  (let [safe-boards (generate-next-safe-boards board col)]
    (if (= col (dec (count board)))
        safe-boards
        (mapcat #(find-boards % (inc col)) safe-boards))))

(defn queens
  "Returns a list with all the solutions for the N-Queens problem."
  [n]
  (find-boards (new-board n) 0))