1

好的，所以我试图在 Haskell 中创建一个数独求解器，但我收到一条错误消息，指出我无法将预期类型 [[Int]] 与实际类型 IO () 匹配。这是我对递归求解器、错误消息和其他相关代码的尝试：

递归求解器尝试：

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 完全陌生，这是我尝试过的第一个真正的程序。任何帮助将不胜感激。

4

2 回答 2

7

an 的两个分支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是事物列表（在这种情况下可能是板），所以类型是[a], if foo :: Int -> Int -> [[Int]] -> 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                  = []

所以这些函数中的每一个都返回一个Grids 列表，并且通过返回一个可以从当前网格到达的解决方案的空列表来修剪死胡同。当还没有诊断出死胡同时，尝试所有允许的组合。

然后你可以有

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

但是，这会产生多次相同的解决方案，并且对于穷举搜索来说效率非常低，因为每个猜测组合都会按照所有可能的顺序进行。

那么，让我们来看看如何提高效率。如果我们有一个算法来选择我们猜测值的下一个位置，我们可以修剪结果列表中解决方案的排列和重复。最简单的算法是选择第一个空闲单元格。因此，让我们编写一个函数来查找网格的空闲单元格。

free_cells :: Grid -> [(Int,Int)]
free_cells s_board = [(i,j) | i <- [0 .. 8], j <- [0 .. 8], get_value i j s_board == 0]

顺便说一句，我们还测试了网格是否已满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]
于 2012-11-29T04:19:30.773 回答
4

如果您是 Haskell 的新手，最好在处理Monads之前花点时间。IO 需要单子。

在不使用 IO monad（putStrLn等）的情况下，首先将一个工作程序放在一起是个好主意。只需加载您的程序ghci并简单地调用您的函数。当您对此感到满意时，并且您在 REPL 上有一个功能可以为您提供答案，您可以考虑将其打印到 STDOUT（与“世界”交互 - Haskell 需要对此有一些了解单子）。

因此，将您的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 is not [[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

只需返回结果。然后你弄乱了solveinside ghci，继续修复你的程序并重新加载它直到它工作，一旦它工作，只需编写一个函数来使用所需的参数调用solve并打印它。

因此，一旦您的程序真正开始工作，您就可以解决 IO 的干扰问题：

print_board s_board = putStrLn $ show $ solve s_board

那么这将是一个很好的下一步阅读：http ://www.haskell.org/tutorial/io.html

于 2012-11-29T04:13:15.417 回答