蛮力数独解决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太慢了。您在订购选项时会获得可接受的性能，以便您首次尝试选择最少数量的单元格。

另一方面说明：要测试这一点，你可以采取一个解决数独，并删除一个数字，看看是否找到解决方案。然后你删除两个数字等。