Haskell sudoku solver

Question

私は関数型プログラミングの初心者で、私はHaskellでsudokuソルバーを作っています。 Sudokusは[(posX,posY),value)]に含まれていますが、位置が空白の場合はリストに含まれていません。

現在、私には、step :: Sudoku -> [Sudoku]という機能があります。スドクがすでに解決されている場合は、そのスドクを含む単一の要素リストを返します。まだ解決されていないが可能な場合は、はっきりと書き込むことができる最初の空白の位置をチェックし（正しい番号が1つのみ）、それをスドクに追加します。そのような空白点がない場合（複数の数値が収まるため）、最初の空白点が取得され、その点のバリエーションがすべて異なる複数のsudokusを含むリストが作成されます。最後に、もしスドクが解けないならば、それは空のリストを返します。

私はそれが疲れていることを知っていますが、これは私がそれをするように割り当てられている方法ですので、私と一緒にご負担ください。次に行うべきことは、step（これは本当にそれを解決するための単なるステップです）を使って実際の解決関数を書くことです。それは次のようにしなければなりません：solve :: Sudoku -> [Sudoku]。それは、スドクを取得し、可能なすべてのソリューションをリストに返します。

問題はどのようにわからないということです。それはおそらく黒い魔法を使った再帰であり、私はその周りに頭を浮かべることはできません。

ありがとうございます。

編集：ここに完全なソースコードがありますが、最後の機能もわかりましたが、現在は非常に遅いです。より速くする方法はありますか？

type Pos = (Int, Int) 
type Cell = (Pos, Int) 
type Sudoku = [Cell] 
type Block = Int 

--example: 
sudoku :: Sudoku 
sudoku = [((0,0),3),((0,1),6),((0,4),7),((0,5),1),((0,6),2), 
      ((1,1),5),((1,6),1),((1,7),8), 
      ((2,2),9),((2,3),2),((2,5),4),((2,6),7), 
      ((3,4),1),((3,5),3),((3,7),2),((3,8),8), 
      ((4,0),4),((4,3),5),((4,5),2),((4,8),9), 
      ((5,0),2),((5,1),7),((5,3),4),((5,4),6), 
      ((6,2),5),((6,3),3),((6,5),8),((6,6),9), 
      ((7,1),8),((7,2),3),((7,7),6), 
      ((8,2),7),((8,3),6),((8,4),9),((8,7),4),((8,8),3)] 

--returns a list of numbers already used in a row 
numsInRow :: Sudoku -> Int -> [Int] 
numsInRow sud n = [ i | ((x,y), i) <- sud, x==n ] 

--returns a list of numbers already used in a column 
numsInCol :: Sudoku -> Int -> [Int] 
numsInCol sud n = [ i | ((x,y), i) <- sud, y==n ] 

--returns the index of a block (goes from 0 to 8) in which the given position is contained 
posToBlock :: Pos -> Block 
posToBlock (x,y) = x - (x `mod` 3) + y `div` 3 

--returns all the positions in a block 
blockToPositions :: Block -> [Pos] 
blockToPositions n 
    | n `notElem` [0..8] = error ("blockToPositions: bad block number " ++ show n) 
    | otherwise = [ (x,y) | x <- [0..8], y <- [0..8], n == (x - (x `mod` 3) + y `div` 3) ] 

--returns the numbers already used in a block 
numsInBlock :: Sudoku -> Block -> [Int] 
numsInBlock sud n = [ i | ((x,y), i) <- sud, (j,k) <- blockToPositions n, (x,y) == (j,k)] 

--decides if all the elements are unique in a list 
allUnique :: Eq a => [a] -> Bool 
allUnique [] = True 
allUnique (x:xs) 
    | x `elem` xs = False 
    | otherwise = allUnique xs 

--returns if a sudoku is valid, so it is 9x9, all the values are between 1 and 9, and there are no repeating numbers in any row, column, or block 
isSudokuPuzzle :: Sudoku -> Bool 
isSudokuPuzzle sud = and [and [ x `elem` [0..8] && y `elem` [0..8] && z `elem` [1..9] | ((x,y), z) <- sud ] , and [ allUnique a | a <- [numsInRow sud i | i <- [0..8] ]] , and [ allUnique a | a <- [numsInCol sud i | i <- [0..8] ]] , and [ allUnique a | a <- [numsInBlock sud i | i <- [0..8] ]]] 

--returns if a sudoku is filled, so all the fields have values (and only one value) 
isFilled :: Sudoku -> Bool 
isFilled sud = allUnique [ (x,y) | ((x,y), z) <- sud ] && length [ (x,y) | ((x,y), z) <- sud ] == 81 

--a sudoku is solved if it is a valid sudoku and filled 
isSolved :: Sudoku -> Bool 
isSolved sud = isSudokuPuzzle sud && isFilled sud 

--decides if a position is blank (has no value, not filled) in a sudoku 
isBlank :: Sudoku -> Pos -> Bool 
isBlank sud (x,y) = (x,y) `notElem` [ (j,k) | ((j,k),l) <- sud ] 

--gives back a list of all empty positions in a sudoku 
blankPositions :: Sudoku -> [Pos] 
blankPositions sud = [ (x,y) | x <- [0..8], y <- [0..8], isBlank sud (x,y) ] 

--returns a list of all valid numbers in a position (empty if position is already filled) 
possibleNumsOnPos :: Sudoku -> Pos -> [Int] 
possibleNumsOnPos sud (x,y) 
    | isBlank sud (x,y) = [ i | i <- [1..9], i `notElem` numsInRow sud x, i `notElem` numsInCol sud y, i `notElem` numsInBlock sud (posToBlock (x,y)) ] 
    | otherwise = [] 

--returns a list of all the blank positions and their possible values in a sudoku 
possibleNumsForBlankPos :: Sudoku -> [(Pos, [Int])] 
possibleNumsForBlankPos sud = [ ((x,y), possibleNumsOnPos sud (x,y)) | x <- [0..8], y <- [0..8], isBlank sud (x,y)] 

--dedices if a sudoku has a solution (so there is still at least one blank and it has at least one valid value) 
hasSolution :: [(Pos, [Int])] -> Bool 
hasSolution [] = False 
hasSolution a = and [ not (null l) | ((j,k),l) <- a ] 

--returns a list of blanks that have only one possible valid value 
uniqueNumForBlankPos :: [(Pos, [Int])] -> [(Pos, Int)] 
uniqueNumForBlankPos a = [ ((j,k),head l) | ((j,k),l) <- a, length l == 1 ] 

--fills a field in a sudoku with a given value 
insertElem :: Sudoku -> Pos -> Int -> Sudoku 
insertElem sud (x,y) n 
    | isBlank sud (x,y) = ((x,y),n):sud 
    | otherwise = error ("insertElem: position " ++ show (x,y) ++ " is not blank") 


--If the sudoku is already solved, it returns a single element list containing that sudoku. 
--If it is not already solved, but can be, it checks for the first blank position that has only one possible valid value, and adds it to the sudoku. 
--If there is no such blank point (so all blanks have multiple valid values), it gets the first blank point and makes a list containing multiple sudokus with all the different, valid variations of that point. 
--Lastly, if the sudoku cannot be solved, it returns an empty list. 
step :: Sudoku -> [Sudoku] 
step sud 
    | isSolved sud = [sud] 
    | hasSolution (possibleNumsForBlankPos sud) && not (null (uniqueNumForBlankPos (possibleNumsForBlankPos sud))) = [ insertElem sud (fst (head (uniqueNumForBlankPos (possibleNumsForBlankPos sud)))) (snd (head (uniqueNumForBlankPos (possibleNumsForBlankPos sud)))) ] 
    | hasSolution (possibleNumsForBlankPos sud) && null (uniqueNumForBlankPos (possibleNumsForBlankPos sud)) = [ insertElem sud (head (blankPositions sud)) x | x <- possibleNumsOnPos sud (head (blankPositions sud)) ] 
    | not (hasSolution (possibleNumsForBlankPos sud)) = [] 

--It gets a sudoku, and returns all the possible solutions in a list, but currently it is very slow. 
solve :: Sudoku -> [Sudoku] 
solve sud 
    | not (isSudokuPuzzle sud) = error "solve: improper sudoku" 
    | otherwise = 
    until done f l 
     where 
     l = return sud 
     f (x:xs) = (f xs) ++ step x 
     f [] = [] 
     done m = and (map isSolved m) && and (map isSudokuPuzzle m) 

Answer 1

ステップにそれを打破

：部分的な解決策は、完成ソリューションである場合

1. どのように伝えることができますか？単純：Sudokuは埋め込み位置のリストなので、完成した解決策は81個の要素を持つリストです。 （標準の9x9数独パズルを想定します）。

   タスク：作業が完了したときにソリューションのリストを考えるとisFinished :: Sudoku -> Bool

2. を書く、どのようにあなたが知っているのですか？容易：リストのすべてのソリューションは完成したソリューションです。直接テストするか、x == (step x)かどうか確認してください。

   タスク：入力した完成ソリューションを削除する書き込みpartials :: [Sudoku] -> [Sudoku]。

3. ソリューションのリストを処理するには、それぞれにstepを適用して結果を収集する必要があります。これは、リストモナドが理想的である計算のタイプ、すなわちpartial_solutions >>= stepです。

4. solve :: Sudoku -> [Sudoku]を実装するには、solve' :: [Sudoku] -> [Sudoku]（solve initState = solve' [initState]）と書いてください。 solve'は、上記のことを念頭に置いておくと、かなり簡単な再帰関数です。