Clojureで8Queen問題

8Queen問題とは, 有名ですが, 以下のような問題です.

エイト・クイーン(Wikipeida.ja)

 チェスのクイーンの動きは, 飛車 + 角行で, 縦横の重複(飛車の動きの判定)は容易ですが, (X軸かY軸が重複していればいいだけなので) ナナメの判定にはどう実装しようか戸惑います. 斜めにコマを取られるケースの実装が厄介に感じられますが, 実際は結構で, 斜め筋が重複している場合の判定は, 2つのクイーンQ₁(x₁, y₁), Q₂(x₂, y₂)について, 次のようになります. どちらか一つの式が成立したら斜めで重複していることになります.

(x₁ - x₂) = (y₁ - y₂)
(x₁ - x₂) = (y₂ - y₁)

 上の式は, 右上から左下への斜め筋が, (1,1), (2,2), (3,3) ... とかなので. 下の式は, 左上から右下へがその逆なので,  y₁とy₂が反転します.

 これをClojureで, 実装するとこんな感じになりました. 実際に問題を解いているのは28行目までで, 他は文字列の出力関係です.

 conflict?ですでに置いたクイーンとの衝突を判定します. put-a-queenは, 次に置く一手を決めます. 引数の(x, y)以上の位置から探索を始めて, others(他のクイーンの座標[x y]のリスト)と重複しないような位置を返します. そのような場所がない場合は, falseを返します.

 solveは, バックトラックによって探索します. solveは, (x, y) = (0, 0), others = []から始めて, 可能な解をすべて計算します. 1行あたり1クイーンなので, 上から順に各行にQueenをputしていきます. xの初期位置が7を超えたら探索終わり. 左上から探索を始めてput-a-queenを何度も呼び出して, 矛盾しない解を探し続ける(solve関数内の末尾のrecur2つ). 解が見つかればputが成功したのだと考えて, その次の行の値を探しに行く. 解が見つからない場合, 前回putが失敗だったと考え, 一つ前の行のputを取り消して, そこから右へ向かって検索を行う.
 一つ解を求めたら, その解が失敗だったものと見なしてバックトラックを行い, solveを再び始めます(solve関数内のconsのあたり) .

(use '[leiningen.exec :only (deps)]) ; lein exec

;; slove the 8 queen problem
(defn conflict? [x y others]
  (and (not (empty? others))
       (let [x1 (ffirst others) y1 (second (first others))]
         (or (= x x1) (= y y1)
             (= (- x x1) (- y y1)) (= (- x x1) (- y1 y))
             (conflict? x y (rest others))))))

(defn put-a-queen [x y others]
  (cond
   (< 7 x) false
   (not (conflict? x y others)) [x y]
   :else (put-a-queen (inc x) y others)))

(defn solve [x1 y1 answer1]
  (loop [x x1 y y1 answer answer1]
    (let [rests (rest answer)]
      (cond
       (and (< 7 x) (= 0 y))
       nil
       (< 7 y)
       (cons answer (solve (inc (ffirst answer)) (dec y) rests))
       :else
       (if-let [xy (put-a-queen x y answer)]
         (recur 0 (inc y) (cons xy answer))
         (recur (inc (ffirst answer)) (dec y) rests))))))

;; make the list of solutions
(def solutions (solve 0 0 []))

;; show the results
(defn queen-str [xs]
  (let [dots #(take % (cycle "."))
        astr (partial apply str)]
    (map (fn [i] (astr (astr (dots i)) "Q" (dots (- 7 i))))
         (map second (sort xs)))))

(defn add-left [xs ys]
  (map str xs ys))

(defn spaces [width] ;; the list of space
  (cycle (apply str (take width (cycle " ")))))

(defn add-leftside-margin [width xs]
  (let [height (count xs)]
    (add-left (take height (spaces width)) xs)))

(defn gen-string [n xs]
  (->> (range n)
       (map (fn [x ns] (add-leftside-margin 10 x)) xs)
       (reduce add-left)))

(defn display-1-line [xs]
  (doall (map println xs))
  (println ""))

(defn display-all [given-list per]
  (loop [xs (partition-all per given-list)]
    (if (not (empty? xs))
      (do (display-1-line (gen-string per (map queen-str (first xs))))
          (recur (rest xs))))))

(display-all solutions 8)

 display-allで, 1列あたり8つの解を表示しています. 8-Queenの解の総数は, 92個あるそうですが, 次のような感じになりました.

u@mint ~/Dropbox/clj/8queen $ lein exec 8queen.clj
 Q....... Q....... Q....... Q....... .....Q.. ...Q.... ....Q... ..Q.....
 ......Q. ......Q. .....Q.. ....Q... Q....... Q....... Q....... Q.......
 ....Q... ...Q.... .......Q .......Q ....Q... ....Q... .......Q ......Q.
 .......Q .....Q.. ..Q..... .....Q.. .Q...... .......Q ...Q.... ....Q...
 .Q...... .......Q ......Q. ..Q..... .......Q .Q...... .Q...... .......Q
 ...Q.... .Q...... ...Q.... ......Q. ..Q..... ......Q. ......Q. .Q......
 .....Q.. ....Q... .Q...... .Q...... ......Q. ..Q..... ..Q..... ...Q....
 ..Q..... ..Q..... ....Q... ...Q.... ...Q.... .....Q.. .....Q.. .....Q..

 ....Q... ......Q. ....Q... ...Q.... .Q...... ....Q... .......Q ...Q....
 Q....... Q....... Q....... Q....... .....Q.. ..Q..... ..Q..... .....Q..
 ...Q.... ..Q..... .......Q ....Q... Q....... Q....... Q....... Q.......
 .....Q.. .......Q .....Q.. .......Q ......Q. ......Q. .....Q.. ....Q...
 .......Q .....Q.. ..Q..... .....Q.. ...Q.... .Q...... .Q...... .Q......
 .Q...... ...Q.... ......Q. ..Q..... .......Q .......Q ....Q... .......Q
 ......Q. .Q...... .Q...... ......Q. ..Q..... .....Q.. ......Q. ..Q.....
 ..Q..... ....Q... ...Q.... .Q...... ....Q... ...Q.... ...Q.... ......Q.

 ....Q... .....Q.. ....Q... .....Q.. ...Q.... .......Q ...Q.... ...Q....
 ......Q. ..Q..... ..Q..... ..Q..... .......Q ...Q.... .......Q ......Q.
 Q....... Q....... Q....... Q....... Q....... Q....... Q....... Q.......
 ...Q.... .......Q .....Q.. .......Q ..Q..... ..Q..... ....Q... .......Q
 .Q...... ...Q.... .......Q ....Q... .....Q.. .....Q.. ......Q. ....Q...
 .......Q .Q...... .Q...... .Q...... .Q...... .Q...... .Q...... .Q......
 .....Q.. ......Q. ...Q.... ...Q.... ......Q. ......Q. .....Q.. .....Q..
 ..Q..... ....Q... ......Q. ......Q. ....Q... ....Q... ..Q..... ..Q.....

 .....Q.. .....Q.. ......Q. ....Q... .Q...... .Q...... .....Q.. ......Q.
 ...Q.... ..Q..... ..Q..... ......Q. ....Q... .......Q .Q...... .Q......
 Q....... Q....... Q....... Q....... ......Q. .....Q.. ......Q. ...Q....
 ....Q... ......Q. .....Q.. ..Q..... Q....... Q....... Q....... Q.......
 .......Q ....Q... .......Q .......Q ..Q..... ..Q..... ..Q..... .......Q
 .Q...... .......Q ....Q... .....Q.. .......Q ....Q... ....Q... ....Q...
 ......Q. .Q...... .Q...... ...Q.... .....Q.. ......Q. .......Q ..Q.....
 ..Q..... ...Q.... ...Q.... .Q...... ...Q.... ...Q.... ...Q.... .....Q..

 .......Q ....Q... .....Q.. ....Q... ..Q..... .....Q.. ....Q... ..Q.....
 .Q...... .Q...... .Q...... .Q...... ....Q... ...Q.... .......Q .....Q..
 ...Q.... .......Q ......Q. .....Q.. ......Q. ......Q. ...Q.... .......Q
 Q....... Q....... Q....... Q....... Q....... Q....... Q....... Q.......
 ......Q. ...Q.... ...Q.... ......Q. ...Q.... .......Q ......Q. ....Q...
 ....Q... ......Q. .......Q ...Q.... .Q...... .Q...... .Q...... ......Q.
 ..Q..... ..Q..... ....Q... .......Q .......Q ....Q... .....Q.. .Q......
 .....Q.. .....Q.. ..Q..... ..Q..... .....Q.. ..Q..... ..Q..... ...Q....

 ......Q. .....Q.. ....Q... ..Q..... ..Q..... ....Q... .Q...... .Q......
 ....Q... ...Q.... .......Q .....Q.. .....Q.. ......Q. .....Q.. ....Q...
 ..Q..... ......Q. ...Q.... ...Q.... .......Q ...Q.... .......Q ......Q.
 Q....... Q....... Q....... Q....... Q....... Q....... ..Q..... ...Q....
 .....Q.. ..Q..... ..Q..... .......Q ...Q.... ..Q..... Q....... Q.......
 .......Q ....Q... .....Q.. ....Q... ......Q. .......Q ...Q.... .......Q
 .Q...... .Q...... .Q...... ......Q. ....Q... .....Q.. ......Q. .....Q..
 ...Q.... .......Q ......Q. .Q...... .Q...... .Q...... ....Q... ..Q.....

 .Q...... ......Q. .......Q ...Q.... ...Q.... ..Q..... ..Q..... .....Q..
 ......Q. .Q...... .Q...... .Q...... .Q...... .....Q.. ....Q... .......Q
 ....Q... .....Q.. ....Q... .......Q ......Q. .Q...... .Q...... .Q......
 .......Q ..Q..... ..Q..... .....Q.. ....Q... ......Q. .......Q ...Q....
 Q....... Q....... Q....... Q....... Q....... Q....... Q....... Q.......
 ...Q.... ...Q.... ......Q. ..Q..... .......Q ...Q.... ......Q. ......Q.
 .....Q.. .......Q ...Q.... ....Q... .....Q.. .......Q ...Q.... ....Q...
 ..Q..... ....Q... .....Q.. ......Q. ..Q..... ....Q... .....Q.. ..Q.....

 ..Q..... ..Q..... .....Q.. .....Q.. .....Q.. ...Q.... ...Q.... ...Q....
 .......Q ....Q... ..Q..... ..Q..... ..Q..... .......Q ......Q. .....Q..
 ...Q.... .......Q ......Q. ....Q... ....Q... ....Q... ....Q... .......Q
 ......Q. ...Q.... ...Q.... ......Q. .......Q ..Q..... ..Q..... ..Q.....
 Q....... Q....... Q....... Q....... Q....... Q....... Q....... Q.......
 .....Q.. ......Q. .......Q ...Q.... ...Q.... ......Q. .....Q.. ......Q.
 .Q...... .Q...... .Q...... .Q...... .Q...... .Q...... .......Q ....Q...
 ....Q... .....Q.. ....Q... .......Q ......Q. .....Q.. .Q...... .Q......

 .Q...... ...Q.... ...Q.... ..Q..... ..Q..... ..Q..... ....Q... ....Q...
 ...Q.... .Q...... .Q...... ......Q. .....Q.. .....Q.. ......Q. ......Q.
 .....Q.. ....Q... .......Q .Q...... .Q...... .Q...... .Q...... .Q......
 .......Q .......Q ....Q... .......Q ....Q... ......Q. .....Q.. .....Q..
 ..Q..... .....Q.. ......Q. ....Q... .......Q ....Q... ..Q..... ..Q.....
 Q....... Q....... Q....... Q....... Q....... Q....... Q....... Q.......
 ......Q. ..Q..... ..Q..... ...Q.... ......Q. .......Q ...Q.... .......Q
 ....Q... ......Q. .....Q.. .....Q.. ...Q.... ...Q.... .......Q ...Q....

 ......Q. ......Q. ....Q... ..Q..... ......Q. ...Q.... ...Q.... ....Q...
 ...Q.... ...Q.... ......Q. .....Q.. ..Q..... ......Q. .....Q.. ..Q.....
 .Q...... .Q...... .Q...... .......Q .......Q ....Q... .......Q .......Q
 ....Q... .......Q ...Q.... .Q...... .Q...... .Q...... .Q...... ...Q....
 .......Q .....Q.. .......Q ...Q.... ....Q... .....Q.. ......Q. ......Q.
 Q....... Q....... Q....... Q....... Q....... Q....... Q....... Q.......
 ..Q..... ..Q..... ..Q..... ......Q. .....Q.. ..Q..... ..Q..... .....Q..
 .....Q.. ....Q... .....Q.. ....Q... ...Q.... .......Q ....Q... .Q......

 .Q...... ...Q.... ....Q... ..Q..... .....Q.. .....Q.. .....Q.. ...Q....
 ......Q. .Q...... .Q...... ......Q. ...Q.... ..Q..... ..Q..... ......Q.
 ..Q..... ......Q. ...Q.... .Q...... .Q...... ......Q. ......Q. ..Q.....
 .....Q.. ..Q..... .....Q.. .......Q .......Q .Q...... .Q...... .......Q
 .......Q .....Q.. .......Q .....Q.. ....Q... ...Q.... .......Q .Q......
 ....Q... .......Q ..Q..... ...Q.... ......Q. .......Q ....Q... ....Q...
 Q....... Q....... Q....... Q....... Q....... Q....... Q....... Q.......
 ...Q.... ....Q... ......Q. ....Q... ..Q..... ....Q... ...Q.... .....Q..

 ...Q.... ....Q... ..Q..... ..Q.....
 .Q...... .Q...... ....Q... .....Q..
 ......Q. ...Q.... .Q...... ...Q....
 ..Q..... ......Q. .......Q .Q......
 .....Q.. ..Q..... .....Q.. .......Q
 .......Q .......Q ...Q.... ....Q...
 ....Q... .....Q.. ......Q. ......Q.
 Q....... Q....... Q....... Q.......

んー.