0

我是 Haskell 世界的新手，我的问题可能很愚蠢，但我无法理解 ghci 或 ghc 在这种情况下的行为。

我试图从 haskell.org 上的 99 个问题中解决旧的“Knights_Tour”问题，而我发现的解决方案在 61 个动作之前都可以正常工作（总共 62 个位置，仅缺少 2 个位置）。但是，如果我将总移动次数增加到 63 ghci 或 runhaskell 或编译的程序在一分钟或更长时间后停止工作而没有答案。

该程序：

import Control.Monad (guard)

type Position = (Int, Int)
type Positions = [Position]

moveKnight :: Positions -> [Positions]
moveKnight pos@((col, row):xs) = do
     (col', row') <- [(col+2, row-1), (col+2, row+1), (col-2, row-1), (col-2, row+1),
                      (col+1, row-2), (col+1, row+2), (col-1, row-2), (col-1, row+2)]
     guard (col' `elem` [1..8] && row' `elem` [1..8] && (not . (`elem` pos)) (col', row'))
     return ((col', row'):pos)

moveMany :: Int -> Position -> [Positions]
moveMany moves start = return (return start) >>= foldr (<=<) return (replicate moves moveKnight)

getMoves :: Position -> [Positions]
getMoves start = moveMany 63 start

我认识到答案的顺序不是很好（缺少反向，但它不会改变整体行为）。当我用 61 步做“head $ getMoves (1,1)”时，我在 0.23 秒内得到答案，但 63 步根本没有答案。谁能向我解释为什么这不起作用，以及这种情况的一些解决方法？为什么其他解决方案（如 99 个问题页面中的解决方案）工作正常？

注意：我尝试了一个不同的 moveMany 函数，但又获得了 1 次移动（62，只有 1 次移动......）

moveMany' :: Int -> Position -> [Positions]
moveMany' moves start = tour moves (return (return start))
            where tour 1 pos = pos
                  tour n pos = tour (n - 1) (pos >>= moveKnight)
4

1 回答 1

0 
run :: Int -> [Positions] -> IO ()
run 0 _ = putStrLn "Stopping"
run n pos = do
  let pos' = pos >>= moveKnight
  print $ length pos'
  run (n-1) pos'

尝试运行这个。它可能会澄清一些事情。这里没有什么花哨的，真的。

于 2013-10-06T19:05:24.933 回答