递归回溯Haskell

Question

好吧所以我试图在Haskell中创建一个Sudoku Solver,但是我收到一个错误,说我无法将预期的类型[[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完全不熟悉,这是我尝试过的第一个真正的程序.任何帮助将不胜感激.

Answer 1

a的两个分支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],如果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]