Clojureで騎士の巡回問題を解いてみる

N-Queen問題に続いて騎士の巡回。

(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 

左上から始めて何回目の移動でどのマスに到達するか、を表す。