algorithm - 在 Haskell 中扩展数独求解器的功能

Question

我很难理解 this 的一部分数独解算器的一部分。我不明白扩展功能是如何工作的。

expand                :: Matrix Choices -> [Matrix Choices]
expand m              =
   [rows1 ++ [row1 ++ [c] : row2] ++ rows2 | c <- cs]
   where
      (rows1,row:rows2) = break (any (not . single)) m
      (row1,cs:row2)    = break (not . single) row

这里发生了什么？一个简短的解释会很有帮助。

Answer 1

幸运的是，您链接的代码有很好的注释。引用上面的函数:

The function expand behaves in the same way as collapse, except that it only collapses the first square with more than one choice:

从直觉上讲，expand 函数接受数独并找到第一个单元格，其中仍有多个选择。然后，它会扩展该选择，生成许多数独，每个数独都有一个特定的选择。也就是说，它变成了(大致):

[ some data ... , [ data, ... [1,2,3] ... data ] , other data ]

进入

[[ some data ... , [ data, ... [1] ... data ] , other data ]
,[ some data ... , [ data, ... [2] ... data ] , other data ]
,[ some data ... , [ data, ... [3] ... data ] , other data ]]

关键行是这些:

 (rows1,row:rows2) = break (any (not . single)) m

这里，row 是第一行，其中有一个单元格具有非单一选择。 rows1,rows2 是数独中的前/后行。

 (row1,cs:row2)    = break (not . single) row

此处，cs 是row 中第一个非单选单元格。 row1,row2 是该行中的左/右部分。