algorithm - Haskell:如果我尝试超过55个步骤，骑士之旅将永远不会结束？

这是我的代码：

maxX=8; maxY=8;
maxSteps=60 -- If I change maxSteps=55 I get an answer
move :: [(Int, Int)] -> [( Int, Int)]
move list
   | lastX>maxX || lastY>maxY || lastX<=0 || lastY<=0 = []
   | lastMove `elem` (init list) = []
   | length list == maxSteps = list
   | length m1 == maxSteps = m1
   | length m2 == maxSteps = m2
   | length m3 == maxSteps = m3
   | length m4 == maxSteps = m4
   | length m5 == maxSteps = m5
   | length m6 == maxSteps = m6
   | length m7 == maxSteps = m7
   | length m8 == maxSteps = m8
   | otherwise = []
   where lastMove = last list
         lastX = fst lastMove
         lastY = snd lastMove
         m1 = move (list ++ [(lastX+1,lastY+2)])
         m2 = move (list ++ [(lastX+2,lastY+1)])
         m3 = move (list ++ [(lastX-1,lastY+2)])
         m4 = move (list ++ [(lastX-2,lastY+1)])
         m5 = move (list ++ [(lastX+1,lastY-2)])
         m6 = move (list ++ [(lastX+2,lastY-1)])
         m7 = move (list ++ [(lastX-1,lastY+2)])
         m8 = move (list ++ [(lastX-2,lastY-1)])
y = move [(1,1)]
main = print $ y

你知道为什么它永远不会结束吗（也许我可以等更多…）您是否有其他解决方案来实现相同的暴力算法，但会工作得更快？

最佳答案

它确实会终止（在我的计算机上运行大约1分钟）并产生正确的答案。
加快速度的一个简单方法是在列表的前面添加一个新的移动（并在打印之前反转结果）。添加第一个元素需要恒定的时间，而将元素追加到列表的后面在其大小上是线性的。
代码中也有一个错误：m3和m7是相同的在修复此bug后，将新的移动添加到列表的前部，代码在一秒钟内运行：

maxX = 8
maxY = 8
maxSteps = 60

move :: [(Int, Int)] -> [( Int, Int)]
move list
   | lastX > maxX || lastY > maxY || lastX <= 0 || lastY <= 0 = []
   | lastMove `elem` (tail list) = []
   | length list == maxSteps = list
   | length m1 == maxSteps = m1
   | length m2 == maxSteps = m2
   | length m3 == maxSteps = m3
   | length m4 == maxSteps = m4
   | length m5 == maxSteps = m5
   | length m6 == maxSteps = m6
   | length m7 == maxSteps = m7
   | length m8 == maxSteps = m8
   | otherwise = []
   where lastMove = head list
         lastX = fst lastMove
         lastY = snd lastMove
         m1 = move ((lastX + 1, lastY + 2) : list)
         m2 = move ((lastX + 2, lastY + 1) : list)
         m3 = move ((lastX - 1, lastY + 2) : list)
         m4 = move ((lastX - 2, lastY + 1) : list)
         m5 = move ((lastX + 1, lastY - 2) : list)
         m6 = move ((lastX + 2, lastY - 1) : list)
         m7 = move ((lastX - 1, lastY - 2) : list)
         m8 = move ((lastX - 2, lastY - 1) : list)
y = move [(1, 1)]
main = print $ reverse y

我又做了一些改变。首先，我摆脱了“手动”在每一步增加8个可能的移动我们可以用一张单子来做这种方法有助于避免像这样的错误。结果还发现，执行时间取决于检查新动作的顺序这个版本在大约一分钟内找到一个开放的教程（而且，在我看来，它比原始代码更可读）：

maxX = 8
maxY = 8
maxSteps = 64
shifts = [-1, 1, -2, 2]

move :: [(Int, Int)] -> [(Int, Int)]
move path
   | lastX > maxX || lastY > maxY || lastX <= 0 || lastY <= 0 = []
   | lastMove `elem` tail path = []
   | length path == maxSteps = path
   | not (null validNewPaths) = head validNewPaths
   | otherwise = []
   where lastMove@(lastX, lastY) = head path
         newPaths = [(lastX + x, lastY + y) : path | x <- shifts, y <- shifts, abs x /= abs y]
         validNewPaths = filter (\xs -> length xs == maxSteps) (map move newPaths)

main = print $ reverse (move [(1, 1)])