解锁数独的秘密：Graph Theory和Abstract Algebra的应用

A magazine for the mathematically curious Order Issue 21 now!

Menu

Skip to content MENUMENU

Issue 21

解锁数独的秘密

Sara Logsdon 借助图论和抽象代数来解决谜题 Sara Logsdon 17 March 2025

数独以其逻辑挑战和令人着迷的特性，长期以来吸引着全世界的谜题爱好者。虽然它可能看起来像一个简单的数字游戏，但在表面之下，隐藏着与数学领域一个迷人的联系。图论和抽象代数都在揭示数独的复杂性中起着至关重要的作用。数独谜题由一个9×9的网格组成，该网格被分为九个3×3的子网格，称为区域。目标是用1到9的数字填充网格，确保每行、每列和每个区域都恰好包含每个数字一次。

一个顶点着色问题

在图论中，图是一个数学结构，它包含一组顶点（或节点），这些顶点通过边连接。图论领域充满了数学问题，并且有着悠久的历史。其中最著名的难题之一就是_顶点着色问题_：给定一个无向图G=(V,E)，其中V代表顶点集合，E代表边集合，能否找到一种为V中每个顶点分配颜色的方案，并满足任何两个相邻顶点（由一条边连接）都不同颜色的条件？

虽然数独可能看起来像一个数字网格，但我们可以通过图论的视角来观察它。有趣的是，我们可以将一个数独谜题表示为一个图，其中数独网格中的每个81个单元格对应于图中的一个顶点。我们用有序对 (x,y) 标记顶点，其中x和y是从1到9的整数。然后，我们当且仅当以下任何一个条件成立时，通过一条边连接两个不同的顶点(x,y) 和 (x′,y′)：

• x=x′ (两个单元格在同一行)，
• y=y′ (同一列)，或
• ⌈x3⌉=⌈x′3⌉ 且 ⌈y3⌉=⌈y′3⌉ (相同的 3×3 区域)。

因此，数独棋盘的左上角区域将像这样连接：

然后，我们提出顶点着色问题：是否存在我们数独图的 9-着色？ 也就是说，我们能否使用不超过 9 种颜色为图中的每个顶点着色，并确保没有通过边连接的顶点最终具有相同的颜色？

事实证明，这个问题等同于：是否存在原始数独棋盘的解？通过应用顶点着色算法，例如_贪婪算法_和/或_回溯_，我们可以系统地为顶点（单元格）分配颜色（数字），以找到任何数独棋盘的有效解，只要存在一个解。

贪婪算法和回溯

贪婪算法的目的是产生图的顶点着色。该算法通过迭代选择未着色的顶点并为其分配最小的可能颜色（不与其相邻节点冲突）来为图的顶点分配颜色。这意味着在数独中，贪婪算法会获取一个数独棋盘，并系统地将数字（颜色）分配给单元格（顶点），从而确保在行、列或区域内不会出现冲突。回溯是一种系统的搜索算法，它通过做出选择并在导致矛盾或死胡同时撤消它们来探索解决方案空间。我们将把贪婪算法与回溯相结合，尤其是在贪婪算法无法找到解决方案时。在数独中，这将涉及用数字填充单元格，测试其有效性，并且如果检测到矛盾，则“回溯”到之前的状态以探索替代选择，直到找到有效解决方案或所有可能性都已用尽。在数独中组合贪婪算法和回溯的过程如下：

1. 从初始棋盘开始并选择第一个未着色的单元格。
2. 将最小的可能数字分配给所选单元格。
3. 移动到下一个未着色的单元格并分配下一个最小的数字。
4. 继续此过程，从左到右、从上到下移动，并将最小的有效数字分配给每个未着色的单元格。
5. 如果出现冲突，表明放置无效，则回溯到上一个单元格并选择下一个可用数字。
6. 重复该过程，直到整个网格被填满或直到无法放置有效数字。

算法实战

步骤 1： 假设我们的初始棋盘如下所示。我们选择第一个未着色的单元格：

步骤 2–4： 贪婪算法。请注意，在 (1,7) 中输入的是 8 而不是 4、5 或 6，因为虽然 4 是最低的可用数字，但 8 是最低的可用_有效_数字。

步骤 5.1： 冲突。 (1,8) 的唯一剩余可用数字已经存在于第 8 列中。

步骤 5.2–6： 回溯。 返回到单元格 (1,7)。 输入下一个最低的可用有效数字 9。 恢复贪婪算法。

通过在所有行中继续执行相同的算法，我们可以找到数独棋盘的解决方案！

其他研究人员似乎也对与我同样的好奇心所吸引，并且通过图论了解了更多关于数独的信息——Joshua Cooper 和 Anna Kirkpatrick 将最小集合与最小公平谜题联系起来，Michael Haythorpe 将 Hamiltonian 循环与不同大小的数独谜题联系起来。

图论是从数学上解锁数独谜题的一种方法。但数独实际上只是解决一个受多个约束的谜题。这听起来像是代数可以帮助我们解决的问题。事实也的确如此！代数几何拥有一个类似的美妙的应用于数独。

Gröbner Bases

如果我们可以将数独问题写成一个多项式系统，那么解决该系统将使我们能够完成这个谜题。解决联立方程可能看起来像是进行 Gauss-Jordan 消元的机会，但这种方法仅适用于线性系统，我们很快就会看到我们的系统不是线性的。此外，我们要求我们的解决方案是整数 1-9。一种更通用的方法在于 Gröbner bases。

多项式系统的 Gröbner basis 是一个新的多项式系统，它与原始系统具有相同的解，但更容易求解。例如，系统 x+y−3=0,xy−2=0 是耦合的，因为两个方程都涉及两个变量。然而，计算此系统的 Gröbner basis 会产生 y2−3y+2=0,x+y−3=0, 其中第一个方程只涉及 y。我们可以求解第一个方程，然后代入来找到 x，从而使系统更容易求解。为了理解 Gröbner bases 的工作原理，我们需要学习一些抽象代数术语。_多项式环_是具有一定数量变量的多项式的集合。就我们的目的而言，多项式的系数将来自有理数域 QQ。_理想_是环 RR 中元素的子集 II，它形成一个加法群，并且具有属性 x∈R 且 y∈I⟹xy∈I 且 yx∈I。理想可以由一组多项式生成，就像向量空间可以由一组向量张成一样。例如，如果 I={af+bg:a,b∈R}，则 f 和 g 生成 II，我们可以写成 I=⟨f,g⟩。_项排序_是一种选择元素放置顺序的方法。我们将在此处使用的项排序是字典项排序，缩写为 Lex。这是您在字典中期望看到的排序。例如，如果我们有变量 x、y 和 z，那么我们将变量排序为 x>y>z。当我们连接变量时，我们查看每个元素的第一个变量并进行比较，然后是第二个，依此类推。例如，Lex(xy)>Lex(yz), 并且 Lex(x2)>Lex(xy)。给定一个项排序，多项式 f 的_首项_是该排序中最大的项，将表示为 lt(f)。给定多项式环中的任何多项式集合 SS，我们可以将 SS 的首项理想定义为由 S 中多项式的首项生成的理想 lt(S)。也就是说，lt(S)=⟨lt(f):f∈S⟩。请注意，多项式集合的首项理想并不总是等于该集合生成理想的首项理想。对于 Gröbner bases，我们使用逆字典度排序。这意味着如果 S={x,x+1}，lt(S)=⟨x⟩，但如果 I=⟨x,x+1⟩，则 x+1−x=1∈I，因此 lt(I)=⟨1⟩=R。

当 lt(S)=lt(I) 时，其中 I=⟨S⟩，我们说 SS 是理想 I 的 Gröbner basis。换句话说，一组非零多项式 G=g1,g2,…,gt⊂I 称为理想 II 的 Gröbner basis，当且仅当 lt(G)=lt(I)。

Gröbner bases 很好，因为它们简化了问题。例如，如果 GG 是理想 II 的 Gröbner basis，那么我们可以使用简单约简来确定给定的多项式 f 是否在理想 II 中。

Gröbner basis 理论中一个著名的定理解释说，Gröbner basis 将给定的系统置于三角形式。例如，如果 G={g1,…,gs} 是变量 x1,…xn (n≤s) 中的 Gröbner basis，该定理指出我们可以对多项式 g1,…,gs 进行排序，以便 g1 仅涉及最小的变量 x1，g2 仅涉及 x1 和 x2，并且其首项仅涉及 x2，依此类推。这使得可以通过快速、简单的替换来获得解。

Bruno Buchberger 在他 1965 年的博士论文中介绍了 Gröbner bases，并以他的导师 Wolfgang Gröbner 的名字命名。

一个称为 Buchberger 算法 的过程计算给定理想和项排序的 Gröbner basis。该算法使用多元除法算法和最小公倍数。该算法还保证了给定理想和项排序的 Gröbner basis 的存在。

数独中的 Gröbner Basis

这对于数独问题很有用。我们可以：

1. 创建一个多项式方程组来表示我们的数独问题
2. 使用 Buchberger 算法计算由我们系统中多项式生成的理想的 Gröbner basis
3. 如果谜题有一个唯一的解，那么 Gröbner basis 将由 81 个线性多项式组成，我们可以从中读出我们数独谜题的解

我们可以将数独规则中给出的约束表示为一个多项式方程组。我们引入 81 个变量，x0,…,x80，每个变量对应于数独中的一个单元格。形式上，我们现在正在处理多项式环 Q[x0,…,x80]。我们希望将数独的条件编码为某些子域 F⊂Q[x0,…,x80] 中的一组多项式。单元格只能取 1 到 9 的整数值，因此我们可以为所有 i=0,…,80 定义以下多项式： (xi−1)(xi−2)⋯(xi−9)=0。

接下来，我们定义多项式来表示每个数字在每列、每行和每个区域中只能使用一次的条件。这可以通过定义所有列/行的总和以及每个区域的总和应为 45，并且乘积应为 9!=362,880 来完成。有了这些条件，我们就没有重复的数字。因此，如果 {xk1,…,xk9} 都在同一行或同一列中，则 9∑n=1xkn=45 并且 9∏n=1xkn=362,880。最后，由于网格中的一些单元格 xj 已经填充了数字 aj，我们为每个这些单元格定义新的多项式 xj−aj=0。这些多项式给出了一个包含 135 个方程的系统，加上每个已知单元格的一个方程。我们可以通过应用 Buchberger 算法来计算 Gröbner basis 来求解该系统，并从中读出初始网格的解。

一个例子：shidoku

正如我们所见，该算法相当长。因此，我们不会使用数独棋盘来完成一个例子，而是将使用一个 shidoku 棋盘。Shidoku 是数独的一个变体，它使用一个 4×4 网格，分为四个 2×2 区域。

引入 16 个变量 x0,…,x15 来表示 16 个单元格。每个单元格只能取值 1、2、3 或 4，因此对于 i=0,1,…,15，(xi−1)(xi−2)(xi−3)(xi−4)=0。与之前类似，一列、一行或一个区域中的所有数字的总和和乘积必须分别为 1+2+3+4=10 和 1×2×3×4=24。有了这些条件，我们就没有重复的数字。

设 {xi,xj,xk,xl} 表示构成一行、一列或一个 2×2 区域的一组单元格，则 xi+xj+xk+xl−10=0 并且 xixjxkxl−24=0。

这给了我们总共 40 个多项式方程。

然后，我们添加任何已经给定的值。让我们假设我们有下面的棋盘，其中给定了变量赋值：

因此，我们需要添加方程 a−1=0,f−2=0,i−2=0,k−3=0,p−4=0。剩下的就是将我们的方程交给计算机代数软件包——Matlab 具有 gbasis 函数——以便执行 Buchberger 算法并计算该系统的 Gröbner basis。

这样做会返回： a−1=0,b−3=0,c−4=0,d−2=0,e−4=0,f−2=0,g−1=0,h−3=0,i−2=0,j−4=0,k−3=0,l−1=0,m−3=0,n−1=0,o−2=0,p−4=0。该basis由一个线性多项式系统组成，我们可以很容易地从中读出shidoku棋盘的解：

数独与图论和抽象代数的领域紧密交织。我们在课程中学习的算法提供了宝贵的见解和策略，可以应用于征服数独谜题。因此，下次您拿起一个数独谜题时，请记住隐藏在其表面之下的美丽的图和多项式方程。

Sara Logsdon Sara 是佐治亚大学的一名本科生，对代数很感兴趣。在数学之外，她喜欢徒步旅行和玩棋盘游戏（她最喜欢的是 Splendor）。

All articles by Sara

Read also

Post navigation

← Skimming potatoes What a load of noise: A beginner’s mathematical guide to AI diffusion models →

Privacy & Cookies: This site uses cookies. By continuing to use this website, you agree to their use. To find out more, including how to control cookies, see here: Cookie Policy