algorithm - 为什么骑士不覆盖所有的 table ？

Question

我希望马从 (1,1) 开始并尝试在整个 table 上移动。这是我的代码:

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

我假设您正在尝试解决 knight's tour Haskell 中的问题。在那种情况下，您的问题是您使用的是贪婪算法，该算法对于骑士的巡回赛问题是失败的。如果从 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.

简而言之，您的骑士在某个时刻进行了“错误的”转弯，并将自己卡在一个位置，如果不重复一个位置就无法脱身。为了避免这种情况，您需要使用某种回溯算法，这样当骑士犯了这样的错误时，它可以撤消其 Action 并尝试其他方法。幸运的是，Haskell 使用 List monad 使这变得相对容易。如果您不熟悉 monad，它们是 Haskell 不可或缺的一部分，您可以了解它们 here .