本文翻译自 Claude’s Cycles，原载于 Hacker News。
引言：震撼的一天
震惊！就在昨天，我得知一个困扰了我好几周的开放问题，刚刚被 Claude Opus 4.6 —— Anthropic 三周前发布的混合推理模型 —— 解决了！看来我不得不重新审视我对”生成式 AI”的看法了。
最令人欣喜的是，不仅我的猜想得到了一个优美的解答，更值得庆祝的是自动推理和创造性问题求解领域取得了如此巨大的进步。让我在这篇短文中简要讲述这个故事。
问题的由来
这个问题源于我在为《计算机程序设计艺术》未来卷册撰写关于有向哈密顿环（directed Hamiltonian cycles）的内容时遇到的：
考虑一个有 m³ 个顶点 ijk（其中 0 ≤ i, j, k < m）的有向图，每个顶点有三条出边，分别指向 i+jk、ij+k 和 ijk+（其中 i+ = (i+1) mod m）。对于所有 m > 2，尝试找到一种将所有边分解为三个有向 m³ 环的通用方法。
我已经解决了 m = 3 的情况，并作为练习题的答案请求一般化方案。我的朋友 Filip Stappers 接受了挑战，通过实验发现了 4 ≤ m ≤ 16 的解。因此，除了 m ≤ 2 之外，所需的分解很可能确实存在。
正是 Filip 有勇气用上述确切措辞向 Claude 提出了这个问题。他还给予指导，要求 Claude 在每次探索后立即记录进度。
Claude 的探索之旅
Claude 的攻击策略令人赞叹。
第一阶段：问题重构
首先它重新表述了问题：”需要一个 sigma: Z₃ᵐ → S₃，在每个顶点分配一个 {0, 1, 2} 的排列；顶点 v 的环 c 沿方向 sigma(v)[c] 前进。每个结果函数图必须是单个哈密顿环。”
然后它尝试简单答案：”如果 sigma 是循环的，即 fc(v) = (c+g(v)) mod 3，那么只需要一个函数 g。测试了线性 g = (a·i+b·j+c·k) mod 3 和二次变体。没有线性或简单二次的 g 可行。”
第二阶段：DFS 搜索
Claude 的第二次探索是所谓的 DFS 搜索（深度优先搜索）：”尝试对 m = 3 的 sigma 分配进行暴力 DFS（6²⁷ 搜索空间）。没有好的剪枝策略太慢了。”
第三阶段：2D 蛇形分析
第三次尝试了所谓的 2D 蛇形分析：”关键的 2D 结果：模式 [0ᵐ⁻¹1]ᵐ 在 Cay(Z₂ᵐ, {e₀, e₁}) 中对于 m = 3 产生哈密顿环。其补集也有效，给出了有效的 2D 分解。”
这真是太令人印象深刻了！Claude 首先识别出这个有向图是所谓的凯莱图（Cayley digraph），有两个生成元 e₀ 和 e₁；数学家会理解边对 m² 个顶点起群作用，其中 e₀ 增加第一个分量，e₁ 增加第二个分量。
第四阶段：3D 蛇形模式
探索 4 构建了”3D 蛇形模式” [0ᵐ⁻¹1]ᵐ⁻¹[0ᵐ⁻¹2]ᵐ。删除这个环后，Claude 发现剩余的 2-正则有向图具有”刚性结构，使分解困难”。
纤维分解的突破
真正的突破出现在探索 15，Claude 引入了所谓的纤维分解（fiber decomposition）：
“商映射 π(i, j, k) = i+j+k mod m 将所有边从纤维 Fₛ 映射到 Fₛ₊₁。有向图是分层的。在纤维坐标 (i, j) 中，k = (s-i-j) mod m。”
使用这些纤维坐标，问题现在可以重新表述为：为每个 (i, j, s) 选择三个操作符的排列，这些操作符将 (i, j) 移动 (1, 0)、(0, 1) 或 (0, 0)。
探索 18 “实现了完整的纤维框架作为可执行代码。对 m = 3 的穷举回溯在 0.1 秒内找到了有效分解（10932 个节点）。”
关键时刻
探索 27 几乎成功了：”取 3D 蛇形作为环 0，应用循环坐标旋转得到环 1 和 2……所有三个对于测试的每个 m = 3…9 都是单独哈密顿的！只有 3(m-1) 个顶点有冲突。”
不幸的是，这些冲突无法解决。探索 29 证明了许多看似合理的场景实际上是不可能的。
但是，探索 30 回到了探索 20 中通过模拟退火找到的解，注意到每个纤维的选择只依赖于单个坐标：s = 0 只依赖于 j；s = 1 和 s = 2 只依赖于 i。
这导致了一个具体的构造（探索 31），以 Python 程序的形式，为 m = 3, 5, 7, 9 和 11 产生了有效结果！
最终解决方案
以下是该 Python 程序的简化版本，转换为 C 形式：
int c, i, j, k, m, s, t;
char *d;
for (c = 0; c < 3; c++) {
for (t = i = j = k = 0; ; t++) {
printf("%x%x%x ", i, j, k);
if (t == m*m*m) break;
s = (i+j+k) % m;
if (s == 0) d = (j == m-1 ? "012" : "210");
else if (s == m-1) d = (i > 0 ? "120" : "210");
else d = (i == m-1 ? "201" : "102");
switch (d[c]) {
case '0': i = (i+1) % m; break;
case '1': j = (j+1) % m; break;
case '2': k = (k+1) % m; break;
}
}
printf("\n");
}
Filip Stappers 对 Claude 的 Python 程序进行了测试，对于 3 到 101 之间的所有奇数 m，每次都能找到完美的分解。因此他相当合理地得出结论：问题确实对于奇数值得到了解决。
m = 3 的示例环
在 m = 3 的特殊情况下，第一个环是：
022 → 002 → 000 → 001 → 011 → 012 → 010 → 020 → 021 →
121 → 101 → 111 → 112 → 122 → 102 → 100 → 110 → 120 →
220 → 221 → 201 → 202 → 200 → 210 → 211 → 212 → 222 → 022
可推广性定理
文中提出了一个重要概念：可推广的哈密顿环。如果一个 m = 3 的哈密顿环 C 通过特定构造能对所有奇数 m ≥ 3 产生哈密顿环，则称它是可推广的。
令人惊讶的是，m = 3 恰好有 11502 个哈密顿环，其中恰好 1012 个可以推广到 m = 5。进一步地，恰好 996 个可以同时推广到 m = 5 和 m = 7。而这 996 个实际上可以推广到所有奇数 m > 1。
定理：”Claude 式”分解对所有奇数 m > 1 有效，当且仅当它为 m = 3 定义的三个序列都是可推广的。
通过设置精确覆盖问题，使用 m = 3 的 11502 个哈密顿环，可以推断出 3×3×3 分解问题恰好有 4554 个解。类似地，如果我们研究仅使用 996 个可推广环中的三个来覆盖每条边的所有方法，我们会发现这 4554 个解中恰好有 760 个只涉及可推广环——大约每 6 个中有 1 个。
仍然开放：偶数情况
这个分解问题对于偶数值的 m 仍然开放。m = 2 的情况很久以前就被证明是不可能的。在探索 24 中，Claude 说它找到了 m = 4、m = 6 和 m = 8 的解，但看不到推广这些结果的方法。
Filip 告诉我，在解决了奇数情况后，他让 Claude 继续研究偶数情况。”但过了一会儿它似乎卡住了。最后，它甚至无法正确编写和运行探索程序了，非常奇怪。所以我停止了搜索。”
个人感悟
这篇论文给我最大的震撼在于：
-
AI 的系统性探索能力：Claude 不是随机猜测，而是有条不紊地尝试了多种方法——从简单猜想、暴力搜索、几何分析到纤维分解，展现了惊人的问题求解策略。
-
人机协作的新范式：Filip 的引导（要求文档化进度、适当的 restart）与 Claude 的推理能力形成了有效互补。
-
数学发现的民主化：这类原本需要顶尖数学家多年研究的开放问题，现在可能被 AI 在几小时内突破。
-
“顿悟”时刻的再现：探索 30 发现”只依赖单个坐标”这一关键洞察，与人类数学家的顿悟体验何其相似。
结语
总而言之，这绝对是一个令人印象深刻的成功故事。我想 Claude Shannon 的精神一定会为他的名字现在与这样的进步联系在一起而感到自豪。向 Claude 致敬！
参考文献：
-
Jacques Aubert and Bernadette Schneider, “Graphes orientés indécomposables en circuits hamiltoniens.” Journal of Combinatorial Theory B32 (1982), 347–349.
-
Donald E. Knuth, The Art of Computer Programming, Volume 4A: Combinatorial Algorithms, Part 1, 2011.
-
Donald E. Knuth, preliminary drafts entitled “Hamiltonian paths and cycles.”