回溯haskell的sudoku

Question

我想在Haskell建一个回溯的sudoku解算器。但我被困在最后一点了。我创建了一个名为nextBoards的函数，它返回所有可能的soduko板，其中下一个空位置填充了可能的值。现在我试图在Haskell中使用回溯，但是我不能使用this循环之类的东西，现在我真的很困惑如何做到这一点。我以前用Java做过sudoku解算器，但目前我完全无法在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

您可以在(部分)解决方案空间(像所有可能的Boards) S上实现回溯解决方案，其类型签名如下：

backtrack :: S -> [S]

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

• 我们找到了一个状态，即solved，我们返回一个列表(单例)，其中包含我们的解决方案： 回溯解s=s
• 我们找到了一条死胡同，在这种情况下，我们不再为它付出努力，而是返回一个空的列表： 无效的s= []
• 或者，我们可能需要进一步部署我们的解决方案，我们生成children：那些已经从s前进了一步的国家，并且递归地调用回溯，我们返回这些子级的所有backtrack的concat： \否则= concatMap回溯$ children s

或者把它们放在一起：

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

可以省略invalid保护，只需为invalid状态生成一个空的children列表(您的解决方案可能会这样做)，或者防止生成无效的Board。

现在，针对您的问题，生成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将生成所有有效解决数独板的列表(最初填充的位置，仍然是填充的)。列表是延迟生成的，因此，如果您想要一个有效的解决方案，只需使用head

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