Eight queens puzzle in clojure.

gistfile1.clj

;; usage: (print-solutions (eight-queens))

(ns eight-queens
  (:use clojure.test)
  (:use clojure.contrib.str-utils))

(def N 8)

(defn distance [x y] (Math/abs (- x y)))

(defn solution? [state]
  (= N (count state)))

(defn next-states [s]
  "compute the successor states of s"
  (map #(conj s %) (range N)))

(defn attack? [s i j]
  "whether the i-th and j-th queen in state s are attacking each other"
  (let [xi (s i)
        xj (s j)]
    (or (= xi xj)
        (= (distance xi xj) (distance i j)))))

(defn valid-state? [s]
  "s is valid if the last queen in s is not able to attack the others"
  (let [max-idx (dec (count s))
        pairs (map #(list % max-idx) (range max-idx))
        no-attack? (fn [pair]
                     (not (attack? s (first pair) (last pair))))]
    (every? no-attack? pairs)))

(defn next-valid-states [s]
  "seq of the valid successor states of s"
  (filter valid-state? (next-states s)))

(defn backtrack [state]
  "backtracking"
  (if (solution? state)
    [state]
    (let [next-states (next-valid-states state)]
      (mapcat backtrack next-states))))


(defn eight-queens [] (backtrack []))

;; printing helper functions

(defn format-solution [solution]
  (let [letters (vec (seq "ABCDEFGH"))
        positions (map #(str-join "" [%1 (+ 1 %2)]) letters solution)]
    (str-join ", " positions)))

(defn print-solutions [solutions]
  (doseq [solution solutions]
    (println (format-solution solution))))

(defn print-all-solution []
  (print-solutions (eight-queens)))

;; tests

(deftest test-next-states
  (is (= (next-states []) [[0] [1] [2] [3] [4] [5] [6] [7]])))

(deftest test-attack?
  (are [x y] (= x (attack? y 0 2))
       true  [0 1 0]
       false [0 1 1]
       true  [0 1 2]))

(deftest test-valid-state?
  (are [x y] (= x (valid-state? y))
       false [0 0]
       false [0 1]
       false [0 2 1]
       true [1 3 5 7 2 0 6 4] ; one of the solutios
       ))

(deftest test-next-valid-states
  (is (= (next-valid-states [1 3 5 7 2])
         '([1 3 5 7 2 0]
             [1 3 5 7 2 4]))))

(deftest test-eight-queens
  (is (= 92 (count (eight-queens)))))