在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回溯数独

回答

相关问题