騎士爲什麼不把所有的桌子都蓋上？

Question

我想讓騎士從(1,1)開始，並嘗試在整個桌子上移動。這是我的代碼：

canMove :: (Int -> Int) -> (Int -> Int) -> [(Int,Int)] -> Bool 

canMove (x) (y) list 
     | (x (fst lastMove),y (snd lastMove)) `elem` list = False 
     | newX> 8 || newY> 8 || newX<=0 || newY<=0 = False 
     | otherwise = True 
     where lastMove = last list 
       newX = x (fst lastMove) 
       newY = y (snd lastMove) 

move :: [(Int, Int)] -> [(Int, Int)] 
move list 
    | length list == 64 = list 
    | canMove (+1) (+2) list = move (list ++ [(x+1,y+2)]) 
    | canMove (+2) (+1) list = move (list ++ [(x+2,y+1)]) 
    | canMove (subtract 1) (+2) list = move (list ++ [(x-1,y+2)]) 
    | canMove (subtract 2) (+1) list = move (list ++ [(x-2,y+1)]) 
    | canMove (subtract 1) (subtract 2) list = move (list ++ [(x-1,y-2)]) 
    | canMove (subtract 2) (subtract 1) list = move (list ++ [(x-2,y-1)]) 
    | canMove (+1) (subtract 2) list = move (list ++ [(x+1,y-2)]) 
    | canMove (+2) (subtract 1) list = move (list ++ [(x+2,y-1)]) 
    | otherwise = list 
    where lastMove = last list 
     x = fst lastMove 
     y = snd lastMove 

y=length (move [(1,1)]) 

main = print $ y 

爲什麼騎士在34之後停下腳步？

Answer 1

我假設你試圖解決在Haskell中的knight's tour問題。在這種情況下，你的問題是你正在使用貪婪算法，這對騎士的巡視問題是失敗的。如果您從y函數中刪除length，則可以看到算法選擇的路徑。

[(1,1),(2,3),(3,5),(4,7),(6,8),(5,6),(7,7),(5,8),(4,6),(6,7), 
(8,8),(7,6),(5,7),(7,8),(6,6),(8,7),(7,5),(6,3),(8,4),(6,5), 
(8,6),(7,4),(5,5),(3,6),(4,8),(2,7),(1,5),(3,4),(2,6),(3,8), 
(1,7),(2,5),(3,7),(1,8)] 
-- From (1,8), we can go to either (4,6) or (3,5). 
-- But we've already been to both of those positions. 

簡單地說，你的騎士取得在某些時候是「錯誤的」轉，並得到自身停留在一個位置，它不可能不重複的位置脫身。爲了避免這種情況，你需要使用某種回溯算法，這樣當騎士犯這樣的錯誤時，它可以撤消它的動作並嘗試其他的東西。幸運的是，Haskell使List monad變得相對容易。如果你不熟悉單子，他們對Haskell是不可或缺的，你可以學習他們here。