Claude Opus 4.6 Solves Knuth's Hamiltonian Cycle Problem for Odd m

Don Knuth recounts how the AI model Claude Opus 4.6 solved a complex open problem regarding Hamiltonian cycle decomposition for odd values of m. By using an iterative exploration process, the AI moved from failed brute-force attempts to a successful algorithmic construction that Knuth subsequently proved mathematically. While the AI was highly effective for odd integers, the problem remains unsolved for even values of m where the AI eventually reached its reasoning limits.

Key Points

• Claude Opus 4.6 successfully identified a general construction for decomposing a specific digraph into three Hamiltonian cycles for all odd m > 2.
• The AI followed a structured 'plan of attack' involving 31 distinct explorations, ranging from brute-force DFS to sophisticated fiber-based coordinate analysis.
• Don Knuth provided a formal mathematical proof for the AI's discovered algorithm, confirming its validity for the infinite set of odd integers.
• The study revealed that there are 760 generalizable 'Claude-like' solutions for this problem, though the AI's specific solution lacked cyclic symmetry.
• Despite the success with odd values, the AI reached a limit and could not find a generalizable solution for even values of m.

Sentiment

The HN community is broadly enthusiastic and impressed, with genuine excitement about the human-AI collaboration achieving a notable mathematical result. There is a substantive undercurrent of debate about attribution and framing — some skeptics argue the title overstates Claude's role — but the overall tone is celebratory and intellectually engaged. Knuth's own evident satisfaction, combined with the concrete verifiability of the result, anchors the discussion in something real and keeps the debate constructive.

In Agreement

• Claude's contribution of finding the working pattern for odd m through systematic exploration was the genuine creative insight and hardest part of the research — writing the formal proof was comparatively mechanical once the pattern was known
• Human-AI collaboration proved synergistic, with the human providing research direction and oversight while the AI executed exhaustive search strategies across large solution spaces
• Knuth's willingness to update his previously skeptical view of AI is scientifically admirable and appropriate — and his endorsement as the primary researcher is a strong signal of the contribution's genuine value
• The achievement demonstrates that expert-guided AI can meaningfully contribute to open mathematical problems, with Claude serving as a powerful 're-search' partner
• LLMs have three key strengths for research: vast knowledge, connection-making, and tireless trial and error — this case is a strong illustration of all three

Opposed

• The framing that Claude 'solved' the problem is misleading — Claude found examples while Knuth provided the mathematical proof establishing correctness for all odd m
• Claude failed entirely on the even case, showing fundamental limitations in sustained mathematical reasoning beyond what systematic search can achieve
• Context window degradation ('the dumb zone') caused real problems in the original experiment and represents an ongoing structural limitation for complex research tasks
• A replication attempt that appeared to succeed quickly was found invalid — the agent had access to Knuth's paper in a nearby directory — raising questions about experimental rigor in AI research claims
• The achievement may reflect pattern matching over a vast training corpus of graph theory and combinatorics rather than genuine novel mathematical reasoning