蠻力數獨解決Haskell

Question

所以我目前正在編寫一個數獨求解器，並且必須創建求解函數。 考慮：

solve :: Sudoku -> [Maybe Sudoku] 

其中數獨的是[[Maybe Int]]。

這是通過蠻力來解決的，所以我遞歸地檢查數獨是否可以被解決，是否滿了，但是是否中斷約束（例如在一行/列/塊中重複的數字），否則， 9遞歸地在第一個找到的空白點直到它工作或直到我知道它永遠不會工作。

當我發現第一個空白空間接受1，因爲它是新的輸入，但後來意識到這不起作用，那麼我必須回去並將其更改爲2或更改爲接下來工作並再次嘗試解決。我如何去做這件事？這裏是目前的代碼我有解決：

solve :: Sudoku -> [Maybe Sudoku] 
solve sud 
    | isSudoku sud && isSolved sud && isOkay sud = [Just sud] 
    | isSudoku sud && isSolved sud && not (isOkay sud) = [Nothing] 
    | isSudoku sud && not (isSolved sud) = solve (helper sud (blank sud) False 1) 

helper :: Sudoku -> Pos -> Bool -> Int -> Sudoku 
helper sud pos check n 
    | n > 9 || n < 1 || check = sud 
    | n > 0 && n < 10 && not check = 
     do 
      let newSud = (update sud pos (Just n)) 
      helper newSud pos (isOkay newSud) (n+1) 

任何投入如何去做到這一點？

編輯：數獨是這樣實現的：

data Sudoku = Sudoku [[Maybe Int]] 
deriving (Eq) 

迄今我已經得到了反饋，上面的代碼已經解決數獨遊戲。問題在於當有足夠的空白點時，某個地點可以接受多個號碼，而不是僅與一個號碼一起工作。說一個空白點與數字5和8一起工作，但8是正確的答案，5是不可解決的。然後，我必須回去改變它，並再次嘗試解決所有下一個空白。

Answer 1

這是非常廣泛的，但基本上這種算法的list-monad是你的朋友;） - 也不需要在那裏也許在那裏，如果你只是代表的情況下，你不能找到一個解決方案[]

這裏是僞代碼它：

solve :: Sudoku -> [Sudoku] 
solve sud 
    | isSudoku sud && isSolved sud && isOkay sud = [sud] 
    | isSudoku sud && isSolved sud && not (isOkay sud) = [] 
    | isSudoku sud && not (isSolved sud) = do 
     nr <- [1..9] 
     let sud' = sud `updateNextUnsetCellWith` nr 
     solve sud' 

當然

，你必須先寫updateNextUnsetCellWith功能 - 它應該只是設置nr到第一未設置單元格，並返回更新的狀態，當然，它假設其他兩種情況會觸發if沒有未設置的單元格。

請注意這個蠻力變種將推動你瘋了它會採取很長的時間產生合理的問題的結果。

Answer 2

我還沒有檢查過你的代碼，但總的來說，你必須像有多個解決方案一樣行事，並試圖找到它們。這意味着您可以隨時重複所有可能的選擇，其中的選擇是(Cell, Integer)。

因此，你輸入第一個選項，它會給你一個更完整的數獨，然後嘗試以同樣的方式解決新的數獨。這會導致數獨解決，或者在你完成Sudoku之前，你在某些時候用盡了選擇。因此，無論何時，您都會收到解決數獨​​或無法解決的跡象。在後一種情況下，您嘗試下一個選擇，直到數獨解決，或者您自己的選擇用盡，並且您返回一條指示，表明沿此路徑沒有解決方案。

作爲一個方面說明：當我嘗試這種方法時，我不得不意識到brute foce太慢了。您在訂購選項時會獲得可接受的性能，以便您首次嘗試選擇最少數量的單元格。

另一方面說明：要測試這一點，你可以採取一個解決數獨，並刪除一個數字，看看是否找到解決方案。然後你刪除兩個數字等。