在Haskell回溯數獨

我正在嘗試在Haskell中建立一個回溯數獨解算器。但是我陷入了最後的一點。我創建了一個名爲nextBoards的函數，它返回所有可能的soduko板，其中下一個空的位置用可能的值填充。現在我試圖在Haskell中使用回溯，但是我不能使用while循環之類的東西，現在我對如何執行此操作感到困惑。我之前在Java中做過一個數獨求解器，但我現在完全停留在如何在Haskell中完成它。在Haskell回溯數獨

-- Generate the next boards for a given board 
nextBoards :: Board -> [Board] 
nextBoards b = 
    let position = findFirstEmpty b 
    in [update z (snd position) (fst position) b | z <- options b (snd position) (fst position)] 

-- We found the real solution 
solve :: Board -> [Board] -> Board 
solve focus options 
    | not (notEmpty focus) = focus 
-- We hit a dead path try the next option 
solve focus options 
    | solve (head options) (tail options) 
-- We are solving the focus, generate the next boards 
-- and save the rest in the options 
solve focus options 
    | solve (head (nextBoards focus)) (tail (nextBoards focus))

我真的不知道如何繼續。

來源

2016-03-02 Pieter Verschaffelt

你有候選人板的名單，並解決了.. –

@牛米的功能。是的，我知道，我不太清楚你的意思？ –

更多提示：[filter]（http://hackage.haskell.org/package/base-4.8.2.0/docs/Prelude.html#v:filter） – isanco

您可以實現通過（部分）解空間的後退的解決方案（如所有可能Board S）S與像一個類型簽名：

backtrack :: S -> [S]

隨着S當前狀態，並[S]所有列表有效的板子。現在有一般三種可能的選擇：包含我們的解決方案

我們發現是solved的狀態，我們返回一個列表（單）：
```
backtrack s | solved s = [s] 
```
我們已經找到了死線索，在這種情況下，我們不再把精力投入到它，並返回一個空列表：
```
  | invalid s = [] 
```
或有可能，我們必須進一步部署我們的解決方案，我們產生children：已經從s先進的一步法狀態，並調用遞歸原路返回，我們返回所有backtrack這幫孩子的concat：
```
  | otherwise = concatMap backtrack $ children s 
```

或者把他們放在一起：

backtrack :: S -> [S] 
backtrack s | solved s = [s] 
      | invalid s = [] 
      | otherwise = concatMap backtrack $ children s

的invalid後衛可以通過簡單地生成children空列表可以省略狀態（因爲你的解決方案可能會這樣做）或通過防止永遠生成無效的Board s。

現在接地這對於您的問題，產生children將回落到您的nextBoards功能：

children = nextBoards

或美化你的函數一點：

children :: Board -> [Board] 
children s = [update s y x v | v <- options s y x] 
    where (x,y) = findFirstEmpty s

現在解決（或backtrack）方法被定義爲：

backtrack :: Board -> [Board] 
backtrack s | not (notEmpty s) = [s] 
      | otherwise = concatMap backtrack $ children s

backtrack將生成一個列表全部有效解決Sudoku板（原來的地方填充，仍然填寫）。是懶洋洋地生成的列表，所以如果你想一個有效的解決方案，你可以簡單地使用head：

solve :: Board -> Board 
solve = head . backtrack

來源

2016-03-02 15:50:59

在Haskell回溯數獨

回答

相關問題