吴方法在求解数独问题中的应用

The Application of Wu’s Method of Characteristic Set in Solving Sudoku Problem

摘要: 吴方法是计算机代数中的一种重要方法，主要通过求解吴特征列来达到对多项式方程组进行消元求解的目的，多项式的不可约特征序列则是在吴特征列的基础上进行因子分解得到的三角列集合，从而得到相应的零点分解，进而达到求解多项式零点的目的。本文以四宫数独为例，类比图论染色问题对数独问题进行建模，给出了一种用多项式组表示数独问题的方法，用数学软件Singular求解了该多项式组的不可约特征序列，并得到了一些相关的结论。

Abstract: Wu’s method is a crucial method in computer algebra. It achieves the elimination purpose by cal-culating the Wu’s characteristic sets. The irreducible characteristic series is a set of triangular sets obtained by factoring the Wu’s characteristic sets, which can provide the zero decomposition of the polynomial equations. In this paper, the Sudoku is modeled by analogy with graph coloring problem, and a method to express Sudoku with polynomial equations is given. Taking Shidoku as an example, we compute the irreducible characteristic series of its polynomial equations and some conclusions are listed.

1. 引言

数独作为一种富有逻辑性的数字填充游戏，具有非常好的益智效果，而且它在数学上也有着很长的历史，它最早起源于18世纪，以瑞士的数学家欧拉等人研究的拉丁方阵为开端；19世纪80年代之后，在美国得到进一步发展；于1984年被引入日本并且迅速流行起来；2004年，数独游戏登上英国泰晤士报，随后广为流传；数独在2007年被引入中国大陆之后也得到了良好的发展，许多数学学者也对数独问题进行了更深的思考，并给出了一些解决数独问题的数学模型和解法。

目前求解数独的方法主要分为两类，一类是以人的逻辑为依据，通过观察比较来寻找数独的解；另一种则是基于计算机回溯法的暴力解法。为了方便叙述和计算，本文以 $4\times 4$ 的数独问题为例，根据数独问题的特点，通过建立多项式方程组将求解数独问题转化为求解多项式方程组零点的问题，我们将用不可约特征序列的方法求解多项式方程组。不可约特征序列是由王东明在吴特征列的基础上进一步通过因子分解而得到的三角系统，以多项式的零点集为主要关注点，给出原多项式方程组的解的结构。

2. 数独问题的多项式表示

四宫数独是一般九宫数独问题的简化版本，要求在 $4\times 4$ 的16个格位内分别填入 $\left\{1,2,3,4\right\}$ 四个数字中的一个，使得每行、每列、每个宫内的数字都不相同。用多项式方程组表示数独问题的方法有很多种，此处我们主要介绍一种与图论中染色问题相似的一种方法 [1] 。我们将待填数的格位看作是图中待染色的点，需要填的 $\left\{1,2,3,4\right\}$ 四个数字看作是四种不同的颜色，每行、每列、每宫内不能填相同数字的格位则看作是不能染相同颜色的点，它们之间由边相连。这样，我们就可以用类似图论染色问题中构建多项式的方式建立多项式方程组来描述数独问题了。

Figure 1. Shidoku puzzle without clues

图1. 无提示数的四宫数独问题

用多项式方程组表示无提示数四宫数独问题的步骤如下：

1) 如上图1设出16个变量 $x_1,x_2,\cdots ,x_{16}$，分别表示16个格位，用有限域 ${\mathbb{F}}_{11}$ 中的四个元素 $\left\{1,2,3,4\right\}$ 分别表示要填的四个数字(注：选择在有限域 ${\mathbb{F}}_{11}$ 中进行计算，是因为我们所应用的计算软件Singular分别用 $\left\{-\frac{p-1}{2},-1,0,1,\cdots ,\frac{p-1}{2}\right\}$ 这11个元素来表示 ${\mathbb{F}}_p$ (其中p为素数)中个元素， $p=11$ 是使 ${\mathbb{F}}_p$ 包含数字1，2，3，4的最小的素数了，为了读写方便，所以选择在 ${\mathbb{F}}_{11}$ 中进行计算。)；

2) 写出表示格位取值的16个多项式： $F\left(x_i\right)={\displaystyle {\prod }_{n=1}^4\left(x_i-n\right)},\left(i=1,2,\cdots ,16\right)$；

3) 若格位 $x_i$ 和格位 $x_j$ 处不能填相同的数字，则用 $G\left(x_i,x_j\right):=\frac{F\left(x_i\right)-F\left(x_j\right)}{x_i-x_j}$ 来表示，这样的方程共有56个，分别用来表示每行、每列、每宫内的格位中所填数字不能相同。

这样我们就用包含72个多项式的方程组将四宫数独问题表示了出来。对于有提示数的数独问题，若格位 $x_i$ 处有提示数n，则用多项式 $f\left(x_i\right)=x_i-n$ 替换掉原来的 $F\left(x_i\right)={\displaystyle {\prod }_{n=1}^4\left(x_i-n\right)}$ 即可。

3. 吴特征列与不可约特征序列

本节主要介绍一些有关吴特征列和不可约特征列的基础知识，其详细内容可以阅读文献 [2] 和文献 [3] 的相关部分。

设 $\mathcal{K}$ 是一个数域，F是多项式环 $\mathcal{K}\left[x_1,\cdots ,x_n\right]$ (默认变元序为 $x_1<\cdots <x_n$ )中的一个多项式。我们定义，多项式F中所含的变元的最大下标 $cls\left(F\right):=\text{max}\left\{k:\mathrm{deg}\left(F,x_k\right)>0,1\le k\le n\right\}$ 为F的类，如果 $F\in \mathcal{K}$ 则规定 $cls\left(F\right)=0$。当 $cls\left(F\right)>0$ 时，把 $lv\left(F\right):=x_{cls\left(F\right)}$ 称为是F的导元；把 $ldeg\left(F\right):=deg\left(F,lv\left(F\right)\right)$ 称为F的导次数；把 $ini\left(F\right):=lc\left(F,lv\left(F\right)\right)$ 称为F的初式。

定理3.1

设 $F,G$ 是多项式环 $\mathcal{R}\left[x\right]$ 中的任意两个多项式， $x_k$ 是一个变元，而且有 $l=deg\left(G,x_k\right)$， $m=deg\left(F,x_k\right)$。如果 $l>0$，那么就存在多项式 $Q,R\in \mathcal{R}\left[x\right]$ 和整数 $0\le s\le m-l+1$ 使得 $lc{\left(G,x_k\right)}^s\cdot F=Q\cdot G+R$，而且有 $deg\left(R,x_k\right)<l$。如果s固定，那么 $Q,R$ 是唯一确定的。证明参见 [3] 。

定义3.2

如果定理3.1中的条件可以被满足，那么称表达式 $lc{\left(G,x_k\right)}^s\cdot F=Q\cdot G+R$ 为F关于G的伪余公式，称Q为F对G关于 $x_k$ 的伪商，记为 $pquo\left(F,G,x_k\right)$，称R为F对G关于 $x_k$ 的伪余式，记为 $prem\left(F,G,x_k\right)$。

定义3.3

如果 $\mathcal{K}\left[x\right]$ 中的有限非空有序集合 $\mathcal{T}=\left[T_1,\cdots ,T_r\right]$ 满足条件 $0<cls\left(T_1\right)<\cdots <cls\left(T_r\right)$，那么我们就将 $\left[T_1,\cdots ,T_r\right]$ 称为是一个三角列，为了方便起见，我们也把空集合称为是一个三角列。

对于多项式集合 $\mathcal{T}\subseteq \mathcal{K}\left[x\right]\backslash \mathcal{K}$，记 $lv\left(\mathcal{T}\right):=\left\{lv\left(T\right):T\in \mathcal{T}\right\}$， $ini\left(\mathcal{T}\right):=\left\{ini\left(T\right):T\in \mathcal{T}\right\}$。对于 $x_i\in lv\left(\mathcal{T}\right)$，记 ${\mathcal{T}}_{x_i}:=\left\{T\in \mathcal{T}:lv\left(T\right)=x_i\right\}$， ${\mathcal{T}}_{<x_i}:=\left\{T\in \mathcal{T}:lv\left(T\right)<x_i\right\}$，类似地定义 ${\mathcal{T}}_{>x_i}$， ${\mathcal{T}}_{\le x_i}$， ${\mathcal{T}}_{\ge x_i}$。

设 $P,Q\in \mathcal{K}\left[x\right]$ 是非零多项式。并且有 $Q\notin \mathcal{K}$。如果 $deg\left(P,lv\left(Q\right)\right)<ldeg\left(Q\right)$。那么就称P对Q是约化的。设多项式集合 $\mathcal{T}\subseteq \mathcal{K}\left[x\right]$ 是一个三角列， $P\in \mathcal{K}\left[x\right]$ 是任意多项式，如果P对 $\mathcal{T}$ 中的每一个多项式T都是约化的，那么称P对 $\mathcal{T}$ 是约化的。

定义3.4

如果多项式集合 $\mathcal{T}\subseteq \mathcal{K}\left[x\right]$ 只包含一个非零常数，则称 $\mathcal{T}$ 为平凡升列；否则，若 $\mathcal{T}=\left[T_1,\cdots ,T_r\right]$ 是三角列，且对于任意 $1\le j<i\le r$， $T_i$ 对于所有 $T_j$ 都是约化的，就称 $\mathcal{T}$ 为非平凡升列。

定义3.5

在三角列 $\mathcal{T}\subseteq \mathcal{K}\left[x\right]$ 中，若对于任意 $x_i\in lv\left(\mathcal{T}\right)$ 都有 $prem\left(ini\left(F\right),{\mathcal{T}}_{<x_i}\right)\ne 0$ 成立，其中 $F\in {\mathcal{T}}_{x_i}$，则称 $\mathcal{T}$ 是良好三角列。

定义3.6

设 $\mathcal{P}\subseteq \mathcal{K}\left[x\right]$ 是非空多项式集合，任意包含于由 $\mathcal{P}$ 所生成的理想的升列都称为 $\mathcal{P}$ 的中间列。

定义3.7

设 $\mathcal{P}\subseteq \mathcal{K}\left[x\right]$ 是非空多项式集合，如果存在升列 $\mathcal{C}$ 使得 $\mathcal{C}\subseteq \langle \mathcal{P}\rangle$ 而且 $prem\left(\mathcal{P},\mathcal{C}\right)=\left\{0\right\}$，那么就称 $\mathcal{C}$ 为 $\mathcal{P}$ 的特征列。

命题3.8 (特征列的零点关系)

设非平凡升列 $\mathcal{C}=\left[C_1,\cdots ,C_r\right]$ 是多项式集合 $\mathcal{P}\subseteq \mathcal{K}\left[x\right]$ 的特征列，设 ${\mathcal{P}}_i:=\mathcal{P}\cup \left\{ini\left(C_i\right)\right\},\left(i=1,\cdots ,r\right)$， $\mathcal{I}:=ini\left(\mathcal{C}\right)$。有如下的零点关系： $Z\left(\mathcal{C}/\mathcal{I}\right)\subseteq Z\left(\mathcal{P}\right)\subseteq Z\left(\mathcal{C}\right)$， $Z\left(\mathcal{C}/\mathcal{I}\right)=Z\left(\mathcal{P}/\mathcal{I}\right)$， $Z\left(\mathcal{P}\right)=Z\left(\mathcal{C}/\mathcal{I}\right)\cup {\displaystyle {\cup }_{i=1}^{r}Z\left({\mathcal{P}}_i\right)}$。

定义 $\mathcal{K}\left[x\right]$ 中多项式P的秩为 $lv{\left(P\right)}^{ldeg\left(P\right)}$，如果 $cls\left(P\right)>0$；否则的话定义P的秩为P，记为 $rank\left(P\right)$。

定义3.9

设 $P,Q\in \mathcal{K}\left[x\right]$ 是非零多项式，如果满足下列三个条件之一，则称P的秩低于Q的秩，记为 $P\prec Q$ ：1) $P\in \mathcal{K}$，但是 $Q\notin \mathcal{K}$；2) $P,Q\notin \mathcal{K}$，而且 $cls\left(P\right)<cls\left(Q\right)$；3) $P,Q\notin \mathcal{K}$， $cls\left(P\right)=cls\left(Q\right)$，而且 $ldeg\left(P\right)<ldeg\left(Q\right)$。如果 $Q\prec P$，则称P的秩高于Q的秩，记为 $P\succ Q$。如果 $P\prec Q$ 和 $P\succ Q$ 都不成立，那么称P和Q具有相同的秩，记为 $P~Q$。把 $P\prec Q$ 或 $P~Q$ 简记为 $P\precsim Q$。

定义3.10

设 $\mathcal{T}=\left[T_1,\cdots ,T_r\right]$ 和 $\mathcal{S}=\left[S_1,\cdots ,S_t\right]$ 是多项式环 $\mathcal{K}\left[x\right]$ 中的两个非平凡升列，称 $\mathcal{T}$ 的秩低于 $\mathcal{S}$ 的秩，记为 $\mathcal{T}\prec \mathcal{S}$，如果满足下列条件之一：1) 存在 $i\le \text{min}\left(r,t\right)$，使得对于每个 $j<i$ 都有 $T_j~S_j$，但是 $T_i\prec S_i$；

2) $r>t$，而且对于每个 $j\le t$ 都有 $T_j~S_j$ 成立。如果 $\mathcal{S}\prec \mathcal{T}$，那么称 $\mathcal{T}$ 的秩高于 $\mathcal{S}$ 的秩，记为 $\mathcal{T}\succ \mathcal{S}$。如果 $\mathcal{T}\succ \mathcal{S}$ 和 $\mathcal{T}\prec \mathcal{S}$ 都不成立，那么称 $\mathcal{T}$ 和 $\mathcal{S}$ 具有相同的秩，记为 $\mathcal{T}~\mathcal{S}$。将 $\mathcal{T}\prec \mathcal{S}$ 或者 $\mathcal{T}~\mathcal{S}$ 简记为 $\mathcal{T}\precsim \mathcal{S}$。并规定平凡升列的秩总是低于非平凡升列的秩。

引理3.11

设 $\mathcal{T}=\left[T_1,\cdots ,T_r\right]$ 和 $\mathcal{S}=\left[S_1,\cdots ,S_t\right]$ 是多项式环 $\mathcal{K}\left[x\right]$ 中的两个升列，那么我们有下列结论成立：(1) $\mathcal{T}~\mathcal{S}$ 当且仅当 $r=t$ 而且对于所有 $j\le t$，都有 $T_j~S_j$ 成立；(2)设 $P\in \mathcal{K}\left[x\right]\backslash \mathcal{K}$，并记 $v=lv\left(P\right)$，如果 $\mathcal{T}$ 是非平凡升列，并且P对于 $\mathcal{T}$ 是约化的，那么 $\left({\mathcal{T}}_{<v}\cup \left\{P\right\}\right)\prec \mathcal{T}$。

定义3.12

对于多项式环 $\mathcal{K}\left[x\right]$ 中任意非空有限的多项式集合 $\mathcal{P}$，设 $\Phi$ 是由所有含于 $\mathcal{P}$ 的升列组成的集合。因为一个非零多项式可以构成一个升列，所以 $\Phi$ 非空。我们将 $\Phi$ 的任意极小升列(关于 $\prec$ 秩最低的升列)称为是 $\mathcal{P}$ 的基列。

$\mathcal{P}$ 的基列可以通过如下步骤找出：设 ${\mathcal{F}}_1:=\mathcal{P}$，令 $B_1$ 是 ${\mathcal{F}}_1$ 中秩最低的多项式。如果 $B_1$ 是非零常数，那么 $\left[B_1\right]$ 就是 $\mathcal{P}$ 的一个基列。否则，令 ${\mathcal{F}}_2:=\left\{F\in {\mathcal{F}}_1\backslash B_1:F对B_1是约化的\right\}$。如果 ${\mathcal{F}}_2=\varnothing$，那么 $\left[B_1\right]$ 就是

$\mathcal{P}$ 的一个基列。否则，设 $B_2$ 是 ${\mathcal{F}}_2$ 中秩最低的多项式。易知 $B_1\prec B_2$。可以类似地依次构造 ${\mathcal{F}}_3,{\mathcal{F}}_4,\cdots$，因为 $\mathcal{P}$ 是非空有限的多项式集合，而基列或是一个非零常数，或是作为一个三角列最多含有n个多项式，所以上述构造过程必定会在有限步之后终止，最后我们就可以得到 $\mathcal{P}$ 的一个基列。

$\mathcal{P}$ 的吴特征列的算法如下：1) 设 $\mathcal{F}:=\mathcal{P}$， $\mathcal{R}:=\mathcal{P}$；2) 如果集合 $\mathcal{R}$ 非空，则求取 $\mathcal{R}$ 的一个基列 $\mathcal{C}$；3) 若 $\mathcal{C}$ 中含有 $\mathcal{K}$ 中的元素，则另 $\mathcal{R}:=\varnothing$，否则另 $\mathcal{R}:=\left\{prem\left(F,\mathcal{C}\right):F\in \mathcal{F}\backslash \mathcal{C}\right\}\backslash \left\{0\right\}$；4) 另 $\mathcal{F}:=\mathcal{P}\cup \mathcal{C}\cup \mathcal{R}$，并返回第2)步，直到集合 $\mathcal{R}$ 为空集为止。最后一次求出的基列 $\mathcal{C}$ 即为多项式组 $\mathcal{P}$ 的吴特征列。该算法的终止性及正确性可参见 [3] 。

设非平凡升列 $\mathcal{C}=\left[C_1,\cdots ,C_r\right]$ 是多项式集合 $\mathcal{P}\subseteq \mathcal{K}\left[x\right]$ 的特征列，现在回到特征列的零点关系，即 $Z\left(\mathcal{P}\right)=Z\left(\mathcal{C}/\mathcal{I}\right)\cup {\displaystyle {\cup }_{i=1}^{r}Z\left({\mathcal{P}}_i\right)}$，显然有 $Z\left({\mathcal{P}}_i\cup \mathcal{C}\right)=Z\left({\mathcal{P}}_i\right)$，于是，计算每一个 ${\mathcal{P}}_i\cup \mathcal{C}$ 的特征列，并如此进行下去，由于 ${\mathcal{P}}_i\cup \mathcal{C}$ 的基列的秩低于 $\mathcal{C}$ 的秩，所以经过有限多步之后可以得到如下的零点分解 $Z\left(\mathcal{P}\right)={\displaystyle {\cup }_{i=1}^{e}Z\left({\mathcal{C}}_i/{\mathcal{I}}_i\right)}$，其中 ${\mathcal{C}}_i$ 都是升列， ${\mathcal{I}}_i=ini\left({\mathcal{C}}_i\right)$。

定义3.15

设 $\Psi$ 为 $\mathcal{K}\left[x\right]$ 中由升列 ${\mathcal{C}}_1,\cdots ,{\mathcal{C}}_e$ 构成的有限集合， $\mathcal{P}$ 为 $\mathcal{K}\left[x\right]$ 中的多项式集合，如果有零点分解 $Z\left(\mathcal{P}\right)={\displaystyle {\cup }_{i=1}^{e}Z\left({\mathcal{C}}_i/{\mathcal{I}}_i\right)}$ 成立，且 $prem\left(\mathcal{P},{\mathcal{C}}_i\right)=\left\{0\right\}$ 对于所有的i成立，则称 $\Psi$ 为 $\mathcal{P}$ 的特征序列。 $\Psi =\varnothing$ 即 $e=0$ 也即 $Z\left(\mathcal{P}\right)=\varnothing$。

设 $\mathcal{T}\subseteq \mathcal{K}\left[x\right]$ 是一个三角列，则 $\mathcal{T}$ 可以写成如下形式：

$\mathcal{T}=\left[T_1\left(x_1,\cdots ,x_{p_1}\right),T_2\left(x_1,\cdots ,x_{p_1},\cdots ,x_{p_2}\right),\cdots ,T_r\left(x_1,\cdots ,x_{p_1},\cdots ,x_{p_2},\cdots ,x_{p_r}\right)\right]$ ,

其中 $p_i=cls\left(T_i\right)$， $x_{p_i}=lv\left(T_i\right)$， $i=1,2,\cdots ,r$， $0<p_1<p_2<\cdots <p_r\le p_n$。进一步地，将导元 $x_{p_1},x_{p_2},\cdots ,x_{p_r}$ 重新命名为 $y_1,\cdots ,y_r$，其它变元记为 $u_1,\cdots ,u_d$ 或简记为 $u$，则 $\mathcal{T}$ 就可以写作 $\mathcal{T}=\left[T_1\left(u,y_1\right),T_2\left(u,y_1,y_2\right),\cdots ,T_r\left(u,y_1,y_2,\cdots ,y_r\right)\right]$。设 ${\mathcal{K}}_0$ 是 $\mathcal{K}$ 添加 $u_1,\cdots ,u_d$ 后得到的超越扩域 $\mathcal{K}\left(u\right)=\mathcal{K}\left(u_1,\cdots ,u_d\right)$，如下对三角列 $\mathcal{T}$ 的不可约性和一般零点作归纳定义。

定义3.16

设 $\mathcal{T}\subseteq \mathcal{K}\left[x\right]$ 是良好三角列，若 $\mathcal{T}$ 只含一个多项式 $T_1\left(u,y_1\right)$，且 $T_1$ 是 ${\mathcal{K}}_0\left[y_1\right]$ 中的不可约多项式，则称 $\mathcal{T}$ 是不可约的。此时，设 ${\eta }_1$ 为 $T_1$ 在 ${\mathcal{K}}_0$ 的某一代数扩域中的零点，则称 $\left(u,{\eta }_1\right)$ 为 $\mathcal{T}$ 的一个一般零点。假设含任意 $k\left(k<r\right)$ 个多项式的良好三角列之不可约性和一般零点已经定义，那么称良好三角列 $\mathcal{T}=\left[T_1\left(u,y_1\right),T_2\left(u,y_1,y_2\right),\cdots ,T_r\left(u,y_1,y_2,\cdots ,y_r\right)\right]$ 是不可约的，如果 $\left[T_1\left(u,y_1\right),T_2\left(u,y_1,y_2\right),\cdots ,T_{r-1}\left(u,y_1,y_2,\cdots ,y_{r-1}\right)\right]$ 是不可约的，且以 $\left(u,{\eta }_1,\cdots ,{\eta }_{r-1}\right)$ 为一般零点，且多项式 $T_r\left(u,y_1,y_2,\cdots ,y_r\right)$ 在 ${\mathcal{K}}_{r-1}\left[y_r\right]$ 中不可约。其中 ${\mathcal{K}}_{r-1}={\mathcal{K}}_0\left({\eta }_1,\cdots ,{\eta }_{r-1}\right)$ 是将 ${\eta }_1,\cdots ,{\eta }_{r-1}$ 添入 ${\mathcal{K}}_0$ 得到的代数扩域。此时设 ${\eta }_r$ 为 $T_r\left(u,y_1,y_2,\cdots ,y_r\right)$ 在 ${\mathcal{K}}_{r-1}$ 的某个代数扩域中的零点，称 $\left(u,{\eta }_1,\cdots ,{\eta }_r\right)$ 为 $\mathcal{T}$ 的一个一般零点。

定理3.17零点分解定理

设多项式组 $\mathcal{P}\subseteq \mathcal{K}\left[x\right]$ 有中间列 $\mathcal{T}=\left[T_1,T_2,\cdots ,T_r\right]$，其中 $cls\left(T_1\right)>0$， $I_i=ini\left(T_i\right)$， $1\le i\le r$。如果 $\mathcal{T}$ 可约，则存在k，使得 $T_k$ 可以分解为不可约多项式 $F_1,F_2,\cdots ,F_t$ ——即存在非负整数 $s_1,s_2,\cdots ,s_{k-1}$ 和 $\mathcal{K}\left[u,y_1,y_2,\cdots ,y_k\right]$ 中的多项式 $Q_1,Q_2,\cdots ,Q_{k-1}$ 以及 $\mathcal{K}\left[u,y_1,y_2,\cdots ,y_{k-1}\right]$ 中的多项式D，使得 $I_1^{s_1}\cdots I_{k-1}^{s_{k-1}}\left(F_1\cdots F_t-D\cdot T_k\right)={\displaystyle {\sum }_{i=1}^{k-1}{Q}_i\cdot T_i}$ 成立——于是有下面的零点分解成立： $Z\left(\mathcal{P}\right)={\displaystyle {\cup }_{i=1}^{k-1}Z\left({\mathcal{P}}_i\right)}\cup {\displaystyle {\cup }_{j=1}^{t}Z\left({\mathcal{Q}}_j\right)}$，其中 ${\mathcal{P}}_i=\mathcal{P}\cup \left\{I_i\right\}\left(1\le i\le k-1\right)$， ${\mathcal{Q}}_j=\mathcal{P}\cup \left\{F_j\right\}\left(1\le j\le t\right)$。

仿照求解特征序列的过程，可以对每个 $\mathcal{P}\cup \left\{I_i\right\}$ 以及 $\mathcal{P}\cup \left\{F_j\right\}$ 进一步求其零点分解，最终会得到形如 $Z\left(\mathcal{P}\right)={\displaystyle {\cup }_{i=1}^{e}Z\left({\mathcal{C}}_i/{\mathcal{I}}_i\right)}$ 的零点分解，其中 ${\mathcal{I}}_i=ini\left({\mathcal{C}}_i\right)$ 且每个 ${\mathcal{C}}_i$ 都不可约。设 $\text{Ψ}$ 是一个特征序列或三角

序列，若 $\text{Ψ}$ 中的升列都不可约，则称 $\text{Ψ}$ 是不可约的。求解任意非空多项式方程组的不可约特征序列主要是在求解吴特征列算法的基础上用因子分解方法将吴特征列中可约的多项式在相应的代数扩域上进行因式分解，从而得到不可约特征序列。详细算法以及相应的因子分解算法详见文献 [2] 的4.4节及9.4节。

4. 应用及结论

对于有唯一解的数独问题，我们可根据本文第二部分给出的建模方法，用有限域 ${\mathbb{F}}_{11}$ 上的72个多项式进行表示，即表示16个格位取值的多项式 $F\left(x_1\right),\cdots ,F\left(x_{16}\right)$ 以及56个表示每行、每列、每宫内的格位所填数字不同的多项式 $G\left(x_1,x_2\right),\cdots ,G\left(x_{15},x_{16}\right)$，这72个多相似构成一个多项式组，之后我们求解出该多项式组的不可约特征序列，即可解出该多项式组的零点集，也就解出了相应的数独问题。直观地，我们有如下结论：

命题4.1 数独问题有解当且仅当多项式方程组的不可约三角分解不为{1}。

命题4.2 数独问题有唯一的解当且仅当多项式方程组的不可约三角分解只包含一个三角列 $\left\{x_i-a_i|i=1,2,\cdots ,16\right\}$，其中 $a_i\in \left\{1,2,3,4\right\}$。此时数独问题的解即第i个格位处填数字 $a_i$。

命题4.3 如果多项式方程组的不可约三角分解包含多个三角列，则原数独问题有多个解。此时，每个三角列都具有形式 $\left\{x_i-a_i|i=1,2,\cdots ,16\right\}$ (其中 $a_i\in \left\{1,2,3,4\right\}$ )，分别代表数独的一种解，不可约特征序列种包含多少个三角列，原数独问题便有多少种解。

在求解多项式组的不可约特征序列时，我们主要用到的计算软件为Singular，在Singular中有内置函数“ $char\text{\_}series\left(I\right)$ ”，可以直接求解出多项式组I在给定数域中的不可约特征序列，关于软件Singular的更多内容见 [4] 。

例4.1 以下图2四宫数独为例：

Figure 2. Shidoku puzzle

图2. 一个四宫数独问题

我们可以用多项式方程组来表示它。首先用 $F\left(x_1\right),\cdots ,F\left(x_{16}\right)$ 表示16个格位的取值，然后用 $G\left(x_1,x_2\right),\cdots ,G\left(x_{15},x_{16}\right)$ (共56个)表示每行、每列、每宫内的格位取值不能相同，最后，由于本题中给定了第2、8、11、13个格位的提示数分别为4、1、3、2，所以分别用多项式 $x_2-4,x_8-1,x_{11}-3,x_{13}-2$ 替换掉 $F\left(x_2\right),F\left(x_8\right),F\left(x_{11}\right),F\left(x_{13}\right)$，这样我们就用72个多项式将该数独问题描述出来了。之后求解由这72个多项式方程构成的多项式方程组的不可约特征列，结果为： $\left\{\left[x_1-1,x_2-4,x_3-2,x_4-3,x_5-3,x_6-2,x_7-4,x_8-1,x_9-4,x_{10}-1,x_{11}-3,x_{12}-2,x_{13}-2,x_{14}-3,x_{15}-1,x_{16}-4\right]\right\}$，该不可约特征序列只包含有一个三角列，即原多项式组只有唯一解，也即原四宫数独只有唯一解，其解即如该三角列所示。

例4.2 若是如图3所示的一个没有任何提示数的空白四宫数独问题，

Figure 3. Shidoku puzzle without clues

图3. 无提示数的四宫数独问题

我们构建的多项式组即为 $\left\{F\left(x_1\right),\cdots ,F\left(x_{16}\right),G\left(x_1,x_2\right),\cdots ,G\left(x_{15},x_{16}\right)\right\}$，由72个多项式组成，计算其不可约特征序列，结果为由288个三角列构成的不可约特征列，其中每一个三角列都形如例4.1中的结果，分别表示数独问题的一种可能的解，也就是说，空白的四宫数独问题一共有288种不同的解，这与我们运用组合数学进行求解的结果是一致的。

此外，在文献 [5] 中，Stephen Lucas等人用求解多项式组的Groebner基的方法处理了由类似的多项式方程组所生成的理想，同样得到了无提示数的四宫数独问题有288种解的结论。对于一般的九宫数独问题来说，也可以用类似的多项式来表示，Gago-Vargas等人在文献 [6] 中对九宫数独问题进行了详细的讨论，并用Groebner基成功求解出有大量提示数的数独问题。值得指出的一点是，想要将无提示数的九宫数独问题表示出来需要用到81个变量和891个多项式，不论对于Groebner基来说还是吴特征列方法来说都是非常巨大的计算量，远远超出了一般个人电脑的计算能力，不过通过这个方法，我们可以用多项式将数独问题的结构进行表示，吴方法的应用也为数独问题提供了一种多项式组解法的新思路。