用PROLOG求解“奇迹数独”

如果你还没有看过它，那你应该看看这段“CrackingTheCryptic”上的视频，这段视频讲述了一位竞争激烈的数独解算者正在解决奇迹数独之谜的过程：

观看这段视频让我想起了我上的一门编程语言课程，我们用Prolog编写了一个简单的数独解算器。由于PROLOG是一种声明性语言，因此编写数独解算器非常简洁。本质上，程序员需要做的就是定义游戏的约束，而Prolog足够聪明，可以找到解决方案：

数独(行)：-length(ROWS，9)，MAPLIST(SAME_LENGTH(ROWS)，ROWS)，APPEND(ROWS，Vs)，Vs INS 1.9，MAPLIST(ALL_DISTINCT，ROWS)，转置(ROWS，COLUMN)，MAPLIST(ALL_DISTINCT，COLUMNS)，ROWS=[AS，Bs，Cs，Ds，ES，Fs，Gs，HS，IS]，块(As，Bs，Cs)，块(Ds，ES，Fs)，块(Gs，HS，IS)。块([]、[]、[])。BLOCKS([N1，N2，N3|NS1]，[N4，N5，N6|NS2]，[N7，N8，N9|NS3])：-ALL_DISTINCT([N1，N2，N3，N4，N5，N6，N7，N8，N9])，BLOCKS(NS1，NS2，NS3)。

上面的代码来自SWI Prolog文档，它使用约束逻辑编程扩展。您可以在SWISH Online Prolog环境中使用它。

这段代码最酷的地方在于，它既可以作为数独解算器工作，也可以作为ASA数独生成器工作。你可以用一个部分求解的电路板来查询它，它会找到所有有效的解决方案。这意味着您还可以给它一个空白板，Prolog将生成所有可能的数独解决方案(尽管这需要一些时间，因为有$6.7\x 10^{21}$有效的板1)。

作为免责声明，我不太了解Prolog。我只是勉强修修补补，所以我确信我对它的使用是次优的。尽管如此，我还是能够写出一个可以工作的奇迹数独解算器。😄。

要编写奇迹数独谜题的解算器，我们需要对以下规则进行编码：

由骑士移动或国王移动分隔的任何两个单元格都不能包含相同的数字。

正交邻接约束是最容易编码的。对于电路板上的每个3x3网格，我们需要确保中间的数字与它的垂直/水平邻居至少相差一个。

%-[[N1，N2，N3]，%-[N4，N5，N6]，%-[N7，N8，N9]]正交邻接([_，N2，N3|NS1]，[N4，N5，N6|NS2]，[_，N8，N9|NS3])：-abs(N5-N2)#>；1，abs(N5-N4)#>；1。1，abs(N5-N8)#>；1，追加([N2，N3]，NS1，Z1)，追加([N5，N6]，NS2，Z2)，追加([N8，N9]，NS3，Z3)，正交邻接(Z1，Z2，Z3)。正交相邻([_，_]，[_，_]，[_，_])。%-基本大小写。

接下来是国王的移动限制，同样简单。我决定使用ALL_DISTINCT函数作为不平等的快捷方式。我们可以在N5'；的邻居上使用#\=运算符，但我们还需要处理网格的边框，这就是为什么我们还需要约束角点-N1、N3、N7和N9。不幸的是，这会创建一些重复的约束。

%-[[N1，N2，N3]，%-[N4，N5，N6]，%-[N7，N8，N9]]KINS_MOVE([N1，N2，N3|NS1]，[N4，N5，N6|NS2]，[N7，N8，N9|NS3])：-ALL_DISTINCT([N1，N2，N4])，ALL_DISTINCT([N4，N7，N8])，ALL_DISTINCT([。n6])，ALL_DISTINCT([N5，N4，N2])，ALL_DISTINCT([N2，N5，N6])，ALL_DISTINCT([N5，N6，N7])，ALL_DISTINCT([N4，N5，N8])，APPEND([N2，N3]，NS1，Z1)，APPEND([N5，N6]，NS2，Z2)，APPEND([N8，N9]，NS3，Z3)。Z3)。Kings_Move([_，_]，[_，_]，[_，_])。

我最初以为骑士的移动限制会更难写，但事实证明，它的瓷砖和其他的一样好：骑士所有的“L”移动也都固定在3x3网格内。

%-[[N1，N2，N3]，%-[N4，N5，N6]，%-[N7，N8，N9]]KNIGES_MOVE([N1，N2，N3|NS1]，[N4，N5，N6|NS2]，[N7，N8，N9|NS3])：-N1#\=N6，N1#\=N8，N3#\=N8，N3#\=N4，N7#\。N9#\=N2，APPEND([N2，N3]，NS1，Z1)，APPED([N5，N6]，NS2，Z2)，APPED([N8，N9]，NS3，Z3)，KINNIGES_MOVE(Z1，Z2，Z3)。Knights_Move([_，_]，[_，_]，[_，_])。

现在我们已经为奇迹数独规则编写了关系，我们需要将它们添加到原来的数独函数中。每个函数一次处理3行，并且需要对电路板中每个3行的窗口进行操作。执行此操作的详细方法如下：

数独(排)：-.。行=[As，Bs，Cs，Ds，Es，Fs，Gs，Hs，is]，.。正交相邻(As，Bs，Cs)，正交相邻(Bs，Cs，Ds)，正交相邻(Cs，Ds，Es)，正交相邻(Ds，Es，Fs)，正交相邻(Es，Fs，Gs)，正交相邻(Fs，Gs，Hs)，正交相邻(Gs，HS，IS)，.

我们在行(A，B，C)上重新断言正交相邻关系，然后在(B，C，D)上重新断言，依此类推。我们可以使用Maplist使其更紧凑：

数独(排)：-.。行=[As，Bs，Cs，Ds，Es，Fs，Gs，Hs，is]，.。追加(块1，[_，_]，行)，追加([_|块2]，[_]，行)，追加([_，_|块3]，[]，行)，Maplist(正交相邻，块1，块2，块3)，Maplist(骑士_移动，块1，块2，块3)，Maplist(KINGS_MOVE，Chunk1，Chunk2，Chunk3)，Maplist(KINS_MOVE，Chunk1，Chunk2，Chunk3)，Maplist(KINS_MOVE，Chunk1，Chunk2，Chunk3。

解释：我们使用append创建3个“块”行。Chunk1等价于[As，Bs，Cs，Ds，Es，Fs，Gs]，Chunk2是[Bs，Cs，Ds，Es，Fs，Gs，Hs]，Chunk3is[Cs，Ds，Es，Fs，Gs，Hs，is]。然后，我们使用Maplist将这些块应用到我们的关系中。当您将多个列表传递给Maplist时，它会调用与第j个列表的第i个元素的ProvidedRelationship作为关联的参数。

数独(行)：-length(ROWS，9)，MAPLIST(SAME_LENGTH(ROWS)，ROWS)，APPEND(ROWS，Vs)，Vs INS 1.9，MAPLIST(ALL_DISTINCT，ROWS)，转置(ROWS，COLUMN)，MAPLIST(ALL_DISTINCT，COLUMNS)，ROWS=[AS，Bs，Cs，Ds，ES，Fs，Gs，HS，IS]，块(As，Bs，Cs)，块(Ds，ES，Fs)，块(Gs，hs，is)，追加(块1，[_，_]，行)，追加([_|块2]，[_]，行)，追加([_，_|块3]，[]，行)，Maplist(正交_相邻，块1，块2，块3)，Maplist(Knights_Move，Chunk1，Chunk2，Chunk3)，Maplist(KINGS_MOVE，Chunk1，Chunk2，Chunk3)，Maplist(KINGS_MOVE，Chunk1，Chunk2，Chunk3)，Maplist(KINGS_MOVE，Chunk1，Chunk2，Chunk3)。

我们可以用PROLOG编码这个问题，方法是创建一个9x9电路板，并用2位数的提示填充它。我们让董事会的其余部分保持原样，让Prology知道这些都是自由变量。我们的解算器将使1和2保持在它们设置的位置，但是可以自由选择其余的值，这取决于拼图的限制。

Maplist(标签，行)告诉Prolog为行中的每个自由变量查找具体的值。(否则，我们只能得到每个变量的约束列表)。

？-问题(1，行)，数独(行)，最大列表(标签([FFC，枚举])，行)，最大列表(PARTRAY_子句，行).[4，8，3，7，2，6，1，5，9，4，8，8，3，7，7，2，6，1，5，9，4，8，8，3，7，2，6].[1，5，9，4，8，3，7，2，6].[8，3，7，2，6，1，5，9，4].[2，6，1，5，9，4，8，3，7].[5，9，4，8，3，7，2，6，1，5，9，4，4，8].[6，1，5，9，4，8，3].[6，1，5，9，4，8，3].[3，7，2，6，1，5，9，4，8，3].[6，1，5，9，4，8，3，7、2].[9、4、8、3、7、2、6、1、5]。

解算器起作用了！为了确认我们不只是走运，如果能在拼图的另一个实例中尝试一下这一点，那就太好了。幸运的是，CrackingTheCryptic频道后来发布了一段后续视频，其中有第二个谜题：

问题(2，[[_，_，_]，[_，4，_]，[_，_，3，_，_]，[_，_]，[_，_，_，_]，[_，_]，[_，_，_，_]]))。问题(2，行)，数独(行)，Maplist(标签，行)，Maplist(画像_子句，行).[9，4，8，3，7，2，6，1，5].[3，7，2，6，1，5，9，4，8，3，7，2].[6，1，5，9，4，8，3，7，2].[4，8，3，7，5].[4，8，3，7，2].[4，8，3，7，2].[4，8，3，7，2].[4，8，3，7，2，6，1，5，9].[7，2，6，1，5，9，4，8，3，7，2，6].[8，3，7，2，6，1，5，9，4，8，3，7，7].[2，6，1，5，9，4，8，3，7].[5，9、4、8、3、7、2、6、1]。

又答对了！Prolog解算器的一个有用的方面是，它能够找到任何给定提示的所有有效解。在PROLOG REPL中，一旦找到解决方案，就可以按；迭代到下一个解决方案。在上述两个谜题中，提示恰好有一个有效的解决方案。根据定义，数独谜题应该只有一个解，所以这些谜题实际上是有效的。

现在我们已经有了奇迹数独问题的解算器，我们可以生成一些我们自己的解算器吗？为了测试这一点，我用一个完全空白的板查询了求解器：

问题(3，[[_，_，_]，[_，_，_]，[_，_]，[_，_，_，_]，[_，_，_，_]))。问题(3，行)、数独(行)、Maplist(标签，行)、Maplist(PROTRAY_子句，行)。

结果呢？井…。没什么。只有我的笔记本电脑风扇旋转的声音。我认为，我指示Prolog搜索解决方案的方式太天真了，在没有提示的情况下无法生成董事会。我打赌Maplist(标签，行)正在执行整个空间的“猜测和检查”搜索，如果没有提示的限制，生成电路板的速度太慢了。

不能用这个解算器生成新奇的电路板有点令人失望。也许有更多PROLOG知识的人可以实现更有效的解决方案。

在写这篇文章时，我偶然发现了Hakan Kjellerstrand用Picat写的奇迹数独解题，这是一种我以前从未听说过的基于逻辑的编程语言。

Hakan的解算器比我的快得多-它是如此之快，以至于它可以生成所有可能的奇迹数独棋盘，所需时间大约是我的解开一个谜题实例所需的时间。令人惊讶的是，符合奇迹数独限制的解决方案板只有72个2。我对Picat的了解甚至比我对Prolog的了解还要少，所以我不确定Hakan的解决方案怎么会比我的快这么多。

我建议您通读一下Picat解算器源代码。由于Hakan的解题速度如此之快，它能够发现奇迹数独谜题的其他几个有趣的性质：。

只有1个提示的板有8个解决方案，永远-无论提示是哪个数字，或者它放在哪里。

有许许多多有效的2位数提示。例如，有2320种方法可以将1和2放在黑板上，从而得到唯一的解决方案。因为只有72个独特的解决方案板，在你用完提示之前，你已经用完了有趣的解决方案。

Prolog在我的日常工作中没有太多用处，但在这种(相对)晦涩的语言中工作很有趣，因为它非常适合这项任务。我在心里也做了一个笔记，看看Picat。Hakan'；的网站上有大量解决方案的示例问题。

我也不知道还有一些益智游戏制造商扩展了传统的数独游戏--它的维基百科页面上有十几种不同的游戏变种。CrackingTheCryptic YouTube频道有充足的素材供拼图变体编写解算器。