Mired in code
Check-in [203a92b61b]
Not logged in
Public Repositories
mwm's Repositories

 ``` ``` ``` ``` ```> > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > ``` ```1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 ``` ```(use ['clojure.string :only ['join]]) (defn printboard [board] (println (join "\n" (map #(join (assoc (vec (repeat (count board) ".")) % "Q")) board)))) (defn attacks "Check if queen on row q attacks queen on row r on board." [board q r] (let [qc (nth board q) rc (nth board r)] (or (== q r) (== qc rc) (== qc (+ rc (- r q))) (== qc (- rc (- r q)))))) (defn checkboard "Check that all queens on board up to row don't attack queen on row." [board row] (not (some #(attacks board row %) (range row)))) (defn queens [n] "Find all solutions to the N-queens problem." (letfn [(bump [board row] (assoc board row (inc (nth board row))))] (loop [board (assoc (vec (repeat n -1)) 0 0) row 0 result []] (cond (== (nth board row) n) (if (== row 0) result (recur (bump (assoc board row -1) (dec row)) (dec row) result)) (not (checkboard board row)) (recur (bump board row) row result) (== row (dec n)) (recur (bump board row) row (conj result board)) :else (recur (bump board (inc row)) (inc row) result))))) (defn find-boards "Find all solutions for the N-queens problem starting with board up to row." [board row] (let [cols (count board) nr (inc row) nbs (filter #(checkboard % row) (map #(assoc board row %) (range cols)))] (if (== nr cols) nbs (mapcat #(find-boards % nr) nbs)))) (defn recursive-queens "Recursively find solutions for the N-queens problem." [n] (find-boards (vec (repeat n -1)) 0)) (defn find-boards-threading "Start threads to find solutions for the N-queens problem from our starting point." [board row] (let [cols (count board) nr (inc row) nbs (filter #(checkboard % row) (map #(assoc board row %) (range cols)))] (if (== nr cols) nbs (apply concat (pmap #(find-boards-threading % nr) nbs))))) (defn threaded-queens "Find solutions to the N-queens problem in parallel." [n] (find-boards-threading (vec (repeat n -1)) 0)) (defn find-boards-threading-1 "Start threads to find solutions for the N-queens problem from our starting point." [board row] (let [cols (count board) nr (inc row) nbs (filter #(checkboard % row) (map #(assoc board row %) (range cols)))] (if (== nr cols) nbs (apply concat (pmap #(find-boards % nr) nbs))))) (defn threaded-queens-1 "Find solutions to the N-queens problem in parallel." [n] (find-boards-threading-1 (vec (repeat n -1)) 0)) (defn find-boards-threading-n "Start threads to find solutions for the N-queens problem from our starting point." [board row] (let [cols (count board) nr (inc row) nbs (filter #(checkboard % row) (map #(assoc board row %) (range cols))) finder (if (< (count nbs) 8) find-boards find-boards-threading-n)] (if (== nr cols) nbs (apply concat (pmap #(finder % nr) nbs))))) (defn threaded-queens-n "Find solutions to the N-queens problem in parallel." [n] (find-boards-threading-n (vec (repeat n -1)) 0)) ```