ClojureでN-Queen問題を解いてみる
「関数型オブジェクト指向AIプログラミング」もちまちま読んでいきたい。
有名な8-Queen問題を一般化したN-Queen問題。本では再帰的に解いているので、まずはそれをなぞってみる。
とりあえずデータの定義。4x4のグリッドに以下のような配置の場合:
X-Q-X-X
X-X-X-Q
Q-X-X-X
X-X-Q-X
データとしては以下のようなList of Vectorsで表す。
'([3 1] [2 3] [1 0] [0 2])
次に、縦横斜めで重複しているピースがないかどうかを調べるコード:
(defn check-position [position] (every? #(apply distinct? (map % position)) [first second #(apply + %) #(apply - %)]))
関数のベクトルをevery?の第二引数にすることでコードがダブつかなくなる。[i j] [a b]の二つのピースが右肩上がり斜め方向に並べばi+j = a+bで、右肩下がりに並ぶ場合はi-j = a-bなのも一つのポイント。
(defn n-queen [n] (letfn [(queen-rec [i] (if (zero? i) (map #(list (vector i %)) (range n)) (filter check-position (for [position (queen-rec (dec i)) piece (map #(vector i %) (range n))] (conj position piece)))))] (queen-rec (dec n))))
とりあえず本に載っているコードのやっていることを変換すると上記のようになる。
ただ、よく見るとあまり再帰にする意味がない。結局一旦一直線にi=0まで降りていって、そこから結果をスタックの上の方に投げていく構造。分岐するわけでもないので、実際にはi=0ではじめてi=n-1まで到達するだけでいい。
それをreduceで表すとこうなる:
(defn n-queen-reduce [n] (letfn [(f [positions i] (filter check-position (for [position positions piece (map #(vector i %) (range n))] (conj position piece))))] (reduce f '(()) (range n))))
こっちの方がわかりやすいのではないかと思う。
しかしreduceで使う関数の名前のつけ方がわからないのはなんとかならないだろうか・・・。