haskell 中的回溯数独

Question

我正在尝试在 Haskell 中构建回溯数独求解器。但我被困在最后一点。我创建了一个名为 nextBoards 的函数，其中 returns 所有可能的数独板，其中下一个空白位置用可能的值填充。现在我正在尝试在 Haskell 中使用回溯，但我不能使用 while 循环之类的东西，现在我真的很困惑如何做到这一点。我之前在 Java 做过数独解算器，但目前我完全不知道如何在 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))

我真的不知道如何进行。

Answer 1

您可以在（部分）解决方案 space（像所有可能的 Boards）S 上实施回溯解决方案，类型签名如下：

backtrack :: S -> [S]

S 当前状态，[S] 所有有效板的列表。现在一般有三种可能的选择：

我们找到了一个状态solved，我们return一个列表（单例）包含我们的解决方案：
```
backtrack s | solved s = [s]
```
发现一条死路，那我们就不再努力了，return一个空列表：
```
            | invalid s = []
```
或者我们可能必须进一步部署我们的解决方案，我们生成 children：从 s 前进了一步的状态，并递归调用回溯，我们 return 这些 children 的所有 backtrack 的 concat:
```
            | otherwise = concatMap backtrack $ children s
```

或者把它们放在一起：

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

可以通过简单地为 invalid 状态生成一个空的 children 列表（正如您的解决方案可能会做的那样）或通过防止生成无效 Boards.

现在为您的问题奠定基础，生成 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 将生成所有有效解决的数独板的列表（最初填写的地方，保持填写）。该列表是延迟生成的，所以如果你想要 one 有效的解决方案，你可以简单地使用 head:

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

haskell 中的回溯数独

Backtrack sudoku in haskell

recursion

haskell

sudoku

backtracking