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

の2つのブランチは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]、iffoo :: 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を初めて使用する場合は、モナドを扱う前に時間をかけることをお勧めします。そして、IOにはモナドが必要です。

IOモナドなどを使用せずに最初に動作するプログラムをまとめることをお勧めし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は ありません）IOprint_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

結果を返すだけです。solve次に、 withinをいじり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 に答える