遞歸回溯Haskell

Question

好吧，所以我試圖在Haskell中創建一個Sudoku求解器，但我得到一個錯誤，說我無法與實際類型IO（）匹配預期類型[[Int]]。這是我嘗試在遞歸求解器，錯誤信息，以及其它代碼的相關部分：

遞歸求解嘗試：

test i j q s_board = if ((valid_row i q s_board)&&(valid_column j q s_board)&& (valid_sub_board i j q s_board)) then (solve (set_value i j q s_board)) else s_board 

foo i j s_board = if ((get_value i j s_board) == 0) then [test i j q s_board | q <- [1..9]] else s_board 

solve s_board = if (full_board s_board) then (print_board s_board) else [foo i j s_board | i <- [0..8], j <- [0..8]] 

如果我包括爲有效的所有定義這個問題將是非常長列，行等功能，但我已檢查確保這些功能。有了這個代碼，我發現了以下錯誤消息：

Couldn't match expected type `[[Int]]' with actual type `IO()' 
In the return type of a call of `print_board' 
In the expression: (print_board s_board) 
In the expression: 
    if (full_board s_board) then 
     (print_board s_board) 
    else 
     [foo i j s_board | i <- [0 .. 8], j <- [0 .. 8]] 

而且，這裏是我使用打印我的板代碼：

-- showLine: this function provides formating for a single row 
showLine :: [Int] -> String 
showLine = intercalate " | " 
     . map unwords 
     . chunksOf 3 
     . map show 

-- showBoad: this function provides formating for the entire board  
showBoard :: [[Int]] -> String 
showBoard = intercalate "---------------------\n" 
      . map unlines 
      . chunksOf 3 
      . map showLine 


-- print_board: this function is meant to print out the entire board 
print_board :: [[Int]] -> IO() 
print_board s_board = putStrLn $ showBoard s_board 

。你們看看有什麼有什麼問題我到目前爲止。我對Haskell完全陌生，這是我嘗試的第一個真正的程序。任何幫助將不勝感激。

Answer 1

的一個if的兩個分支必須具有相同的類型，但在

if (full_board s_board) then 
    (print_board s_board) 
else 
    [foo i j s_board | i <- [0 .. 8], j <- [0 .. 8]] 

的True分支具有類型IO（），而False分支是一個事物列表（在這種情況下很可能是板），所以如果foo :: Int -> Int -> [[Int]] -> a的類型是[a]。

你應該分開關注點，遞歸回溯應該給你一個（完整）板的列表，打印應該從另一個上下文中調用solve。

我的建議是沿

type Grid = [[Int]] 

solve :: Grid -> [Grid] 
solve s_board = if full_board s_board 
        then [s_board] -- full means no branches, singleton list 
        else concat [foo i j s_board | i <- [0 .. 8], j <- [0 .. 8]] 

test :: Int -> Int -> Int -> Grid -> [Grid] 
test i j q s_board 
    | valid_row i q s_board 
     && valid_column j q s_board 
     && valid_sub_board i j q s_board = solve $ set_value i j q s_board 
    | otherwise = [] 

foo :: Int -> Int -> Grid -> [Grid] 
foo i j s_board 
    | get_value i j s_board == 0 = concat [test i j q s_board | q <- [1 .. 9]] 
    | otherwise     = [] 

線的東西所以每一個函數返回的Grid秒的列表，以及一個死端通過返回的解決方案的空單可以達到修剪來自當前網格。當沒有死路被診斷時，所有允許的組合都被嘗試。

然後，您可以有

solve_and_print :: Grid -> IO() 
solve_and_print s_board = case solve s_board of 
          [] -> putStrLn "Sorry, that board had no solution." 
          (g:_) -> print_board g 

但是，這會產生相同的解決方案多次，並非常低效窮盡搜索，因爲猜測埃夫裏的組合將在所有可能的順序進行。

因此，讓我們來看看如何讓它更有效率。如果我們有一個算法來選擇我們猜測值的下一個位置，我們可以修剪結果列表中解決方案的排列和重複。最簡單的這種算法是挑選第一個空閒單元。所以我們寫一個函數來查找網格的空閒單元格。

就這樣，我們也有一個測試電網是否已滿，full_board = null . free_cells，順便說一句。因此，我們可以開始我們的解決

solve :: Grid -> [Grid] 
solve s_board 
    | null frees = [s_board] 
    | otherwise = guesses s_board (head frees) 
     where 
     frees = free_cells s_board 

接下來，我們找到了值，我們可能將在細胞(i,j)，

possible_values :: Grid -> (Int, Int) -> [Int] 
possible_values s_board (r,c) = [q | q <- [1 .. 9], isPossible s_board q] 
    where 
    isPossible v = valid_row r v s_board 
        && valid_column c v s_board 
        && valid_sub_board r c v s_board 

，並放置在細胞並進行進一步

guesses :: Grid -> (Int, Int) -> [Grid] 
guesses s_board (r,c) = [solution | v <- possible_values s_board (r,c) 
            , solution <- solve $ set_value r c v s_board] 

Answer 2

如果您是Haskell的新手，在處理Monads之前花點時間是個好主意。 IO需要單子。

使用IO monad（putStrLn等），首先得到一個工作程序而不使用將是一個好主意。只需加載您的程序ghci，並簡單地調用您的功能。當你對此感到滿意時，並且你在REPL上有一個函數可以給你答案，你可以考慮將它打印到STDOUT（與'世界'交互 - Haskell需要對monad進行一些理解）。

所以，把你的solve功能對於初學者：

讓solve做到這一點 - 不是更多。因此，而不是做IO這裏，如：

solve s_board = 
    if (full_board s_board) then (print_board s_board) 
    else [foo i j s_board | i <- [0..8], j <- [0..8]] 

的問題是，if和else條款不具有相同的類型。 else返回[[Int]];和if的IO單子（的print_board 結果不[[Int]]）

將其更改爲：

-- sometimes it helps to be explicit - solve takes a puzzle, returns a solved one. 
solve :: [[Int]] -> [[Int]] 
solve s_board = 
    if (full_board s_board) then s_board    -- type of s_board is [[Int]] 
    else [foo i j s_board | i <- [0..8], j <- [0..8]] -- and so is this 

簡單的返回結果。然後你在內亂搞ghci，繼續修復你的程序並重新加載它直到它工作，一旦它發生了，只需編寫一個函數來調用求解所需的參數並打印它。

所以一旦你有你的程序工作的真正的肉，可以解決IO的分心：

print_board s_board = putStrLn $ show $ solve s_board 

那麼這將讓閱讀的好下一步：http://www.haskell.org/tutorial/io.html