深さ優先探索で、橋渡し問題を解く。
; 各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))))))