𝗗𝗼𝗻𝗮𝗹𝗱 𝗞𝗻𝘂𝘁𝗵 𝗶𝘀 𝘀𝗵𝗼𝗰𝗸𝗲𝗱 𝗯𝘆 𝗵𝗼𝘄 𝗴𝗼𝗼𝗱 𝗔𝗜 𝗵𝗮𝘀 𝗯𝗲𝗰𝗼𝗺𝗲 𝗮𝘁 𝘀𝗼𝗹𝘃𝗶𝗻𝗴 𝗽𝗿𝗼𝗯𝗹𝗲𝗺𝘀

Knuth is now 88 years old. He wrote The Art of Computer Programming starting in 1962, and won the Turing Award in 1974.

In his paper which talks about how AI helped him solve a problem, he wrote on the start: "Shock! Shock!"

Here is what happened:

𝟭. 𝗧𝗵𝗲 𝗽𝗿𝗼𝗯𝗹𝗲𝗺

Knuth was stuck for weeks on an open graph theory problem he was preparing for a future volume of TAOCP. The problem involves a 3D grid of points, think of it as an m×m×m cube. Each point connects to three neighbors. The challenge is to find a single rule that traces three separate paths through the entire cube, where each path visits every point exactly once.

That kind of path is called a Hamiltonian cycle. Knuth had worked it out for a 3×3×3 cube. His friend Filip Stappers confirmed it worked up to a 16×16×16 cube by running it on a computer. But no one could find a general rule that worked for any size.

𝟮. 𝗧𝗵𝗲 𝘀𝗲𝘀𝘀𝗶𝗼𝗻

Stappers gave the problem to Claude Opus 4.6 with one strict rule: after every attempt, write down what you tried and what you learned before moving on. Claude worked through 31 explorations over about an hour. It tried simple formulas, brute-force search, geometric patterns, statistical methods. Most hit dead ends.

At attempt 25, it essentially told itself: "The search approach won't get us there. This needs actual mathematical reasoning." At attempt 31, it found a construction that worked.

𝟯. 𝗧𝗵𝗲 𝗰𝗼𝗻𝘀𝘁𝗿𝘂𝗰𝘁𝗶𝗼𝗻

Claude found a surprisingly simple rule for navigating the cube. At each point, look at where you are and follow a small set of conditions to decide which direction to move next. That's it. No complex formula, no special cases beyond a handful of boundary checks. Stappers ran the resulting program against every odd cube size from 3 to 101. It produced perfect results every time.

Then, Knuth wrote a formal proof, generalized the construction, and showed that there are exactly 760 valid solutions of this type for all odd cube sizes. Claude found one of them. Knuth found all of them.

𝟰. 𝗪𝗵𝗮𝘁 𝗵𝗮𝗽𝗽𝗲𝗻𝗲𝗱 𝗻𝗲𝘅𝘁

The even-sized cubes were still unsolved. Then a friend fed that version of the problem to GPT-5.4 Pro and got back a 14-page proof that required no further work on it.

Then another researcher used GPT and Claude together as two collaborating agents and found an even better solution covering both cases. The problem that had been open for years, odd and even sizes, is now fully solved. Knuth's reaction was: "We are living in very interesting times indeed."

His closing line: "It seems I'll have to revise my opinions about generative AI one of these days."

From Donald Knuth, that sentence lands differently than it would from anyone else.

Paper: cs.stanford.edu/~knuth/…