在Wolfram语言中使用整数优化创建和解决数独游戏

数独是一个锻炼玩家的分析、数学能力和智力的游戏。Wolfram社区中一直以来就常有人讨论解决各种数独问题，而且也有一些很惊艳的解决数独问题的代码（https://community.wolfram.com/groups/-/m/t/974303）。在这个基础上，我想展示一些Mathematica版本12.1中的新功能，包括如何将数独问题变成一个使用整数优化的问题，使用LinearOptimization函数解决，还有如何生成新的数独游戏。

用编程的方法解决数独问题

在一个典型的数独问题中，玩家面对的是一个九宫格，在某些位置上会有一些数字。

以下是一个标准数独面板：

玩家需要用1到9之间的数字填满每个空格（如果是个m宫格则为1到m之间的数字），并需要遵循以下三个规则：

1. 每一行必须包括1-9这九个数字。

2. 每一列必须包括1-9这九个数字。

3. 每个3*3的区块中（由白或灰色标示出的区域）必须包括1-9这九个数字。

玩家必须遵守这三条规则来填写空白处的数字。

我会使用SparseArray来代表初始数独问题，放在LinearOptimization的“数独游戏”范例中：

想要把这个问题当做整数优化的问题来解决，设

是元素（i, j）的变量。设

是向量

的元素k。当

，则(i, j)对数字k成立。每一个（i, j）只包含一个数字，所以

只能包含一个非零元素，例如

：

应用第一条数独规则，每一行必须包含所有数字，即

，其中

是一个九维向量：

第二条规则规定每一列必须包含所有数字，即

：

第三条规则规定每一个3x3的区块必须包含所有数字，即

：

把以上结合起来，即是任一数独游戏的约束条件：

集合所有变量：

把已知值转换为约束条件。如果元素(i, j)对k成立，则

：

LinearOptimization以一组线性约束为条件，通常用于最小化某个线性目标。在这种情况下，因为在可行解的目标为0：

为了知道每个数字应该在什么位置，必须从向量

中提取信息。用下面这种方法可以轻易做到：

通过将前述输出转换为SparseArray的方法可视化结果：

你可以看到，将问题放在一起并解决需要6-7行的代码。这个过程是一个ResourceFunction，称为SolveSudokuPuzzle，用户可以用其解决数独问题：

该函数已经非常通用，并有解决任意大小数独问题的能力。它还接收板面上出现负数。如果负数存在，则该解答器会使用该位置上的数字不能存在的假设来解决问题。

生成一个数独游戏

我们生成数独问题的策略是从一个完整面板开始。从这里开始，首先随机选择一个元素，则该元素位置上的数字将被移除。然后我们会假设在该元素上移除的数字不能出现在该元素的位置上。如果解答器在上述假设情况下得出了一个解，那么说明这个位置上的数字不是唯一，所以这个数字不能离开面板。如果解答器没有得出解，则该位置上的数字为唯一且可以被移除。

为了实施这个策略，需要有一个生成完整随机数独面板的方法。有几个可以生成完整数独面板的方法，其中之一是随机指定数独面板上对角线的数字，并允许解答器为我们生成一个数独游戏：

这会生成约三十万个可能的游戏。我们这个解答器其中一个优点是，我们还可以指定，某些数字不能出现在在某个特定位置。这可以通过将该位置上的数字设为负值实现。使用这一个特性，我们可以通过调整该过程生成超过百万个游戏：

当然，在所有可能的面板中，这依然只占一小部分，但这也是一个开始。

现在我们有一个完整面板，我们现在假设我们只想在面板上保留50个元素，则迭代代码是：

注意这个额外的情况，通过将不能出现在某些位置上的数字设为负值的方法移除这些数字。我们现在可以展示我们新鲜出炉的数独游戏了：

可以再检查一遍，这个数独游戏可以解决，并且得到的结果是和最开始的游戏一样：

注意最后解出的数独正是开始的参考数独。

为了用户使用方便，我们开发了一个名为GenerateSudokuPuzzle的ResourceFunction函数用于生成不同尺寸的数独游戏并决定需要给出多少元素：

借助于这个函数的一般特性，可以生成不同尺寸的数独面板。下面是一个4x4的面板：

下面是一个16x16的面板。生成面板的时间随着尺寸变化大幅增加，因为现在有256个长度为16的二进制向量（在9x9的情况下则有81个长度为9的向量）。以下数独游戏花了30秒生成（每次运行时间可能会不太一样）：

老实说，我还没有勇气来解这个数独。我希望你们能尝试解一解这种超大尺寸的数独！

决定难度

数独爱好者可能会问接下来的问题：“之前那个游戏的难度是多少？”这个问题需要有技巧地回答，但是我认为答案会很主观。然而，我们可以通过判断面板上有多少位置的元素在三条规则的规定下是唯一的并逐渐填写面板中空缺的位置知道没有唯一的元素存在的方法，尝试为生成游戏的困难等级从1-10进行打分，1为非常简单，10为非常困难。

所以，对于一个提供了40%的初始元素的游戏，难度系数会是：

在可以生成的所有谜题中，你可以通过指定显示元素的数量为零，来让这个游戏生成器返回其能生成的难度系数最大的谜题。当然，这个目标肯定达不到，所以生成器会返回可以唯一解出的最佳谜题。

当然，每次运行会产生不同的数字和谜题。下例就是生成器返回的一个困难谜题：

求解杀手数独游戏

杀手数独游戏是原始游戏版本的变种。它遵守原始游戏的三条规则，但是不同于原始游戏会在特定位置给出数字的方式，玩家面对的游戏面板像下图所示：

每个颜色组都成为一个“区（cage）”，每个区中都提供了一个数字。这个数字表示的是这个区中所有数字之和。比如，左上角区的数字为26，由四个方格组成。意思是这四个方格中的数字之和必须等于26。

在我们函数的框架下，这件事很容易完成。使用LinearOptimization求解杀手数独的难点在于将每个二进制向量

与另一个包含了在该位置上数字的变量

相关联。可以通过对数独解答器现有的约束条件增加下列约束条件组：

这是一个名为SolveKillerSudokuPuzzle的ResourceFunction，可以合并体现额外的约束条件并解答给定的谜题。

生成杀手数独游戏面板

当然，还是需要一个生成杀手数独面板的方法。我的方法是生成随机类似俄罗斯方块的样式，然后使用MorphologicalComponents来提取不同的方块（我很乐意听到读者们还有自己创新的方法来生成杀手数独谜题）。我描述的方法正是一个名为GenerateKillerSudokuPuzzle的ResourceFunction所运行的那样，允许我们生成杀手数独谜题的必要信息：

可通过使用DisplayKillerSudokuPuzzle函数帮助可视化该谜题：

我必须指出，生成杀手数独谜题实际上比生成传统数独谜题更加简单和便宜，因为不需要移除任何元素。这个谜题是从以下参考数独面板中生成的：

你可以通过对区内的数字进行加和手动检查这个谜题。我们现在可以解决这个杀手数独谜题了：

在实验过程中，我发现有时候整数优化问题会在几秒内解决，有时候可能要花半分钟。所以很难预测下一个问题需要多久可以解决。下面就特定情况给出了一个结果：

我也注意到有时候解出的谜题和参考数独面板不匹配。这一点，我认为，是完全没有问题的。以我的经验来看，区的尺寸越大，解答器获取可行解和数字的结果就越灵活，所以，有移动的可能性。另一方面，对于尺寸较小的区，解答谜题的过程就会越严格。

其他优化工具

我带你们简略地了解了一下优化的世界，尤其是（混合）整数优化，以及如何使用优化框架解决一些有趣的问题。在LinearOptimization的文档页面你可以找到很多关于QuadradicOptimization、SecondOrderConeOptimization、SemidefiniteOptimization和ConicOptimization的应用范例。

在创造你自己的杀手数独游戏的过程中你肯定会感受到乐趣。我最开始是因为尝试解决网上找到的一个困难等级的数独游戏，在对着草稿纸大呼小叫了一个小时之后，我意识到用电脑解决可能会更简单，所以我才写了这篇文章。你可以在评论区随心所欲地分享你的最佳谜题，或加入 Wolfram 社区来与大家分享吧。