哈密顿分解
哈密顿分解（Hamiltonian Decomposition）是将一个图的边集分解为多个互不重叠的哈密顿圈的问题。这是一个经典的NP-hard图论难题。
高德纳的版本
考虑一个m×m×m的三维网格有向图（torus-like directed 3D grid），共有m³个顶点，每个顶点(i,j,k)有三条出弧，分别指向(i+1 mod m, j, k)、(i, j+1 mod m, k)和(i, j, k+1 mod m)。目标是将所有弧（边）精确分解为三个有向哈密顿圈——每个圈访问每个顶点恰好一次，长度均为m³，且三圈互不重叠、覆盖全部边。
历史
- 高德纳早在30多年前就注意到m=3的特例，并作为练习题放入TAOCP。
- Filip Stappers后来实验找到4≤m≤16的解，但通用构造始终缺失。
- 偶数m早知不可行；奇数m虽有零星解法，却无普适证明。
- 2026年3月，Claude Opus 4.6和GPT-5.4 Pro联手攻克此难题。
意义
哈密顿分解难题的攻克不仅解决了具体的数学问题，更展示了AI在解决结构化、可验证的数学难题上的潜力，预示了科研范式的转变。