导读：今年，计算机作家克努斯另辟蹊径，分享了他最近在对骑士访问棋盘上每个方格的数万亿种方式进行分类和计数方面取得的突破。

“又到了一年一度的这个时候了！”斯坦福在线的邮件中如此写道。

唐纳德·克努斯（中文名字高德纳）将要迎来88岁生日，他在12月份初斯回到斯坦福大学，举办了他一年一度的“圣诞”特别讲座，这项传统他已经坚持了30多年。

这位斯坦福大学备受师生爱戴的荣誉退休教授提醒听众们，他仍在撰写《计算机程序设计艺术》——这是一本他已经创作了 63 年多的传奇作品（分阶段出版）。

但是在今年，他却走了一条不同寻常的路。

这位备受尊敬的数学与算法专家承诺将讨论：“图论中最古老的问题之一的最新突破，这个问题已经吸引了人们 1200 多年：‘一个骑士能否在不两次访问同一个地方的情况下覆盖棋盘上的所有单元格？’”

然而，在这个问题令人眼花缭乱的各种可能性背后，克努斯传递了一个重要的人生启示：

在所有数学和计算机科学的背后，他所追寻的其实是“美”。克努斯兴高采烈地翻阅着打印出来的答案，展示着他最喜欢的解法，就像展示他珍藏的雪花一样。

他以温暖与智慧，营造了一个恰如其份的圣诞节日氛围。

艺术与冒险

在斯坦福大学英伟达礼堂，一场演讲以一个好消息开场，主持人宣告过去演讲的录像已经全部修复！人们还创建了一个包含26场往年圣诞演讲的播放列表——最早可以追溯到20世纪90年代末——而克努斯的个人网页也链接到了他自1981年以来的其他视频合集。

展望2025年，克努斯开玩笑地告诉听众们：“我今晚得抓紧时间，因为——我今年经历了太多冒险。” 例如，克努斯的“新闻”页面还显示，今年6月，他庆祝了结婚64周年纪念日。

四月份，他还参与了母校克利夫兰凯斯西储大学计算机科学与技术系的盛大重开庆祝活动。

当人们问克努斯应该如何装饰墙壁时，克努斯建议采用“骑士巡游”这一图案——这个图案是通过描绘骑士走遍棋盘上每个方格一次的路径而形成的。

唐纳德·克努特在2025年之演讲

克努斯还与母校的设计团队合作，并在其网站上发表了一篇长达2200字的文章，解释了每面墙上呈现的数学概念。克努斯在其网站上称其“对我来说是一个激动人心的前景，因为我一直以来都是‘极客艺术’的拥趸”——克努斯曾在他的圣诞演讲中解释过这个概念。“这是一种左右脑的结合。你用一半的大脑知道它很漂亮，而另一半大脑则会说，‘这真是一个绝妙的设计。’”

这些内容在克努斯的《计算机程序设计艺术》一书中均有详细描述。然后，他在这次圣诞讲座中分享了一些精彩实例。

“纯粹之美”

克努斯说，他对《骑士之旅》的喜爱始于1973年，半个多世纪后，他终于找到了当年的笔记。

“当时我被一个未解之谜深深吸引，”他告诉听众们。他笑着继续说，尽管这个问题早在1891年就被提出，但至今仍未解开。

但克努斯也意识到，骑士巡游中每两步的组合都会形成一个角度或“楔形”——事实证明，识别出落在中间四个方格时形成的楔形“让我能够轻松地将所有骑士巡游分成大约八分之一的局面”。（因为每个解都可以沿四个方向之一旋转，或者翻转成镜像。）

克努斯谈到，这里有一个重要的教训：凡是能分类的，都可以计数。

在21世纪，克努斯编写了一个程序来进行这些“普查”——用来计算在给定中间四个方格中特定楔形组合的情况，总共会有多少个解。

克努斯著作的最新预印本（已出版的草稿）详细介绍了他所使用的“有趣”的数据结构，这些数据结构使他最终能够回答1891年首次提出的那个关键问题：对于骑士移动的四种可能的数学斜率，每种斜率都有16步的解有多少种？

精确答案是：103,361,771,080。

“其实找这些东西并不难，只是用手找不太容易！”

后来，克努斯说他收到“各种各样人士的来信，他们都对这个主题着迷……部分原因在于——我不知道，这些巡演本身就非常美，看着、看着就让人着迷。这就像在听你最喜欢的音乐——在某种程度上，它们之间是有一种韵律。”

在问答环节中，克努斯告诉听众们，一位数学家甚至为三维棋盘（每边四个方格）设计了骑士巡游。“它具有特别美丽的对称性。”

很快，他展示了一个更令人印象深刻的结果——骑士巡游问题所有可能解决方案的总数为：

13,267,364,410,532。

“我读本科的时候，以为我永远也算不出这个数字的答案。”（这个数字实际上是澳大利亚数学家布伦丹·麦凯在1997年首次计算出来的。）

亲切人物

这一切都在《计算机程序设计艺术：第 8a 册（哈密顿路径和循环）》中有详细的描述。但这仅仅是个开始。如果你画两条线连接骑士落脚的三个方格，它们当然会形成一个角，“很多人都在互相竞争，看哪条骑士巡游路线在行进过程中形成的 37 度角最多！”

“直到今年人口普查终于步入正轨，人们才知道实际上可以达到 29 岁。”

在这 130 亿次巡演中，只有 136 次达到了 29 的高度。

事实上，对于每一个可能的角度，我们现在已经计算出一个解中可以出现的最大数量——而克努斯对每一个都怀有美好的想法。

• 直角？“直到今年，最广为人知的直角是38度。但令人惊讶的是，人口普查员找到了用39度也能达到直角的方法。”
• 直线？“这有点神奇，因为早在1932年，罗马尼亚就有人找到了这个方程的最优解。” 最大值是19，只有112个解。
• “骑士巡游”谜题共有 56 种解法，其中使用了 42 个锐角。如果避免使用锐角，则可有 28,000 种解法。
• 钝角呢？最多有 47 个。“最令人惊讶的是，无论你走哪条路线，都至少要有四个钝角。你无法完全避免它们。”而且这四个钝角的解是唯一的。“在 13,267,364,410,532 条路线中，只有一条。而且我认为，这恰好也是你所能见到的最美的骑士路线之一。”
  
  

数学给了人们一种独特的美感，克努斯欣喜地向师生们展示了充满直线角或复杂对称楔形图案的解。

但这些解法中还蕴含着其他引人入胜的角度——例如骑士们行进路线交叉的线条。克努特展示了一位比利时数学家的图表，其中只有69处路径交叉。

克努斯本人称“多年前”在寻找对称解时，就发现了一条包含 126 个不同交叉路口的路线。（直到多年后他才知道这是独一无二的——在所有 13,267,364,410,532 个解中，它是唯一一条包含 126 个交叉路口的路线。）

他还展示了更多可能的解决方案——包括垂直交点最少的解决方案和垂直交点最多的解决方案。

答案是“全部”。有一种64步的解法，其中每一步都构成一个垂直交点的一部分。

要有光！

但所有普查中最复杂的一个问题是“我思考了30年的问题”。结果证明，这既是一次数学的伟大冒险，也是一次计算机科学的伟大冒险。

数学中包含一个“绕数”的概念——即曲线绕一个点一周的次数——通常用白色代表偶数，黑色代表奇数来表示。克努特的朋友 乔治·杰利斯曾精辟地指出：“我们可以用这种黑白模式来描述任何骑士巡游。”克努特著作的预出版册中包含了一些令人印象深刻的例子：

那么，最黑暗的巡演是什么？最轻松的巡演又是什么？

如果用他家里的电脑，克努特需要八个月才能计算出来。但幸运的是，一位斯坦福大学的同事借给他一套更好的设备——26台计算机，机器总共有832个内核，每台机器上都有两个16核的CPU。

“那种感觉真是太棒了！”他说道，引得听众一阵笑声表示赞同。“你们可以想象一下，我连续三天同时管理着800多个项目！”

旋转式收尾

如果那位坚定不移的巡游骑士总是逆时针绕着中心行进，正如克努特所说，“他从不后退！”

这并非不可能——在8x8的棋盘上，共有1120种走法。但克努斯展示了其中的规律。“当你观察这些路径时，你会发现它们可以分成许多圈，”每个完整的回路最终都会穿过一条“铅垂线”。

克努斯尝试用与棋盘边长相同的线圈数来绘制图案，并与保加利亚数学家尼古拉·贝卢霍夫合作。贝卢霍夫最终在一个 12×12 的棋盘上找到了这样的解决方案。随后，两人共同创作了一幅令人叹为观止的图。“我们提出的这个构造至少表明，对于所有大于 24 且为 4 的倍数的 N，都存在一个由 N 个线圈组成的‘旋转’骑士巡游。”

“但我后来又说，‘那如果试着找一个旋转90度后仍然对称的图形呢？’”

最后，作为压轴大戏，克努斯展示了他的最后一张幻灯片。如果这些图案是一堆雪花，那么这或许就是他最珍贵的收藏。它不仅螺旋圈的数量与侧放的正方形数量相同。“这是一个18×18的‘旋转’骑士环线，如果你把它旋转90度，它仍然是同一个环线。”

它就在那里——既是数学上的美，也是视觉上的美。“我觉得用这个来结束我的圣诞讲座很不错。在我看来，它就像一件很棒的圣诞装饰品。”

热烈的掌声响了起来。

作者：场长