揭秘数独 (2025)

# 解锁数独的秘密 - Chalkdust 来源: https://chalkdustmagazine.com/features/unlocking-sudokus-secrets/ 隐私与 Cookie: 本网站使用 Cookie。继续使用本网站即表示您同意其使用。 如需了解更多信息，包括如何控制 Cookie，请参阅此处:Cookie Policy (https://automattic.com/cookies/) 数独长期以来以其逻辑挑战和令人上瘾的特性吸引了全世界的谜题爱好者。虽然它看起来只是一个简单的数字游戏，但其表面之下隐藏着与数学领域的迷人联系。图论和抽象代数在揭示数独的复杂性方面都发挥着关键作用。数独谜题由一个 $9 \times 9$ 的网格组成，划分为九个称为区域的 $3 \times 3$ 子网格。目标是用 1 到 9 的数字填充网格，确保每行、每列和每个区域都恰好包含每个数字一次。 ## 一个顶点着色问题 在图论中，图是一种数学结构，由通过边连接的顶点（或节点）集合组成。图论是一个充满数学问题的领域，有着众多著名的引人深思的问题的历史。其中最著名的问题之一是*顶点着色问题*：给定一个无向图 $G = (V, E)$，其中 $V$ 表示顶点集合，$E$ 表示边集合，能否找到一种给 $V$ 中每个顶点分配颜色的方案，使得任意两个相邻顶点（由边连接）不具有相同的颜色？ [](https://i0.wp.com/chalkdustmagazine.com/wp-content/uploads/2025/03/sudoku-img0.png?ssl=1) 虽然数独看起来像是一个数字网格，但我们可以通过图论的视角来看待它。有趣的是，我们可以将数独谜题表示为一个图，其中数独网格中的 81 个单元格中的每一个对应于图中的一个顶点。我们用有序对 $(x, y)$ 标记顶点，$x$ 和 $y$ 为 1 到 9 的整数。然后，当且仅当满足以下任一条件时，我们用一条边连接两个不同的顶点 $(x, y)$ 和 $(x', y')$： - $x = x'$（两个单元格在同一行）， - $y = y'$（同一列），或 - $\displaystyle\left\lceil \frac{x}{3} \right\rceil = \left\lceil \frac{x'}{3} \right\rceil$ 且 $\displaystyle\left\lceil \frac{y}{3} \right\rceil = \left\lceil \frac{y'}{3} \right\rceil$（同一 $3\times3$ 区域）。 因此，数独盘左上角的区域连接方式如下： [](https://i0.wp.com/chalkdustmagazine.com/wp-content/uploads/2025/03/sudoku-img1.png?ssl=1) 然后我们提出顶点着色问题：*我们的数独图是否存在 9-着色？* 也就是说，我们能否用不超过 9 种颜色对图中的每个顶点进行着色，使得由边连接的顶点颜色不同？ [](https://i0.wp.com/chalkdustmagazine.com/wp-content/uploads/2025/03/sudoku-img2.png?ssl=1) 事实证明，这个问题等价于：原始数独盘是否存在解？通过应用顶点着色算法，如*贪心算法*和/或*回溯法*，我们可以系统地给顶点（单元格）分配颜色（数字），从而找到任何数独盘的有效解（只要存在解）。 ## 贪心算法与回溯法 贪心算法的目的是产生图的顶点着色。该算法通过迭代选择一个未着色的顶点并分配给其最小的不与其相邻节点冲突的颜色来给图的顶点着色。这意味着在数独中，贪心算法接收一个数独盘，并系统地给单元格（顶点）分配数字（颜色），确保行、列或区域内不会出现冲突。回溯法是一种系统搜索算法，通过做出选择并在导致矛盾或死胡同时撤销选择来探索解空间。我们将贪心算法与回溯法相结合，特别是在贪心算法无法找到解时。在数独中，这将涉及用数字填充单元格，测试其有效性，如果检测到矛盾，则“回溯”到 previous 状态以探索其他选择，直到找到有效解或穷尽所有可能性。在数独中结合贪心算法和回溯法的程序如下： 1. 从初始盘开始，选择第一个未着色的单元格。 2. 给选定的单元格分配尽可能小的数字。 3. 移动到下一个未着色的单元格并分配下一个最小的数字。 4. 继续此过程，从左到右、从上到下移动，给每个未着色的单元格分配最小的有效数字。 5. 如果出现冲突，表明放置无效，则回溯到上一个单元格并选择下一个可用的数字。 6. 重复此过程，直到整个网格填满或无法放置有效数字为止。 ## 算法实战 **步骤 1：** 假设我们的初始盘如下所示。我们选择第一个未着色的单元格： [](https://i0.wp.com/chalkdustmagazine.com/wp-content/uploads/2025/03/sudoku-img3.png?ssl=1) **步骤 2–4：** 贪心算法。注意，$(1, 7)$ 处填入的是 8 而不是 4、5 或 6，因为虽然 4 是最低的可用的数字，但 8 是最低的可用*有效*数字。 [](https://i0.wp.com/chalkdustmagazine.com/wp-content/uploads/2025/03/sudoku-img4.png?ssl=1) **步骤 5.1：** 冲突。$(1,8)$ 剩余的唯一可用数字已经存在于第 8 列中。 [](https://i0.wp.com/chalkdustmagazine.com/wp-content/uploads/2025/03/sudoku-img5.png?ssl=1) **步骤 5.2–6：** 回溯。返回单元格 $(1,7)$。输入下一个最低的有效数字，即 9。恢复贪心算法。 [](https://i0.wp.com/chalkdustmagazine.com/wp-content/uploads/2025/03/sudoku-img6.png?ssl=1) 通过在所有行中继续执行此相同算法，我们可以找到数独盘的解！ 其他研究者似乎也对我产生了好奇心，并从图论中了解了更多关于数独的知识——Joshua Cooper 和 Anna Kirkpatrick 将最小集与最小公平谜题联系起来，而 Michael Haythorpe 将哈密顿循环与不同大小的数独谜题联系起来。 图论是从数学上解锁数独谜题的一种方法。但数独实际上只是在满足一系列约束条件下解决谜题。这听起来像是代数可以帮助我们的事情。确实可以！代数几何在数独方面有着同样美妙的应用。 ## Gröbner 基 如果我们能将数独问题写为多项式系统，那么求解该系统就能让我们完成谜题。求解联立方程组似乎是高斯-约当消元法的机会，但该方法仅适用于线性系统，而我们稍后将看到我们的系统不是线性的。此外，我们需要解为整数 1–9。更通用的方法在于*Gröbner 基*。 多项式系统的 Gröbner 基是一个新的多项式系统，具有与原系统相同的解，但更容易求解。例如，系统 $\begin{align*} x+y-3 &= 0,\\ xy-2&=0 \end{align*}$ 是耦合的，因为两个方程都涉及两个变量。然而，计算该系统的 Gröbner 基得到 $\begin{align*} y^2-3y+2 &= 0,\\ x+y-3&=0, \end{align*}$ 其中第一个方程仅涉及 $y$。我们可以先解这个方程，然后代入求 $x$，使系统更容易求解。为了理解 Gröbner 基如何工作，我们需要学习一些抽象代数术语。*多项式环*是具有一定数量变量的多项式集合。出于我们的目的，多项式的系数来自有理数域 $\mathbb{Q}$。*理想*是来自环 $R$ 的元素子集 $I$，它形成加法群并具有属性 $\[x \in R \text{ 且 } y\in I \implies xy \in I \text{ 且 }yx \in I。\]$ 理想可以由一组多项式生成，就像向量空间可以由一组向量张成一样。例如，如果 \[ I= \{af+bg : a,b \in R\}, \] 那么 $f$ 和 $g$ 生成 $I$，我们可以写 \[I= \langle f,g \rangle。\] *项序*是一种选择元素放置顺序的方法。我们将使用的项序是字典序项序，缩写为 $\operatorname{Lex}$。这就是你在字典中期望的顺序。例如，如果我们有关变量 $x$，$y$ 和 $z$，则将变量排序为 \[x>y>z。\] 当我们连接变量时，我们查看每个元素中的第一个变量并进行比较，然后是第二个变量，依此类推。例如， $\begin{align*} \operatorname{Lex}(xy) > \operatorname{Lex}(yz), \\ \text{且 }\operatorname{Lex}(x^2) > \operatorname{Lex}(xy)。 \end{align*}$ 给定一个项序，多项式 $f$ 的*首项*是序中最大的项，记为 $\operatorname{lt}(f)$。给定多项式环中的任何多项式集合 $S$，我们可以定义 $S$ 的首项理想为由 $S$ 中多项式的首项生成的理想 $\operatorname{lt}(S)$。即， \[\operatorname{lt}(S)= \langle \operatorname{lt}(f) : f \in S \rangle。\] 请注意，多项式集合的首项理想并不总是等于由该多项式集合生成的理想的首项理想。对于 Gröbner 基，我们使用度逆字典序。这意味着如果 $S=\{x,x+1\}$，$\operatorname{lt}(S)= \langle x\rangle$，但如果 $I= \langle x,x+1\rangle$，则 \[x+1-x= 1 \in I,\] 所以 $\operatorname{lt}(I)=\langle 1 \rangle =R$。 当 $\operatorname{lt}(S)=\operatorname{lt}(I)$，其中 $I=\langle S \rangle$ 时，我们说 $S$ 是理想 $I$ 的 Gröbner 基。换句话说，如果且仅当 $\operatorname{lt}(G)= \operatorname{lt}(I)$ 时，非零多项式集合 \[G=\{g_1,g_2,\dots,g_t \} \subset I\] 被称为 $I$ 的 Gröbner 基。 Gröbner 基之所以好，是因为它们简化了问题。例如，如果 $G$ 是理想 $I$ 的 Gröbner 基，那么我们可以使用简单的约简来确定给定的多项式 $f$ 是否在理想 $I$ 中。 Gröbner 基理论中的一个著名定理解释说，Gröbner 基将给定系统置于三角形式。例如，如果 $G=\{g_1,\dots,g_s\}$ 是变量 $x_1, \dots x_n$（$n\leq s$）中的 Gröbner 基，则该定理指出我们可以对多项式 $g_1,\dots,g_s$ 进行排序，使得 $g_1$ 仅涉及最小变量 $x_1$，$g_2$ 仅涉及 $x_1$ 和 $x_2$ 且首项仅涉及 $x_2$，依此类推。这使得通过快速简单的代入求解成为可能。 [](https://i0.wp.com/chalkdustmagazine.com/wp-content/uploads/2025/03/Bruno_Buchberger.jpg?ssl=1) Bruno Buchberger 在他 1965 年的博士论文中引入了 Gröbner 基，并以他的导师 Wolfgang Gröbner 命名 一种称为*Buchberger 算法*的过程计算给定理想和项序的 Gröbner 基。该算法使用多元除法算法和最小公倍数。该算法还保证给定理想和项序存在 Gröbner 基。 ## 数独中的 Gröbner 基 这对数独问题很有用。我们可以： 1. 创建多项式方程系统来表示我们的数独问题 2. 使用 Buchberger 算法计算由我们系统中的多项式生成的理想的 Gröbner 基 3. 如果谜题有唯一解，Gröbner 基将由 81 个线性多项式组成，从中我们可以读出数独谜题的解 我们可以将数独规则中给出的约束表示为多项式方程系统。我们引入 81 个变量 $x_0,\dots,x_{80}$，每个单元格一个。严格来说，我们现在处理的是多项式环 $\mathbb{Q}[x_0,\dots,x_{80}]$。我们希望将数独的条件编码为某个子域 $F \subset \mathbb{Q}[x_0,\dots,x_{80}]$ 中的一组多项式。单元格只能取 1 到 9 的整数值，因此我们可以为所有 $i=0,\dots,80$ 定义以下多项式： \[(x_i-1)(x_i-2)\cdots(x_i-9)=0。\] 接下来，我们定义多项式来表示每个数字在每列、每行和每个区域中只能使用一次的条件。这可以通过定义所有列/行和每个区域的和应为 45 且乘积应为 $9! = \text{362,880}$ 来完成。有了这些条件，我们就没有重复的数字。因此，如果 $\{x_{k_1},\dots,x_{k_9}\}$ 都在同一行或列中， \[\sum_{n=1}^{9} x_{k_n} = 45 \quad\text{且}\quad \prod_{n=1}^{9} x_{k_n} = \text{362,880}。\] 最后，由于网格中的一些单元格 $x_j$ 已经填有数字 $a_j$，我们为每个这些单元格定义新多项式， \[x_j-a_j=0。\] 这些多项式给出了 135 个方程的系统，加上每个已知单元格一个。我们可以通过应用 Buchberger 算法计算 Gröbner 基来解决这个系统，并从中读出初始网格的解。 ## 一个例子：四宫格数独 正如我们所见，算法相当长。因此，我们不使用数独盘通过工作示例，而是使用*四宫格数独*盘。四宫格数独是数独的一种变体，使用 $4 \times 4$ 网格，划分为四个 $2 \times 2$ 区域。 引入 16 个变量 $x_0,\dots,x_{15}$ 来表示 16 个单元格。每个单元格只能取值 $1$，$2$，$3$ 或 $4$，因此对于 $i=0,1,\dots,15$， \[(x_i-1)(x_i-2)(x_i-3)(x_i-4)=0。\] 与之前类似，列、行或区域中所有数字的和与积必须分别为 $1+2+3+4=10$ 和 $1\times 2 \times 3 \times 4=24$。有了这些条件，我们就没有重复的数字。 让 $\{x_i,x_j,x_k,x_l\}$ 表示构成一行、一列或 $2 \times 2$ 区域的单元格集合，所以 $\begin{align*} x_i+x_j+x_k+x_l-10&=0 \\ \text{且}\quad x_i x_j x_k x_l-24&=0。 \end{align*}$ 这总共给出了 40 个多项式方程。 然后我们添加任何已给出的值。假设我们有下面的盘，带有给定的变量赋值： [](https://i0.wp.com/chalkdustmagazine.com/wp-content/uploads/2025/03/sudoku-img7.png?ssl=1)[](https://i0.wp.com/chalkdustmagazine.com/wp-content/uploads/2025/03/sudoku-img8.png?ssl=1) 因此我们需要添加方程 $\begin{align*} a-1=0, \quad f-2=0, \\ i-2=0, \quad k-3=0, \\ p-4=0.\hspace{8mm} \end{align*}$ 剩下的就是将我们的方程交给计算机代数包——Matlab 有*gbasis*函数——以执行 Buchberger 算法并计算该系统的 Gröbner 基。 这样做，它返回： $\begin{align*} 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。 \end{align*}$ 这个基由线性多项式系统组成，从中我们可以轻松读出四宫格数独盘的解： [](https://i0.wp.com/chalkdustmagazine.com/wp-content/uploads/2025/03/sudoku-img9.png?ssl=1) 数独与图论和抽象代数领域紧密交织。我们在课程中学到的算法提供了宝贵的见解和策略，可以应用于征服数独谜题。因此，下次你拿起数独谜题时，请记住其表面之下隐藏的这张美妙的图和多项式方程层。