川渡りパズル

川渡りパズルを Haskell で解いてみた。川渡りパズルというのは、次のような問題だ。

川岸に狐とガチョウと豆の袋を持った農夫がいる。農夫が目を離すと、狐はガチョウを食べてしまうし、ガチョウは豆をついばんでしまう。ところで、川を渡るのに一艘の小舟があるがこれは、農夫と荷物をひとつしか運べない。狐がガチョウを食べたり、ガチョウが豆を食べたりしないように、これらを川の向こう岸に船で運ぶにはどうするかというパズルだ。

ネットを方々検索して作ったのが次のプログラムだ。

import List

data Member = Fox | Goose | Beans
  deriving (Show, Eq, Ord)

data Farmer = LeftSide | RightSide
  deriving (Show, Eq)

data State = State {left :: [Member], right :: [Member], farmer :: Farmer}
  deriving (Show, Eq)

beginState = State {left = [Fox, Goose, Beans], right = [], farmer = LeftSide}

goal s = length (left s) == 0

forbidden xs = (elem Fox xs && elem Goose xs) || (elem Goose xs && elem Beans xs)

available s = (farmer s == LeftSide && (not (forbidden (right s)))) || (farmer s == RightSide && (not (forbidden (left s))))

updateLeft s = filter available ([State {left = delete x (left s), right = sort (x : right s ), farmer = RightSide} | x <- left s] ++ [State {left = left s, right = right s, farmer = RightSide}])

updateRight s = filter available ([State {right = delete x (right s), left = sort (x : left s), farmer = LeftSide} | x <- right s] ++ [State {left = left s, right = right s, farmer = LeftSide}])

findNext s
  | farmer s == LeftSide = updateLeft s
  | otherwise = updateRight s

search s path
  | goal s = [reverse (s:path)]
  | otherwise = concatMap (\x -> search x (s:path)) [x | x <- findNext s, not (elem x path)]

きちんと説明できるほど理解しているわけではないので、とりあえず実行例。

Main> mapM putStrLn $ map show $ head $ search beginState []
State {left = [Fox,Goose,Beans], right = [], farmer = LeftSide}
State {left = [Fox,Beans], right = [Goose], farmer = RightSide}
State {left = [Fox,Beans], right = [Goose], farmer = LeftSide}
State {left = [Beans], right = [Fox,Goose], farmer = RightSide}
State {left = [Goose,Beans], right = [Fox], farmer = LeftSide}
State {left = [Goose], right = [Fox,Beans], farmer = RightSide}
State {left = [Goose], right = [Fox,Beans], farmer = LeftSide}
State {left = [], right = [Fox,Goose,Beans], farmer = RightSide}

パソコンを使わないで答えを出す時間より、プログラムを作る時間のほうが何倍もかかってしまった。実際、人間の頭脳がなんとなくこなしてしまう仕事を、プログラム化するのにずいぶんいろいろな条件を考えなくてはいけなかった。普段何気なくやっている推論が実はいろいろな条件を上手に使いこなしていたのだと、いまさらながら脳の推理能力の優秀さに気がついた。
[PR]
by tnomura9 | 2011-06-13 23:44 | Haskell | Comments(0)
<< 探索 順列と組み合わせ >>