n-queens-problem.clj

(ns clojure-tests.eight-queens)

(def empty-board '())

(defn safe? [column positions]
  (prn "positions: " positions)
  (let [latest-row (first (first positions))]
    (prn "latest-row: " latest-row)
    (loop [pos (rest positions)]
      (prn "pos: " pos)
      (if (empty? pos)
        true
        (and (let [actual-row (first (first pos))
                   actual-col (first (rest (first pos)))
                   dif (- column actual-col)]
               (prn "actual-row: " actual-row ", actual-column: " actual-col)
               (and (not= latest-row actual-row)
                    (not= (- latest-row dif) actual-row)
                    (not= (+ latest-row dif) actual-row)))
             (recur (rest pos)))))))

(defn adjoin-position [row column rest-of-queens]
  ;; (prn "row: " row ", column: " column ", rest-of-queens: " rest-of-queens)
  (cons (cons row (list column)) rest-of-queens))

(defn queens [board-size]
  (defn queen-cols [k]
    (if (= k 0)
      (list empty-board)
      (filter
        (fn [positions] (safe? k positions))
        (mapcat
          (fn [rest-of-queens]
            (map (fn [new-row]
                   (adjoin-position new-row k rest-of-queens))
                 (range 1 (inc board-size))))
          (queen-cols (- k 1))))))
  (queen-cols board-size))

(comment
  (queens 0)
  (queens 1)
  (queens 2)
  (queens 4) ;; '(((3 . 4) (1 . 3) (4 . 2) (2 . 1)) ((2 . 4) (4 . 3) (1 . 2) (3 . 1)))
  )