前言 看抽象代数的时候突然想到，群的 Cayley 表和数独一样，都要求每行（列）中的元素互异。那么能不能按照群的规则（即结合律）出一道变种数独题呢？于是简单试了一下。
规则：
题面是一个 \(10 \times 10\) 数表（行和列从 \(0\) 开始计数），元素为 \(0 \sim 9\) 的整数；第 \(0\) 行和第 \(0\) 列的值已经给出 与普通数独相同，每行、每列的元素不能重复；注意没有九宫格的条件 若 \(i\) 行 \(j\) 列的值为 \(x\) ，\(j\) 行 \(k\) 列的值为 \(y\) ，则 \(i\) 行 \(y\) 列和 \(x\) 行 \(k\) 列的值相同 TLDR：补全一个以 \(0\) 为单位元的 \(10\) 阶群的乘法表。（提示：\(10\) 阶群只有 \(\mathrm{Z}_{10}\) 和 \(\mathrm{D}_{10}\) 两种）为什么这一规则对应群
把第 \(i\) 行第 \(j\) 列的值记为 \(i \otimes j\) . 根据第一条规则，\(\otimes\) 是 \(\{0,1,\dots,9\}\) 上的一个二元运算，值域也是 \(\{0,1,\dots,9\}\) . 因此 \(\otimes\) 满足封闭性。
第 \(0\) 行和第 \(0\) 列的值表明，对任意 \(x\) 都有 \(0 \otimes x = x \otimes 0 = x\) ，因此 \(0\) 是单位元。
若 \(i \otimes j = x,\ j \otimes k = y\) ，由第三条规则可得
\[ i \otimes (j \otimes k) = i \otimes y = x \otimes k = (i \otimes j) \otimes k, \]
因此 \(\otimes\) 满足结合律。
根据第二条规则，每一行、每一列的 \(10\) 个数都互不相同；又因为它们都落在 \(\{0,1,\dots,9\}\) 中，因此每一行、每一列都是这 \(10\) 个数的一个排列。
于是对任意 \(a\) ，存在 \(b,c\) 使得 \(a \otimes b = 0,\ c \otimes a = 0\) . 再由结合律可得
\[ c = c \otimes 0 = c \otimes (a \otimes b) = (c \otimes a) \otimes b = 0 \otimes b = b, \]
因此 \(b\) 同时是 \(a\) 的左逆元和右逆元。
综上所述，这三条规则恰好定义了一个以 \(0\) 为单位元的 \(10\) 阶群；反过来，任何 \(10\) 阶群的 Cayley 表也都满足这三条规则。
题目 题 1：（表中横、竖线仅作美化排版用途，无实际含义）
\[ \begin{array} {r|rrr|rrr|rrr} 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\ \hline 1 & 0 & & & & & & & & \\ 2 & & & 1 & & & & & & \\ 3 & & 4 & & & & & & & \\ \hline 4 & & & & & & & & & \\ 5 & & & & 2 & & & & & \\ 6 & & & & & & & & & \\ \hline 7 & & & & & & 3 & & & \\ 8 & & & & & 9 & & & & \\ 9 & & & & & & & & & \\ \end{array} \] 解析
表中 \(2 \otimes 3 \ne 3 \otimes 2\) ，说明这个群一定是 \(\mathrm{D}_{10}\) . 这里先明确一下记号：\(\mathrm{D}_{10} = \langle r, s \mid r^5 = s^2 = e,\ sr = r^{-1}s \rangle\) .
解决题目的关键在于理解 \(\mathrm{D}_{10}\) 的自同构。 \(\operatorname{Aut}(\mathrm{D}_{10})\) 在 \(\{r,r^2,r^3,r^4\}\) 与 \(\{s,rs,r^2s,r^3s,r^4s\}\) 上分别传递作用；等价地，任取一个非单位旋转元 \(r^n\ (n=1,2,3,4)\) 和一个反射元 \(r^m s\ (m=0,1,2,3,4)\) ，都存在 \(\mathrm{D}_{10}\) 的自同构 \(\varphi\) ，使得 \(\varphi(r^n)=r,\ \varphi(r^m s)=s\) .
\(0\) 是单位元，而 \(1 \otimes 1 = 0\) ，说明 \(1\) 是“s 型”元素。再由上面的自同构性质可知，若本题有解，则一定可以通过适当的自同构让 \(1\) 对应群中元素 \(s\) （下文简写为 \(1 \sim s\) ）。因此不妨设 \(1 \sim s\) .
\(2 \otimes 3 = 1\) ，说明 \(2\) 和 \(3\) 一个是“r 型”，一个是“s 型”。注意到 \(5 \otimes (3 \otimes 2) = 2\) ，因此 \(5\) 和 \(3\) 互为逆元。“s 型”元素的逆元都是它本身，因此 \(3\) 是“r 型”，\(2\) 是“s 型”。
不妨设 \(3 \sim r\) ，则 \(2 \sim rs\) ，\(5 \sim r^4\) . \(3 \otimes 2 = 4\) ，说明 \(4 \sim r^2 s\) .
这是目前已确定的元素：
\(e\) \(s\) \(rs\) \(r\) \(r^2 s\) \(r^4\)
还剩下 \(r^2,\, r^3,\, r^3 s,\, r^4s\) 尚未确定。
\(7 \otimes 6 = 3\) ，说明 \(6\) 和 \(7\) 要么都是“r 型”，要么都是“s 型”。而 \(r^2 \cdot r^3 = r^3 \cdot r^2 = e\) ，说明 \(6\) 和 \(7\) 只能都是“s 型”，因此 \(6 \sim r^3 s\) ，\(7 \sim r^4 s\) .
\(8 \otimes 5 = 9\) ，而 \(8\) 和 \(9\) 只能在 \(r^2,\, r^3\) 中取值，因此 \(8 \sim r^3\) ，\(9 \sim r^2\) .
完整的对应关系如下：
\(e\) \(s\) \(rs\) \(r\) \(r^2 s\) \(r^4\) \(r^3 s\) \(r^4 s\) \(r^3\) \(r^2\)
据此把乘法表补全即可。
答案：
\[ \begin{array} {r|rrr|rrr|rrr} 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\ \hline 1 & 0 & 5 & 7 & 8 & 2 & 9 & 3 & 4 & 6 \\ 2 & 3 & 0 & 1 & 5 & 4 & 8 & 9 & 6 & 7 \\ 3 & 2 & 4 & 9 & 6 & 0 & 7 & 1 & 5 & 8 \\ \hline 4 & 9 & 3 & 2 & 0 & 6 & 5 & 8 & 7 & 1 \\ 5 & 7 & 1 & 0 & 2 & 8 & 4 & 6 & 9 & 3 \\ 6 & 8 & 9 & 4 & 3 & 7 & 0 & 5 & 1 & 2 \\ \hline 7 & 5 & 8 & 6 & 9 & 1 & 3 & 0 & 2 & 4 \\ 8 & 6 & 7 & 5 & 1 & 9 & 2 & 4 & 3 & 0 \\ 9 & 4 & 6 & 8 & 7 & 3 & 1 & 2 & 0 & 5 \\ \end{array} \]
题 2：
\[ \begin{array} {r|rrr|rrr|rrr} 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\ \hline 1 & & & & & & & & & \\ 2 & & & & & & & & & \\ 3 & & & 0 & & & & & & 4 \\ \hline 4 & & & & & & & & 0 & \\ 5 & & 7 & & & & & & & \\ 6 & & & & & & & & & \\ \hline 7 & & & & & & & & & \\ 8 & & & & & 2 & & & & \\ 9 & & & & 1 & & & & & \\ \end{array} \] 解析
用和题 1 类似的方法，可以发现 \(\mathrm{D}_{10}\) 是不行的。因此，这个群只能是 \(\mathrm{Z}_{10}\) . 记 \(\mathrm{Z}_{10} = \langle g \mid g^{10} = e \rangle\) .
\(3 \otimes 3 = 0\) ，说明 \(3\) 的阶为 \(2\) ，因此 \(3 \sim g^5\) .
考虑从 \(4\) 出发往后推。但我们还不确定 \(4\) 的阶是 \(5\) 还是 \(10\) . 先假设 \(4\) 的阶是 \(5\) ，那么不妨设 \(4 \sim g^2\) .
\(3 \otimes 9 = 4\) ，说明 \(9 \sim g^7\) . \(4 \otimes 8 = 0\) ，说明 \(8 \sim g^8\) . \(9 \otimes 4 = 1\) ，说明 \(1 \sim g^9\) .
这是目前已确定的元素：
\(e\) \(g^9\) \(g^5\) \(g^2\) \(g^8\) \(g^7\)
还剩下 \(g,\, g^3,\, g^4,\, g^6\) 尚未确定。
还有两个条件没有用到：\(5 \otimes 2 = 7\) 和 \(8 \otimes 5 = 2\) . 对 \(8 \otimes 5 \otimes 2\) 使用结合律，得到 \(2 \otimes 2 = 8 \otimes 7\) .
这说明 \(7\) 是 \(g^4\) 或者 \(g^6\) . 若 \(7 \sim g^4\) ，则 \(2 \sim g\) 或 \(2 \sim g^6\) ；若 \(7 \sim g^6\) ，则 \(2 \sim g^2\) 或 \(2 \sim g^7\) ，矛盾。因此，\(7 \sim g^4\) .
\(5 \otimes 2 = 7\) ，若 \(2 \sim g\) ，则 \(5 \sim g^3\) ；若 \(2 \sim g^6\) ，则 \(5 \sim g^8\) ，矛盾。因此，\(2 \sim g\) ，\(5 \sim g^3\) ，\(6 \sim g^6\) .
完整的对应关系如下：
\(e\) \(g^9\) \(g\) \(g^5\) \(g^2\) \(g^3\) \(g^6\) \(g^4\) \(g^8\) \(g^7\)
据此把乘法表补全即可。
如果 \(4\) 的阶是 \(10\) ，按同样流程推导会出现矛盾，过程不再赘述。
答案：
\[ \begin{array} {r|rrr|rrr|rrr} 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\ \hline 1 & 8 & 0 & 7 & 2 & 4 & 3 & 5 & 9 & 6 \\ 2 & 0 & 4 & 6 & 5 & 7 & 9 & 3 & 1 & 8 \\ 3 & 7 & 6 & 0 & 9 & 8 & 2 & 1 & 5 & 4 \\ \hline 4 & 2 & 5 & 9 & 7 & 3 & 8 & 6 & 0 & 1 \\ 5 & 4 & 7 & 8 & 3 & 6 & 1 & 9 & 2 & 0 \\ 6 & 3 & 9 & 2 & 8 & 1 & 4 & 0 & 7 & 5 \\ \hline 7 & 5 & 3 & 1 & 6 & 9 & 0 & 8 & 4 & 2 \\ 8 & 9 & 1 & 5 & 0 & 2 & 7 & 4 & 6 & 3 \\ 9 & 6 & 8 & 4 & 1 & 0 & 5 & 2 & 3 & 7 \\ \end{array} \]
以下是作者的一些疑问：
存不存在只有 5 个已知数且有唯一解的题面？ 有没有比较有效的方法构造这类题目的 \(8 \times 8\) 版本？ 自动生成器 时隔一年多突然想起这篇烂尾博客，我惊喜地发现现在的 LLM 已经可以爆杀上文的两个疑问了。以下两节的代码全部由 GPT-5.4 生成。
首先从枚举所有合法的 Cayley 表开始。借助一些（我并不会的）抽象代数知识，可以在近似 \(O(\mathrm{output \_ size})\) 的时间复杂度内完成枚举。生成枚举结果的 GAP 程序见此 。生成 3GiB 大小的 \(12 \times 12\) Cayley 表全集需要约 5min。
\(8\) 阶群有 \(2760\) 种 Cayley 表，\(10\) 阶群有 \(108864\) 种，\(12\) 阶群有 \(21621600\) 种。对于 \(8\) 阶和 \(10\) 阶群，可以直接使用（剪枝后的）暴力搜索 找出已知数最少且有唯一解的题面。对于 \(12\) 阶群，暴力搜索已经不可行了，因此略作妥协 ：对于每类群，随机选择一个答案，二分搜索已知数的数量，随机生成题面，若连续 \(1000\) 个题面都有多解，则认为该数量的已知数不足以保证唯一解，尝试更多的已知数。
对于两种 \(10\) 阶群，最少的已知数都是 \(5\) 个：
\[ \begin{array} {r|rrr|rrr|rrr} 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\ \hline 1 & 5 & & & & & & & & \\ 2 & & 4 & & & & & & & \\ 3 & & & & 8 & & & & & \\ \hline 4 & & & & & & & & & \\ 5 & & 7 & & & & & & & \\ 6 & 3 & & & & & & & & \\ \hline 7 & & & & & & & & & \\ 8 & & & & & & & & & \\ 9 & & & & & & & & & \\ \end{array} \]
\[ \begin{array} {r|rrr|rrr|rrr} 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\ \hline 1 & 7 & & & & & & & & \\ 2 & & 8 & & & & & & & \\ 3 & 6 & & & & & & & & \\ \hline 4 & & & & & 8 & & & & \\ 5 & & & & & & 2 & & & \\ 6 & & & & & & & & & \\ \hline 7 & & & & & & & & & \\ 8 & & & & & & & & & \\ 9 & & & & & & & & & \\ \end{array} \] 8 阶群的结果
这些题目都不难，欢迎读者尝试！为减少对读者时间的浪费，我直接给出了每道题对应的群类型。
\(\mathrm{Z}_8\) :
\[ \begin{array} {rrrr|rrrr} 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 \\ 1 & & & & & & & \\ 2 & 3 & & & & & 5 & \\ 3 & & & & & & & 4 \\ \hline 4 & & & & & & & \\ 5 & & & & & 3 & & \\ 6 & & & & & & & \\ 7 & & & & & & & \\ \end{array} \]
\(\mathrm{Z}_4 \times \mathrm{Z}_2\) :
\[ \begin{array} {rrrr|rrrr} 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 \\ 1 & 0 & & & & & & \\ 2 & & & & & & & 0 \\ 3 & & & & & & & \\ \hline 4 & & & & 3 & & & \\ 5 & & & & & & & \\ 6 & & & & 2 & & & \\ 7 & & & & & & & \\ \end{array} \]
\(\mathrm{D}_8\) :
\[ \begin{array} {rrrr|rrrr} 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 \\ 1 & & & & & & & \\ 2 & & & & & & & \\ 3 & & & & & & & \\ \hline 4 & & & & & & & \\ 5 & & & & & 0 & & \\ 6 & & & & & & 3 & 2 \\ 7 & 3 & & & & & & \\ \end{array} \]
\(\mathrm{Q}_8\) :
\[ \begin{array} {rrrr|rrrr} 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 \\ 1 & & & & & & & \\ 2 & & & 5 & & & & \\ 3 & & & & & & & \\ \hline 4 & & & & 7 & 6 & & \\ 5 & & & & & 7 & & \\ 6 & & & & & & & \\ 7 & & & & & & & \\ \end{array} \]
\(\mathrm{Z}_2 \times \mathrm{Z}_2 \times \mathrm{Z}_2\) :
\[ \begin{array} {rrrr|rrrr} 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 \\ 1 & & & & & & 4 & \\ 2 & & & & & 1 & & \\ 3 & & & & 2 & & & \\ \hline 4 & & & & & & & \\ 5 & & & 6 & & & & \\ 6 & 4 & & & & & & \\ 7 & & & & & & & 0 \\ \end{array} \]
12 阶群的结果
我对这些群不熟悉，就不手算了，总之能做
\(\mathrm{Q}_{12}\) :
\[ \begin{array} {rrr|rrr|rrr|rrr} 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & \mathrm{A} & \mathrm{B} \\ 1 & & 4 & & & & & & & & & \\ 2 & & & & & & & & & & & \\ \hline 3 & & & & & & & \mathrm{B} & & & & \\ 4 & & & & & & & & & & & \\ 5 & & & & & & & 1 & & & & \\ \hline 6 & & & & & & & & & & & \\ 7 & & & 6 & & & 8 & & & & & \\ 8 & & & & & & & & & & & \\ \hline 9 & & & 1 & & & & & & & & \\ \mathrm{A} & & & & & & & & & & & \\ \mathrm{B} & & & & & & & & & & & \\ \end{array} \]
\(\mathrm{Z}_{12}\) :
\[ \begin{array} {rrr|rrr|rrr|rrr} 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & \mathrm{A} & \mathrm{B} \\ 1 & & & & & & & & & & & \\ 2 & & & & & 6 & & & & & & \\ \hline 3 & & & & & & & & & & & \\ 4 & & & & & & & & & & \mathrm{B} & \\ 5 & & & & & & & & & & & \\ \hline 6 & & & & & & & & & 2 & & \\ 7 & & & & & & & & & & & \\ 8 & & & & & & & & 2 & & & \\ \hline 9 & & & & & & & & & & & \\ \mathrm{A} & 0 & & & & & & & & & 5 & 7 \\ \mathrm{B} & & & & & & & & & & & \\ \end{array} \]
\(\mathrm{A}_{4}\) :
\[ \begin{array} {rrr|rrr|rrr|rrr} 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & \mathrm{A} & \mathrm{B} \\ 1 & & & & & & & & & & & \\ 2 & & & \mathrm{B} & & & & & & & & \\ \hline 3 & & & & & & & & & & & \\ 4 & & & & & & & & & & & \\ 5 & 7 & & & & & & & & & & \\ \hline 6 & & & & & 7 & & & & & & \\ 7 & & & & & & & & & & & \\ 8 & & & & & & & & 5 & & & \\ \hline 9 & & & & & 4 & & & & & & \\ \mathrm{A} & & & & & & & & & & & \\ \mathrm{B} & & & & & & & & & & & \mathrm{A} \\ \end{array} \]
\(\mathrm{D}_{12}\) :
\[ \begin{array} {rrr|rrr|rrr|rrr} 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & \mathrm{A} & \mathrm{B} \\ 1 & & & & & & & & & & & \\ 2 & & & & & & & & & & & \\ \hline 3 & & & & & & & & & & & \\ 4 & & & & & & 9 & & & & & \\ 5 & & & & & & & & & & & \\ \hline 6 & & 1 & & & & & & & & & \\ 7 & & & & & 8 & & & & & & \\ 8 & 4 & & & & & & & & & & \\ \hline 9 & \mathrm{A} & & & & & & & & & & \\ \mathrm{A} & & & & 3 & & & & & & & \\ \mathrm{B} & & & & & & 0 & & & & & \\ \end{array} \]
\(\mathrm{Z}_{6} \times \mathrm{Z}_{2}\) :
\[ \begin{array} {rrr|rrr|rrr|rrr} 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & \mathrm{A} & \mathrm{B} \\ 1 & & & & & & 3 & & & & & \\ 2 & & & & & & & & & & & \\ \hline 3 & & & & & & & & & & & \\ 4 & & & & & & & & & & & \\ 5 & & & & & & & & & & & \\ \hline 6 & & 8 & & & & & & & & & \\ 7 & & & & & & & & & & & \\ 8 & 4 & & & & & & & & & & \\ \hline 9 & & & & & & & & & & & \\ \mathrm{A} & & & & & & & 9 & & 8 & & \\ \mathrm{B} & & & & 3 & & & 2 & & & & \\ \end{array} \]
自动求解器 首先考虑最暴力的求解方法：直接把结合律作为约束，使用求解器求解。使用 Z3 描述这种约束非常简单：1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 op = Function("op" , IntSort(), IntSort(), IntSort()) solver = Solver() for left in range (order): for right in range (order): solver.add(op(left, right) >= 0 , op(left, right) < order) for element in range (order): solver.add(op(0 , element) == element) solver.add(op(element, 0 ) == element) solver.add(Distinct([op(element, other) for other in range (order)])) solver.add(Distinct([op(other, element) for other in range (order)])) for row in range (1 , order): for col in range (1 , order): clue = grid[row][col] if clue is not None : solver.add(op(row, col) == clue) for a in range (order): for b in range (order): for c in range (order): solver.add(op(a, op(b, c)) == op(op(a, b), c))
这个程序 可以求解 \(8\) 阶和 \(10\) 阶的题目，但对于 \(12\) 阶的题目就无能为力了：五道题目在 1min 的时限内都无法求解并证明唯一性。
能不能做得更好呢？答案是肯定的。我们可以把抽象代数知识融入求解器，告诉它对应阶数的群的所有种类。对于每个种类，任取一个 Cayley 表作为规范形，让求解器搜索题面数字与这一 Cayley 表中元素之间的一一映射。这样，求解器的搜索空间就从 \(121\) 个格子变成了 \(11\) 个元素的排列。改进后的程序 可以在 27s 内解决五道 \(12\) 阶题目。
当然——如果融入更多的知识，也就是直接把所有 Cayley 表丢进去，那么遍历一遍就能得到答案了，用时甚至不到一秒钟！看来数学理论对这个奇特的解谜帮助确实很大（笑）