Nonexistence of Whirling-Knight Tours at Half Coil Count for $n \equiv 4, 6 \pmod 8$

破解 Beluhov 猜想：为什么这些“回旋马周游”路径根本不存在？

Nonexistence of Whirling-Knight Tours at Half Coil Count for $n \equiv 4, 6 \pmod 8$

总结

问题

方法

结果

要点

摘要

本文解决了由 Beluhov 提出的关于“回旋马周游”（Whirling Knight’s Tour）的一个组合数学猜想。作者证明了在棋盘尺寸 $n \equiv 4, 6 (mod 8)$ 的情况下，不存在线圈数（Coil Count）为 $n /2$ 的哈密顿回路。该结论通过对循环覆盖线性规划（Cycle-cover LP）构造 Farkas 不可行性证明文件（Farkas Certificate）得以严谨证实。

TL;DR

在组合数学的长卷中，关于国际象棋中“马周游”（Knight's Tour）问题的研究已持续数百年。近日，来自中科大的 Shisheng Li 在 arXiv 上发表的研究，彻底终结了由 Beluhov 提出的一个关于“回旋马周游”（Whirling Knight’s Tour）的猜想。该研究证明：在 $n \equiv 4$ 或 $n \equiv 6 (mod 8)$ 的棋盘上，绝对不存在线圈数恰好为 $n /2$ 的回旋巡游路径。

背景定位：这是一篇典型的组合最优化与图论交叉的理论修补作。它不仅补全了回旋马周游理论的最后一块拼图，更展示了如何利用 线性规划（LP）松弛 与 Farkas 证书 这套强大的数学工具来“否定”一个复杂组合问题的存在性。

1. 何为“回旋马”？（Whirling Knight）

标准的马周游要求马访问 $nim es n$ 棋盘上的每个格子一次并回到起点。而 回旋马 增加了一个严苛的几何约束：所有的马步必须是围绕棋盘中心（Pivot）逆时针（CCW）旋转的。

线圈数 (Coil Count, $c$ )：简单来说，就是这条路径绕棋盘中心转了多少圈。
痛点：Beluhov 此前通过计算机搜索发现， $n \equiv 0, 2 (mod 8)$ 时可以找到 $c = n /2$ 的路径，但在 $n \equiv 4, 6 (mod 8)$ 时却颗粒无收。

由于组合空间巨大，单纯的计算搜索不能代表证明。寻找一个通用的数学理由来解释这种“阶梯式”的不存在性，成为了该领域的难题。

2. 核心利器：Farkas 证书与 LP 松弛

作者将寻找哈密顿路径的问题“放松”为一个线性规划问题。如果一个更简单的线性约束系统都没有解，那么原问题（寻找完整的回路）自然也没有解。

证明逻辑：

建立约束：每个格子（顶点）的入度和出度必须为 1，且路径的总相交数（Crossing Count）必须等于预设的线圈数 $c$ 。
构造 Farkas 证书：这是一个三元组 $(α, β, γ)$ 。数学上证明，如果能找到一组权重，使得在所有允许的移动（弧）上权重的总和 $\leq 0$ ，而整体系统的目标常数项和 $> 0$ ，那么这个系统就是不可行的。

3. 架构解析：几何引理的定力

为了支撑 Farkas 证书的有效性，作者提出了一个关键的 几何引理（Geometric Lemma）。

模型架构图：回旋马移动与中心射线的交叉判定 上图展示了典型的逆时针马步弧如何跨越棋盘中心的北铅垂线（North Plumb-line），这是计算线圈数的核心。

引理指出：对于处于枢轴列附近的特定区域，任何合法的逆时针马步都必须跨越中心射线。这为后续构造证书中的权重提供了物理依据。

4. 针对不同余数的两种策略

论文最精彩的部分在于，针对两种余数类构造了完全不同的证书结构：

情况一： $n \equiv 6 (mod 8)$ —— 块状计数

对于这类棋盘，作者定义了两个对称的单元格集合 $N^{in}$ 和 $N^{o u t}$ 。

直觉：通过设定权重，作者证明了每一条进入 $N^{in}$ 的弧和离开 $N^{o u t}$ 的弧都会贡献一个线圈计数。
矛盾产生：计算发现，路径中这些特定弧的总数至少会产生 $4 m + 4$ 个计数，但目标线圈数 $c$ 却被限制在 $4 m + 3$ 。多出的这一个计数直接宣判了路径的“死刑”。

n=14 时的证书支持区域 图 5：在 n=14 棋盘上，蓝色和橙色的方块区域构成了证书的支撑集。

情况二： $n \equiv 4 (mod 8)$ —— 奇偶性交替

对于这种情况，块状计数失效了。作者引入了一个位于棋盘东北角的 三角形区域（NE-triangle），赋予其 $\pm 1$ 交替的权重。

数学技巧：利用一个巧妙的奇偶性计数恒等式（式 9），证明在该三角形内，奇数坐标和的格子比偶数坐标和的格子恰好多出 $2 m + 1$ 个。
结果：这一差异最终导致 RHS（右手项）恒等于 1，再次通过 Farkas 理性反证了不可行性。

5. 实验结论与深度洞察

本研究通过严密的证明，不仅 Settled 了 Beluhov 的猜想，还揭示了回旋马问题的深层对称性破缺：

边界敏感性：几何引理在靠近枢轴行（Pivot Row）时是失效的，这解释了为什么只有特定的线圈数和特定的 $n$ 值下才存在解。
组合屏障： $c = n /2$ 恰好位于线性规划可行性的边缘。这是一个典型的“相变点”，微小的奇偶性变化（余数 4, 6 vs 0, 2）就会导致解空间的完全消失。

局限性：虽然解决了 $c = n /2$ 的情况，但对于更大线圈数（如 $c > n /2$ ）的不存在性范围，该方法是否能生成通用的证书仍有待探索。

总结：这篇论文是代数方法解决几何组合问题的典范。它告诉我们，当我们无法通过编程搜索找到答案时，转向对偶空间（Dual Space）寻找不可行性证明，往往能看到问题的本质。

发现相似论文