すごいH本 part89

騎士の旅

チェス盤の上にナイトの駒が1つだけ乗っており、ナイトを3回動かして特定のマスまで移動させられるかという問題を解く。

type KnightPos = (Int, Int)

moveKnight :: KnightPos -> [KnightPos]
moveKnight (c,r) = do
    (c', r') <- [(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)
                ]
    guard (c' `elem` [1..8] && r' `elem` [1..8])
    return (c', r')

ナイトの位置を表す型と、ナイトの現在位置をとって移動可能な位置を全て返す関数。

実行してみる

*Main> moveKnight (6,2)
[(8,1),(8,3),(4,1),(4,3),(7,4),(5,4)]
*Main> moveKnight (8,1)
[(6,2),(7,3)]

3手でいける位置をすべて返す関数

in3 :: KnightPos -> [KnightPos]
in3 start = do
    first <- moveKnight start
    second <- moveKnight first
    moveKnight second

実行

*Main> in3 (6,2)
[(8,1),(8,3),(4,1),(4,3),(7,4),(5,4),(5,2),(5,4),(8,1),(8,5),(6,1),(6,5),(8,1),(8,3),(4,1),(4,3),(7,4),(5,4),(8,3),(8,5),(4,3),(4,5),(7,2),(7,6),(5,2),(5,6),(5,2),(8,3),(6,3),(5,4),(5,6),(8,3),(8,7),(6,3),(6,7),(8,1),(8,3),(4,1),(4,3),(7,4),(5,4),(4,1),(4,3),(3,4),(1,4),(7,2),(7,4),(3,2),(3,4),(6,1),(6,5),(4,1),(4,5),(5,2),(5,4),(1,2),(1,4),(4,1),(4,5),(2,1),(2,5),(8,1),(8,3),(4,1),(4,3),(7,4),(5,4),(8,3),(8,5),(4,3),(4,5),(7,2),(7,6),(5,2),(5,6),(4,1),(4,3),(3,4),(1,4),(4,3),(4,5),(3,2),(3,6),(1,2),(1,6),(7,2),(3,2),(6,3),(4,3),(7,4),(7,6),(3,4),(3,6),(6,3),(6,7),(4,3),(4,7),(5,2),(1,2),(4,3),(2,3),(5,4),(5,6),(1,4),(1,6),(4,3),(4,7),(2,3),(2,7),(7,2),(7,4),(3,2),(3,4),(6,1),(6,5),(4,1),(4,5),(7,4),(7,6),(3,4),(3,6),(6,3),(6,7),(4,3),(4,7),(6,1),(6,3),(7,4),(6,5),(6,7),(7,4),(7,8),(8,1),(8,3),(4,1),(4,3),(7,4),(5,4),(8,5),(8,7),(4,5),(4,7),(7,4),(7,8),(5,4),(5,8),(5,2),(5,4),(8,1),(8,5),(6,1),(6,5),(5,4),(5,6),(8,3),(8,7),(6,3),(6,7),(5,2),(5,4),(1,2),(1,4),(4,1),(4,5),(2,1),(2,5),(5,4),(5,6),(1,4),(1,6),(4,3),(4,7),(2,3),(2,7),(8,1),(8,3),(4,1),(4,3),(7,4),(5,4),(8,5),(8,7),(4,5),(4,7),(7,4),(7,8),(5,4),(5,8),(6,1),(6,3),(2,1),(2,3),(5,4),(3,4),(6,5),(6,7),(2,5),(2,7),(5,4),(5,8),(3,4),(3,8)]

全てのパターンが列挙されてよくわからん。

2つの位置をとり、その間をちょうど3手で到達できるかどうかを調べる関数を作る

canReachIn3 :: KnightPos -> KnightPos -> Bool
canReachIn3 start end = end `elem` in3 start

実行

*Main> (6,2) `canReachIn3` (6,1)
True
*Main> (6,2) `canReachIn3` (7,3)
False

3手で到達できるルートを表示する演習問題は挫折

所感

演習問題が解けない。無能感を存分に味わった。

すごいHaskellたのしく学ぼう！