Donald Knuth’s 2025 Christmas Lecture: The Knight’s Tours

“It’s that time of the year!” read the email from Stanford Online. As he approaches his 88th birthday, Donald Knuth returned in early December for his special once-a-year “Christmas” lecture — a tradition he’s been honoring for over 30 years.

Stanford’s beloved professor emeritus reminded his audience he’s still writing “The Art of Computer Programming” — a legendary book he’s been working on for over 63 years (releasing it in installments).

But this year, he took a detour of sorts: The revered math and algorithms expert promised to discuss “recent breakthroughs in one of the most venerable graph theory questions that has fascinated people for more than 1,200 years: ‘Can a knight cover all cells of a chessboard without ever visiting the same place twice?’”

Yet inside that question’s dazzling permutations, Knuth delivered an important life lesson — that through all the math and computer science, what he’s searching for is beauty. Shuffling cheerfully through his printouts, Knuth showed off his favorite solutions to the puzzle, like a collection of treasured snowflakes.

And with warmth and wisdom, he delivered a real holiday moment.

Art and Adventures

Speaking at Stanford’s Nvidia Auditorium, the lecture opened with an announcement — that recordings of past lectures have been recently restored! They’ve also created a playlist with 26 past Christmas lectures — all the way back to the late 1990s — while Knuth’s own webpage links to other collections of his videos as far back as 1981.

But looking back over 2025, Knuth told his audience playfully that “I gotta move fast tonight, because there’s — I just had too many adventures this year.” For one thing, Knuth’s “news” page notes that in June, he celebrated his 64th wedding anniversary.

In April, he’d also helped celebrate the grand reopening of the computer science department at his alma mater, Case Western University in Cleveland. When they’d asked Knuth how they should decorate its walls, Knuth had suggested “Knight’s Tours” — those patterns formed by tracing the path of a knight visiting every chess board square exactly once.

Knuth even collaborated with his alma mater’s design team, and in a new 2,200-word page on his website, explains the mathematics visualized on each wall. Knuth’s website calls it “a thrilling prospect for me, because I’ve long been a fan of ‘Geek Art’” — a concept Knuth explained in his Christmas lecture. “It’s a sort of right-brain/left-brain thing. You know with one half of your brain that it’s nice, with the other half you say, ‘This is just a gorgeous design.’”

They’re described in detail in “The Art of Computer Programming.” And he’d share examples in this Christmas lecture.

‘Sheer Beauty’

Knuth said his fondness for Knight’s Tours started in 1973, and more than half a century later, he’d finally found his old notes. “I was intrigued at that time by an unsolved problem,” he told his audience — smiling at the fact that he still hadn’t solved it, though the question was first posed in 1891.

But Knuth also realized that every two-move combination in a Knight’s Tour will form an angle or “wedge” — and it turns out that identifying the wedges formed when landing on the four middle squares “gives me an easy way to divide all Knight’s Tours into about one-eighth as many.” (Since each solution could be rotated in one of four directions, or flipped to its mirror image.)

There’s an important lesson here: What you can classify, you can count.

Here in the 21st century, Knuth had written a program to take these “censuses” — to calculate how many total solutions exist (when given specific sets of wedge shapes for those four middle squares). His book’s latest Pre-Fascicles (published draft) details what he says are the “fun” data structures he used, which allowed him to finally answer that fateful question first posed in 1891: How many solutions have 16 moves for each of the four possible mathematical slopes for the knight’s moves?

The answer is: 103,361,771,080.

“It wasn’t really too hard to find those. Just it’s not that easy to do by hand!”

Later, Knuth says he hears from “all kinds of people who are entranced by the subject … It’s partly just — I don’t know, the sheer beauty of some of these tours, to look at, to watch ’em. It’s like listening to some of your favorite music — it’s rhyming in some way.”

During a Q&A session, Knuth tells the audience that one mathematician even created a Knight’s Tour for a three-dimensional chessboard (with four squares on each side). “It has beautiful symmetry.”

And soon he’s displaying an even more impressive result — the total number of all possible solutions to the Knight’s Tour problem: 13,267,364,410,532.

“This is the number that I thought I’d never know the answer to when I was an undergrad.” (The number was actually first calculated in 1997 by Australian mathematician Brendan McKay.)

Fond Figures

It’s all described in “The Art of Computer Programming: Pre-Fascicle 8a (Hamiltonian Paths and Cycles).” But that’s just the beginning. If you draw two lines connecting three squares a knight lands on, of course they’ll form an angle, and “A lot of people have been competing with each other to see what Knight’s Tour has the most 37-degree angles as you march along!

“It wasn’t known until this year, when they finally got the censuses working, that you can actually achieve 29.”

Of all these 13 billion tours, there’s only 136 that have reached this 29.

In fact, it turns out that for every possible angle, we’ve now calculated the maximum number that can appear in a solution — and Knuth has a fond thought for each one.

• Right angles? “Up until this year, the best-known was 38. But lo and behold, the census-taker found a way to do it with 39.”
• Straight lines? “This is kind of amazing because a guy in Romania actually found the optimum of this one already in 1932.” The maximum number is 19, and there are only 112 solutions.
• There are 56 solutions to the Knight’s Tour puzzle that use 42 acute angles. And if you’re trying to avoid using acute angles, there are 28,000 solutions.
• What about obtuse angles? The maximum number is 47. “The big surprise was that no matter what tour you have, you’ve got to have at least four obtuse angles in it. You can’t avoid them altogether.” And that four-angle solution is unique. “Of the 13,267,364,410,532, there’s exactly one of them. And I also happen to think this is one of the most beautiful Knight’s Tours you’ll see.”

There’s a beauty to math, and Knuth delightedly showed solutions filled with straight-line angles, or with intricate symmetrical wedge patterns.

But there are also other tantalizing angles formed in the solutions — in the lines showing where the knights crossed their own path. Knuth shows a diagram from a Belgian mathematician with just 69 path crossings.

Knuth himself had actually discovered a tour with 126 different intersections “years ago” while he was searching for symmetrical solutions. (It was only years later that he learned it was unique — the only 126-crossing solution, out of all 13,267,364,410,532.)

He shows more possible solutions — including one with the fewest possible perpendicular intersections, and with the most.

The answer there would be “all of them.” There’s one 64-move solution in which every move forms part of a perpendicular intersection.

Let There Be Light!

But the most complicated census of all was “a problem that I had been thinking about for 30 years.” And it turned out to be a grand adventure in both math and computer science.

Math includes the concept of a “winding number” — the number of times a point is fully circled by a curving line — and it’s often visualized with white for even numbers and black for odd. Knuth’s friend George Jelliss made a beautiful observation: “We can describe any Knight’s Tour by this black-and-white pattern.” The Pre-Fascicles of Knuth’s book include some impressive examples:

So what’s the darkest possible tour — and what’s the lightest?

It would’ve taken Knuth eight months to calculate it on his home computer. But fortunately, a Stanford colleague loaned him a better setup — 26 machines, boasting a total of 832 cores. There were two 16-core CPUs on each machine.

“What a feeling of power,” he said, drawing a laugh of agreement from his audience. “If you can imagine. For three days, I was running over 800 jobs at once!”

A ‘Whirling’ Finish

And what if that steadfast touring knight is always traveling counterclockwise around the center so, as Knuth puts it, “He never backs up!”

It’s possible — there are 1,120 ways on an 8 x 8 chessboard. But Knuth shows off the patterns. “When you look at these tours, they divide into coils,” with each complete circuit eventually crossing over a “plumb line.”

Knuth tried to make a pattern with as many coils as there are squares to a side, collaborating with Bulgarian mathematician Nikolay Beluhov. Beluhov eventually found such a solution, on a 12 x 12 chessboard. And then together, the two created a truly breathtaking diagram. “We came up with this construction that shows at least that for all N > 24 that are multiples of 4, there is a ‘whirling’ Knight’s Tour with N coils.”

“But then I said, ‘Well, what about trying to get one that has symmetry under rotation of 90 degrees?’”

And then for a grand finale, Knuth puts up his final slide. If these were a collection of snowflakes, this might be his prized possession. Not only does it have the same number of coils as squares on its side. “This is an 18 x 18 ‘whirling’ Knight’s Tour, that if you rotate it 90 degrees, it’s the same tour.”

And there it was — a mathematical beauty, and a visual beauty. “I thought this would be a good way to end my Christmas lecture, because it just looks like a wonderful Christmas decoration to me.”

And the audience applauded warmly.

---

Previous Donald Christmas Lectures

Donald Knuth’s Christmas Lectures are an annual tradition at Stanford University. Each year in early December, the renowned computer scientist and author of “The Art of Computer Programming” delivers a lecture on a variety of topics related to computer science and mathematics, to the delight of students and greybeards alike. These talks are captured on YouTube. 

Donald Knuth’s 2024 Christmas Lecture: ‘Strong’ Memories

Donald Knuth’s 2023 Christmas Lecture: Making the Cells Dance

Donald Knuth’s 2022 ‘Christmas Tree’ Lecture Is about Trees

Donald Knuth on Machine Learning and the Meaning of Life (2021)

Donald Knuth’s 2019 ‘Christmas Tree Lecture’ Explores Pi in ‘The Art of Computer Programming’

Donald Knuth’s 2018 Christmas Tree Lecture on Dancing Links — and Organ Music

Donald Knuth’s 2017 Christmas Tree Lecture Tackles a ‘Curious Problem’ in Combinatorial Geometry

---