Symmetric Sudoku-Type Games from Perfect Codes

技术摘要：基于完美码的对称数独类游戏

问题陈述
虽然标准的 $9 \times 9$ 数独是一个具有丰富对称性的、研究透彻的组合对象，但许多变体（如拼图数独）通过改变网格分区，破坏了旋转对称性和反射对称性。这种对称性的丧失使得许多标准解题策略和理论工具无法适用。本文旨在构建一个通用框架，用于构造数独类游戏，使其在提供新结构变化的同时，保留与经典游戏相当的高水平对称性。

方法论
作者提出了一种基于整数模 $n$ 环（$\mathbb{Z}_n$）上的李距离完美码和直径完美码的构造方法。

1. 理论基础：该方法利用这些码的“平铺性质”。完美码 $C$ 将空间 $\mathbb{Z}_n^2$ 划分为半径为 $t$ 的不相交球体。“直径完美码”在码 - 反码界（Code-Anticode Bound）中达到等式，利用特定直径的反码对空间进行划分。
2. 网格构造：
   • 构建一个调色板网格 $I$，其中每个单元格 $(x, y)$ 根据该坐标包含在哪个码字的球体（或反码平移）中而被分配一个符号。
   • 定义一个数独网格 $S$ 为 $n$ 阶拉丁方，且与调色板网格 $I$ 正交。这种正交性确保了每个符号在由码的平铺所定义的区域内恰好出现一次。
3. 等价关系：作者定义了所得网格在以下情况下的等价类：
   • 重标记：符号的置换。
   • 刚体运动：由保持底层码结构的旋转、反射和平移生成的特定群 $G_S$。
4. 案例研究：该框架应用于两个最小案例：
   • $5 \times 5$ 数独：由 $\mathbb{Z}_5^2$ 中的 1-纠错完美码构造（其中 $n=5$）。
   • $8 \times 8$ 数独：由 $\mathbb{Z}_8^2$ 中的 3-直径完美码构造（其中 $n=8$）。
5. 难度评估：实现了一个“类人求解器”以评估可玩性。该求解器仅使用基本逻辑推理（唯一候选数和隐性唯一数），并结合试错阶段。难度通过初始线索之外所需的试错插入次数来量化。

主要贡献与结果

• 解的枚举：
  • 对于$5 \times 5$ 案例，作者识别出 2,040 个有效网格。在重标记和刚体运动群的作用下，这些网格简化为 17 个不等价解。
  • 对于$8 \times 8$ 案例，分析了两种不同类型的直径完美码。第一种类型产生了约 $2.80 \times 10^{11}$ 个有效网格，简化为 232,735 个不等价解。第二种类型产生了约 $1.95 \times 10^{11}$ 个有效网格，简化为 304,014 个不等价解。
• 最小数独分析：
  • 对于 $5 \times 5$ 案例，作者枚举了最小数独谜题（即具有唯一解所需的最少线索数的谜题）。他们发现共有 15,898,200 个最小谜题（等价类下为 35,759 个），线索数范围从 4 到 7。
  • 对于 $8 \times 8$ 案例，对最小谜题进行完整枚举被认为在计算上不可行。相反，作者识别出了线索数范围从 10 到 18 的最小谜题。
• 特殊网格：研究识别出了“特殊数独网格”，这些网格不仅满足用于构造的特定完美码的数独约束，而且满足给定参数的任何完美码的数独约束。对于 $5 \times 5$ 有 240 个这样的网格，对于 $8 \times 8$ 有 $4 \times 8!$ 个。
• 难度分布：使用类人求解器对 $5 \times 5$ 游戏的分析揭示了难度水平的平衡分布。谜题被分类为简单（得分 0）、中等（得分 1–10）和困难（得分 >10）。结果显示了可行的难度混合，许多谜题可通过基本逻辑解决，而另一些则需要大量的试错。

意义与主张
本文主张，完美码为生成对称数独类游戏提供了一个系统化且数学上严谨的框架。其主要意义在于证明：

1. 对称性保留：与不规则变体不同，这些基于码的构造固有地保留了经典数独中的旋转和反射对称性，从而允许应用标准的群论分析。
2. 结构多样性：该框架生成了结构多样的有效网格，将数独的版图扩展到了标准的 $9 \times 9$ 格式之外。
3. 实际可玩性：难度分析证实，这些游戏不仅仅是理论构造，而且提供了“从简单到困难的平衡难度分布”，使其成为传统数独进行娱乐性游戏的可行替代品。

作者得出结论，这种方法架起了编码理论与娱乐数学之间的桥梁，为生成具有丰富代数结构的逻辑谜题提供了新途径。未来的工作建议将这些构造扩展到其他环和距离度量（例如曼海姆度量或秩度量）。