用 Wolfram 的方法探索象棋数独挑战

美国数学协会的每一期《数学视野》（https://www.maa.org/press/periodicals/math-horizons）都会向读者展示一些难题，2021 年 4 月的一期包括由新泽西州韦恩市威廉帕特森大学的数学教授大卫·纳辛 (David Nacin, https://wpconnect.wpunj.edu/directories/faculty/default.cfm?user=nacind) 发起的“Knightdoku”挑战（http://digitaleditions.sheridan.com/publication/?m=53548&i=704790&p=2&ver=html5）。

在这个谜题中，基于象棋骑士棋子描述了一个简单的类似数独的问题。9×9 网格中的每个单元格都可能包含一个骑士棋子。初始棋盘配置定义了一组骑士棋子的位置，且特定数量的骑士棋子必须出现在解答的邻域。骑士棋子的邻域指的是骑士棋子可以通过一个 L 形国际象棋走法到达的一组单元格。

除了骑士的初始位置之外，正确答案必须遵守类似数独的约束。具体来说，每一行、每一列和每个 3×3 块必须正好有三个骑士。

这个谜题包括两个需要解决的棋盘配置：一个热身板和一个常规板——也就是说，更难的版本！这是热身板：

© 美国数学协会，2021。保留所有权利。

下面是常规板：

© 美国数学协会，2021。保留所有权利。

对我来说，挑战不仅仅是解决 Nacin 的 Knightdoku 谜题（https://doi.org/10.1080/10724117.2021.1881366），而是使用 Wolfram 语言（https://www.wolfram.com/language/）来做到这一点，它提供了多种解决数独谜题（https://resources.wolframcloud.com/FunctionRepository/search/?i=sudoku）的方法。

解决基于国际象棋骑士棋子的数独问题

像数独这样的游戏使用布尔约束求解器相对简单。本质上，可将问题归结为一组代表可能电路板配置的逻辑变量之间的关系。

例如，如果我们有两个单元格，我们想让一个为真，另一个为假，我们可以创建四个变量：两个用于第一个单元格（cell1false，cell1true），两个用于第二个单元格（cell2false，cell2true）。有效的配置将满足约束（cell1false 和 cell2true）或（cell1true 和 cell2false）。该逻辑表达式 ((cell1false&&cell2true)||(cell1true&&cell2false)) 可以交给可满足性问题求解器以确定是否存在满足逻辑约束的配置。

辅助函数

首先，我们必须创建一些辅助函数来从列表中形成合取和析取，这将在以后构建我们的逻辑表达式时有用：

棋盘配置

初始棋盘配置是一个三元组列表：{x,y,n} 其中 {x,y} 是棋盘上的位置（使用移动一格的索引），n 是在 {x, y}处有一个骑士棋子的答案中包含的邻域的骑士棋子数量。邻域被定义为可以通过有效的骑士棋子移动到达的单元格。

首先，我们为热身板创建一个基本配置：

然后是常规板配置：

为方便起见，我们还会创建一些关联，以便稍后在绘制求解器结果时查找这些初始标记：

定义逻辑变量

我们需要通过逻辑变量对棋盘的状态进行编码，因此我们为每个单元格的可能状态定义了一组布尔值（有骑士棋子，无骑士棋子）。我们使用约定 s[[i,j,1]] 表示 {i,j} 有一个棋子，而 s[[i,j,2]] 表示没有棋子：

我们还将创建一个关联映射坐标，可映射到该坐标的两个逻辑变量（这在调试和查看约束条件时最有用）：

有必要建立第一个逻辑约束来保证单元格被标记或未标记。一个既不是被标记也不是未标记，或者既标记又未标记的单元格是无效的，因此我们将这类单元格排除在外：

我们为约束条件编写的大部分代码都是这样的。在这种情况下，最里面的表设置了每个单元格的约束条件。然后，我们将前面创建的函数 AndList 映射到表上，从表的每一行的列中形成一个连接，然后再应用一次 AndList，将这些行连接成一个大的逻辑表达式。

邻域约束条件

初始配置中，我们需要考虑每个骑士棋子可以到达的单元格，且不超出棋盘的边界。我们可以编写一个简单的函数来枚举单元格 {x,y} 的邻域的坐标：

为给定的位置和数量的预期骑士棋子的邻域生成所有可能的有效值分配。我们通过获取一组邻域棋子并将每个值与 1 或 2 相关联来实现这一点。1 和 2 分配的顺序是通过计算1 和 2 序列的所有排列来实现的，这些序列包含适当数量的 1 和 2 的预期的邻域棋子数。也包括标记为 (s[[x,y,1]]) 的邻域中心的骑士棋子：

将这些组合起来的效果类似于我们上面所做的事情，不同的是在表达式中添加了 Or（https://reference.wolfram.com/language/ref/Or.html）。具体来说，我们需要对每个邻域的邻居应用And(https://reference.wolfram.com/language/ref/And.html)，并用Or连接每个可能的邻域。最后，我们将所有这些 And/Or 表达式与所有初始骑士棋子的标记结合：

棋盘约束条件

我们还需要添加类似于数独的通用棋盘约束条件：每行、每列和 3×3 大小的方块中有最多三枚骑士棋子。它们遵循与上述相同的模式：我们为每一行、每一列和每个方块创建标记/未标记的所有排列，并使用 And 和 Or 运算符将其结合起来。

添加一个每行最多可以设置三个棋子的约束条件：

同样，为每列设置最多三个棋子的约束：

同样也为3×3方块设置约束条件：

解方程组

求解棋盘谜题的准备工作已经完成。

棋盘配置#1

我们可以在一组逻辑变量上使用可满足性问题求解器来求解方程组：

对于可视化部分，我们重新计算结果以确定分配给与棋盘相同形状的每个逻辑变量的内容。我们用

加一个上标代表原始骑士棋子及其必须拥有的邻居数量。求解器计算填充的骑士棋子表示为

：

棋盘配置#2

我们可以将相同的技巧应用于 Nacin 提供的第二块更难的板：

如果您对将 Wolfram 语言应用于数独游戏的其他示例感兴趣，可以查看 Wolfram 社区成员撰写的“将数独作为整数编程问题求解”（https://community.wolfram.com/groups/-/m/t/974303）和“使用递归和 FindInstance 求解数独”（https://community.wolfram.com/groups/-/m/t/1050618）等帖子。您还可以在David Nacin的谜题博客 Quadrata（https://quadratablog.blogspot.com/） 中找到更多的有趣谜题。

Matthew Sottile 是一名计算机科学家，在劳伦斯利弗莫尔国家实验室（Lawrence Livermore National Laboratory）的应用科学计算中心工作。他的研究领域包括编程语言、编译器和形式化方法。Sottile 自 1995 年以来一直是 Wolfram Mathematica 的活跃用户，常将其用于生成艺术、解决难题以及研究重写和证明方程组等。

欢迎访问 Wolfram Community（https://community.wolfram.com/） 或 Wolfram Function Repository （https://resources.wolframcloud.com/FunctionRepository/）开启您自己的计算探索！