我希望马从 (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
步后停下来?
最佳答案
我假设您正在尝试解决 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 .
关于algorithm - 为什么骑士不覆盖所有的 table ?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/40445481/