Clojureで騎士の巡回問題を解いてみる
(defn knight-tour [n] (let [board (set (for [i (range n) j (range n)] [i j])) dirs (for [a [1 2] i [-1 1] j [-1 1]] (let [b (- 3 a)] [(* i a) (* j b)])) tour (fn f [pos visited i] (if (= (* n n) i) visited (let [reachable (->> dirs (map #(map + pos %)) (filter board) (remove visited) (map vec))] (some->> reachable not-empty (map #(f % (assoc visited % i) (inc i))) (remove nil?) first))))] (tour [0 0] {[0 0] 0} 1)))
Lazy EvaluationだとBacktrackingが非常に簡単でありがたい。mapして最初のnilじゃない値を返すと書くだけで、正解が見つかればその時点でそれ以降の再帰は呼び出されない。逆に再帰先からnilが帰ってきたときのみ次の再帰に移るし、すべての再帰先からnilが帰ってきたら空リストからfirstでnilになるので、nilを再帰元に返す。
不満としては関数内関数の定義がやはり冗長というかネスト・インデントが深すぎるように感じてしまう点と、再帰のためにまたしてもfとかいう名前をつけていること。letfnにしたほうがよかっただろうか。
n=6で走らせて表示させてみる。
(def grid-map (knight-tour 6)) (doseq [i (range 6)] (doseq [j (range 6)] (print (format "%2d "(grid-map [i j])))) (println))
表示の仕方が非常に手続き型なのは悲しい・・・
n=6だと5分弱かかるが結果はこの通り:
0 29 12 5 2 23 11 4 1 22 13 6 30 17 28 3 24 21 33 10 31 16 7 14 18 27 34 9 20 25 35 32 19 26 15 8
左上から始めて何回目の移動でどのマスに到達するか、を表す。