Claude 之环：Claude Opus 4.6 攻克高德纳提出的数学难题 [PDF]
Hacker News 摘要原标题：Claude's Cycles: Claude Opus 4.6 solves a problem posed by Don Knuth [pdf]
计算机科学泰斗高德纳（Don Knuth）在2026年2月发布的一篇文章中，分享了一个令他震惊的消息：他在《计算机程序设计艺术》（TAOCP）后续卷中研究了数周的一个数学难题，被 Anthropic 公司当时发布的混合推理模型 Claude Opus 4.6 攻克了。高德纳表示，这次经历让他必须重新审视对生成式 AI 的看法，并赞赏了 AI 在自动推演和创造性解决问题方面的巨大进步。
问题背景
高德纳正在编写关于定向哈密顿循环（directed Hamiltonian cycles）的内容。他设计了一个具有 m³ 个顶点的有向图，每个顶点表示为 ijk（其中 0 ≤ i, j, k < m）。每个顶点有三条出边，分别指向 (i+1)jk、i(j+1)k 和 ij(k+1)，所有加法均对 m 取模。问题的目标是：对于所有 m > 2 的情况，将图中所有的边分解为三个覆盖所有顶点的哈密顿循环（Hamiltonian cycles）。
高德纳之前解决了 m = 3 的情况，他的朋友 Filip Stappers 通过实验发现了 4 ≤ m ≤ 16 的解，这表明通用分解方案极有可能存在。
Claude 的探索过程
Filip Stappers 使用精确的问题描述向 Claude 提问，并要求 Claude 在执行每一个探索脚本后，必须立即更新其计划文件 plan.md 以记录进度。Claude 的攻击计划非常出色，经历了多次尝试：
• 初步尝试：它先尝试了线性函数和二次函数变体，但未能成功。
• 深度优先搜索：它尝试对 m = 3 的情况进行暴力搜索，但发现如果没有良好的剪枝，速度太慢。
• 蛇形模式分析：Claude 意识到该图是一个 Cayley 有向图，并成功识别出一种 2D 蛇形模式，随后将其推广到 3D 蛇形模式（即经典的多进制格雷码）。虽然这构造了一个哈密顿循环，但剩余的边构成的图形结构非常僵硬，难以分解。
• 纤维分解法：在第 15 次探索中，Claude 引入了纤维分解（fiber decomposition）模型，利用 i+j+k mod m 的值将图分层。
• 模拟退火与回溯：在第 18 到 20 次探索中，Claude 通过回溯法在 0.1 秒内找到了 m = 3 的解，并利用模拟退火找到了 m = 4 的特解。
• 思维转变：经过多次尝试失败后，Claude 决定不再死磕纤维结构，而是直接思考构成哈密顿循环的本质条件。它在第 27 次探索中尝试了坐标循环旋转法，虽然在超平面上存在冲突，但离成功又近了一步。
最终解法与程序
在第 31 次探索中，Claude 终于通过一个 Python 程序给出了通用构造方案，该方案在 m = 3, 5, 7, 9, 11 等奇数情况下全部通过了测试。高德纳将其核心逻辑转化为了如下 C 语言逻辑：
• 定义变量 s = (i+j+k) mod m。
• 当 s = 0 时：如果 j = m-1，增加 i；否则增加 k。
• 当 0 < s < m-1 时：如果 i = m-1，增加 k；否则增加 j。
• 当 s = m-1 时：如果 i > 0，增加 j；否则增加 k。
这里的增加操作均指对 m 取模。
严谨证明与结论
高德纳随后对 Claude 发现的规律进行了严格的数学证明。证明的核心在于，当 m 是奇数时，该规则能确保序列在回到起点前遍历完所有 m³ 个顶点。
通过对 m = 3 情况下的 11502 个哈密顿循环进行分析，高德纳发现其中有 996 个可以推广到所有大于 1 的奇数 m。而在这 996 个循环中，只有 760 个可以组合成符合要求的“类 Claude”分解方案。这意味着 Claude 不仅找到了解，而且在海量的可能性中精准锁定了一个通用的构造模式。
总结与展望点
• 奇数解完备：对于所有奇数 m，该问题已通过 Claude 的构造和高德纳的证明得到解决。
• 偶数解悬而未决：当 m 为偶数时，该问题依然开放。Claude 曾试图解决 m = 4, 6, 8 的情况，但未能找到通用公式，并在后续尝试中陷入逻辑混乱，无法正常运行程序。
• AI 的成就：高德纳对这次 AI 辅助科研的经历感到惊叹。从开始对话到得出第 31 次探索的成功结果，仅用了一小时左右。他认为这不仅是自动推论的胜利，更是创造性解决问题的典范。
原文：https://www-cs-faculty.stanford.edu/~knuth/papers/claude-cycles.pdf