Haskell，我的「Knights_tour」方法停止工作，當我從61更改爲63時

我是Haskell世界的新手，可能我的問題很愚蠢，但我無法理解ghci的行爲或ghc在這種情況下。Haskell，我的「Knights_tour」方法停止工作，當我從61更改爲63時

我試圖通過對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 [email protected]((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步移動「頭部$ 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)

來源

2013-10-06 Sérgio Paulo

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-06 19:05:24

非常感謝@Karolis但是...經過10個週期後，我的系統幾乎崩潰:) ghc達到了1.94G的內存... –

這就是要點。你正在試圖做一個荒謬的數量計算。顯然，在你的情況下，直到61步，只有前幾個可能性需要計算，但在63步，其中大部分處理。這就是你使用蠻力算法得到的結果。 –

你覺得我可以修改我的代碼來工作嗎？通過我的新手護目鏡，99問題頁面上的解決方案與我的aproach有很大不同... –

Haskell，我的「Knights_tour」方法停止工作，當我從61更改爲63時

回答

相關問題