『すごいHaskell たのしく学ぼう!』の13.6節ではリストモナドによる非決定性計算を使ってチェスのナイトが3手で指定したマスに到達できるかを計算する関数が紹介された。
ghci> (6, 2) `canReachIn3` (6, 1) True
のように始点と終点を指定すると到達の可否がかえってくる。
節尾の演習にどのように到達できるか教えてくれるようにせよとあったので書いてみる。
import Monad
type KnightPos = (Int, Int)
type KnightTrack = [KnightPos]
moveKnight :: KnightTrack -> [KnightTrack]
moveKnight ((c, r) : xs) =
map addLog $
filter onBoard [(c+2,r-1), (c+2,r+1), (c-2,r-1), (c-2,r+1)
,(c+1,r-2), (c+1,r+2), (c-1,r-2), (c-1,r+2)]
where onBoard (c, r) = c `elem` [1..8] && r `elem` [1..8]
addLog pos = pos : (c, r) : xs
in3 :: KnightTrack -> [KnightTrack]
in3 start = return start >>= moveKnight >>= moveKnight >>= moveKnight
canReachIn3 :: KnightPos -> KnightPos -> [KnightTrack]
canReachIn3 start end =
filter (\(pos : track) -> pos == end) $ in3 [start]
canReachIn3は真偽値でなくナイトの軌跡を返すように変更した。到達できないときは [] が帰る。
ghci>canReachIn3 (6,2) (6,1) [[(6,1),(7,3),(8,1),(6,2)],[(6,1),(5,3),(4,1),(6,2)],[(6,1),(5,3),(7,4),(6,2)], [(6,1),(8,2),(7,4),(6,2)],[(6,1),(7,3),(5,4),(6,2)],[(6,1),(4,2),(5,4),(6,2)]] ghci>canReachIn3 (6,2) (7,3) []