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

Many hyperlinks are disabled.
Use anonymous login to enable hyperlinks.

Overview
Comment:Add initial version of parallel n queens solvers.
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA1:203a92b61b7fcd6f3ee94c06cfc47a3056337262
User & Date: mwm@mired.org 2011-03-08 23:21:50
Context
2011-04-04
18:55
Update to the latest code, using a database for config, and a reload option. check-in: cbf17190cb user: mwm@mired.org tags: trunk
2011-03-08
23:21
Add initial version of parallel n queens solvers. check-in: 203a92b61b user: mwm@mired.org tags: trunk
2011-02-24
08:17
Add code from my .zshrc so readers can recreate the example. check-in: 72974d03d3 user: mwm@mired.org tags: trunk
Changes
Hide Diffs Unified Diffs Ignore Whitespace Patch

Added clojure/queens.clj.







































































































































































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