depth-first-search

深さ優先探索で、橋渡し問題を解く。

; 各stateは'n か's(対岸)のどちらか)
(defstruct state :farmer :wolf :goat :cabbage)

(defn opposite [x] (if (= x 'n) 's 'n))

(defn expand [st]
  (let [f (:farmer st) w (:wolf st)
        g (:goat st) c (:cabbage st)]
  (filter #(not= nil %) (conj []
        (if (= f w) (struct state (opposite f) (opposite w) g c))
        (if (= f g) (struct state (opposite f) w (opposite g) c))
        (if (= f c) (struct state (opposite f) w g (opposite c)))
        (struct state (opposite f) w g c)))))
            
(defn safe? [st]
  (let [f (:farmer st) w (:wolf st)
        g (:goat st) c (:cabbage st)]
  (not (or (and (= w g) (not (= f w)))
           (and (= g c) (not (= f g)))))))

(defn goal? [st]
  (let [f (:farmer st) w (:wolf st)
        g (:goat st) c (:cabbage st)]
  (= f w g c 'n)))

(defn node-expand
  "state: struct state
  hist: set of state that contains history"
  [state hist]
    (filter #(not (contains? hist %)) (expand state)))

(defn depth-first-search
  ([path]
    (if
      (goal? (first path)) (reverse path)
      (for [c (filter safe? (node-expand (first path) (set (rest path))))]
        (depth-first-search (cons c path))))))