algorithm - Haskell:如果我尝试超过 55 步，Knight tour 永远不会结束？

Question

这是我的代码:

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

你知道为什么它永远不会完成吗(也许我可以再等等......)？您是否有其他解决方案来实现相同的强力算法但工作速度更快？

Answer 1

它会终止(在我的电脑上运行大约 1 分钟)并产生正确答案。

一个简单的加快速度的方法是在列表的前面添加一个新的移动(并在打印之前反转结果)。添加第一个元素需要常数时间，而将元素追加到列表的后面在其大小上是线性的。

您的代码中还有一个错误:m3 和m7 是一样的。修复这个错误并将新的移动添加到列表的前面后，代码运行不到一秒:

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 个可能的 Action 。我们可以使用列表来做到这一点。这种方法有助于避免此类错误。结果还表明，执行时间取决于检查新移动的顺序。这个版本在大约一分钟内找到一个 open tour(并且，在我看来，它比原始代码更具可读性):

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)])