Haskellでのsudokuソルバーの最適化

Question

私はHaskellでsudokuソルバーを書いた。これは、リストを通過し、それが見つかった「0」（空のセル）が合うことができる番号を取得し、それらをしようとします。例えば、この作品いくつかのパズルのために

import Data.List (group, (\\), sort) 
import Data.Maybe (fromMaybe) 

row :: Int -> [Int] -> [Int] 
row y grid = foldl (\acc x -> (grid !! x):acc) [] [y*9 .. y*9+8] 
    where y' = y*9 
column :: Int -> [Int] -> [Int] 
column x grid = foldl (\acc n -> (grid !! n):acc) [] [x,x+9..80] 
box :: Int -> Int -> [Int] -> [Int] 
box x y grid = foldl (\acc n -> (grid !! n):acc) [] [x+y*9*3+y' | y' <- [0,9,18], x <- [x'..x'+2]] 
    where x' = x*3 

isValid :: [Int] -> Bool 
isValid grid = and [isValidRow, isValidCol, isValidBox] 
    where isValidRow = isValidDiv row 
      isValidCol = isValidDiv column 
      isValidBox = and $ foldl (\acc (x,y) -> isValidList (box x y grid):acc) [] [(x,y) | x <- [0..2], y <- [0..2]] 
      isValidDiv f = and $ foldl (\acc x -> isValidList (f x grid):acc) [] [0..8] 
      isValidList = all (\x -> length x <= 1) . tail . group . sort -- tail removes entries that are '0' 

isComplete :: [Int] -> Bool   
isComplete grid = length (filter (== 0) grid) == 0 

solve :: Maybe [Int] -> Maybe [Int] 
solve grid' = foldl f Nothing [0..80] 
    where grid = fromMaybe [] grid' 
      f acc x 
      | isValid grid = if isComplete grid then grid' else f' acc x 
      | otherwise = acc 
      f' acc x 
      | (grid !! x) == 0 = case guess x grid of 
       Nothing -> acc 
       Just x -> Just x 
      | otherwise  = acc 

guess :: Int -> [Int] -> Maybe [Int] 
guess x grid 
    | length valid /= 0 = foldl f Nothing valid 
    | otherwise   = Nothing 
    where valid = [1..9] \\ (row rowN grid ++ column colN grid ++ box (fst boxN) (snd boxN) grid) -- remove numbers already used in row/collumn/box 
      rowN = x `div` 9 -- e.g. 0/9=0 75/9=8 
      colN = x - (rowN * 9) -- e.g. 0-0=0 75-72=3 
      boxN = (colN `div` 3, rowN `div` 3) 
      before x = take x grid 
      after x = drop (x+1) grid 
      f acc y = case solve $ Just $ before x ++ [y] ++ after x of 
      Nothing -> acc 
      Just x -> Just x 

を、この1：

sudoku :: [Int] 
sudoku = [5,3,0,6,7,8,0,1,2, 
      6,7,0,0,0,0,3,4,8, 
      0,0,8,0,0,0,5,0,7, 
      8,0,0,0,0,1,0,0,3, 
      4,2,6,0,0,3,7,9,0, 
      7,0,0,9,0,0,0,5,0, 
      9,0,0,5,0,7,0,0,0, 
      2,8,7,4,1,9,6,0,5, 
      3,0,0,2,8,0,1,0,0] 

は、しかし、この1、第二の下で取った：私は、仕上がりを見ていない

sudoku :: [Int] 
sudoku = [5,3,0,0,7,0,0,1,2, 
      6,7,0,0,0,0,3,4,8, 
      0,0,0,0,0,0,5,0,7, 
      8,0,0,0,0,1,0,0,3, 
      4,2,6,0,0,3,7,9,0, 
      7,0,0,9,0,0,0,5,0, 
      9,0,0,5,0,7,0,0,0, 
      2,8,7,4,1,9,6,0,5, 
      3,0,0,2,8,0,1,0,0] 

。私は正しい結果を返すので、これがメソッドの問題だとは思わない。

プロファイリングでは、ほとんどの時間が "isValid"関数で費やされていることがわかりました。その機能について明らかに非効率的/遅いことがありますか？

Answer 1

実装はもちろん改良可能ですが、それは問題ではありません。問題は、2番目のグリッドでは、簡単な推測と検査のアルゴリズムは、ロットのバックトラッキングが必要であるということです。各機能の速度を1000倍に高速化しても、グリッドが存在します（グリッドが一意でない場合は、最初に宇宙の年齢の何倍かを必要とします）。

これを避けるには、より良いアルゴリズムが必要です。そのようなケースを避けるためのかなり効率的な方法は、可能性が最も少ない正方形を最初に推測することです。それはすべての悪いケースを避けるわけではありませんが、それらを多く減らします。

もう1つのことは、length thing == 0のチェックをnull thingに置き換えることです。比較的短いリストがここで発生すると、効果は限られますが、一般的には劇的になることがあります（また、length list <= 1を使用しないでください）。代わりにnull $ drop 1 listを使用してください。

Answer 2

isValidList = all (\x -> length x <= 1) . tail . group . sort -- tail removes entries that are '0' 

元のリストは、任意のゼロが含まれていない場合は、tailは何か他のもの、2つのものの、おそらくリストを削除します。私はtail . group. sortをgroup . sort . filter (/= 0)に置き換えます。

isValidBoxとisValidDivは、foldlを使用するとわかりません。なぜなら、mapが適切と思われるからです。私は何かを逃したのですか？彼らは何かひどく賢いことをしていますか？