高德纳讲座：骑士巡逻之旅的算法探秘与模式之美
总结：
骑士巡逻图案
[
00:02:50
]
28种不同的“楔形”分类图
[
00:16:00
]
8x8棋盘闭合骑士巡逻总数达130亿的计算结果
[
00:32:29
]
具有最少钝角的独特骑士巡逻图
[
00:44:29
]
- 高德纳教授的讲座深入探讨了国际象棋中骑士巡逻（Knight's Tour）的悠久历史和计算挑战，展示了其在艺术设计和数学理论中的结合。
- 他介绍了创新的“普查（census）”方法，通过将复杂的巡逻分解为28种基本“楔形”，大大简化了计数过程，并利用并行计算解决了关于特定斜率分布的百年数学难题。
- 利用该方法，Knuth教授计算出8x8棋盘上闭合骑士巡逻的总数超过130亿，并发现了一个具有最少4个钝角的独特巡逻，称之为“稀世珍宝”。
- 讲座还探讨了不同角度和交点在骑士巡逻中的最小/最大出现次数，挑战了长期以来关于是否存在特定模式巡逻的假设。
- 此外，Knuth教授分享了“盲计数（blind counting）”算法，该方法能在不显式生成所有路径的情况下，高效计算大型棋盘（如8x32）上的汉密尔顿路径数量，展示了内存优化和并行处理的重要性。
- 最后，他介绍了“旋转巡逻（whirling tours）”的奇特现象，即骑士始终以逆时针方向绕棋盘中心移动的巡逻，并展示了在NxN棋盘上（N为4的倍数且N>24）存在N线圈旋转巡逻的构造。
引言与骑士巡逻的魅力 [00:00:00]
高德纳（Donald Knuth）教授在其第29届年度圣诞讲座中，深入探讨了国际象棋骑士巡逻（Knight's Tour）这一图论中的古老问题，及其在现代计算机科学中的新发现。
- 讲座背景与高德纳教授的贡献
- 高德纳教授因对计算机科学基础的杰出贡献而获得奖项。
- 他与斯坦福大学图书馆合作，修复了早期讲座录音，并可在YouTube上观看。
- 骑士巡逻的定义及在计算机科学系的艺术展示
- 骑士巡逻是指骑士在棋盘上移动，访问每个格子且不重复，最终回到起点（闭合巡逻）。
- 骑士的移动规则：L形移动，即“走二格，拐一格”。
- 凯尔特结图案：骑士巡逻在艺术设计中的应用。
骑士巡逻的历史与数学挑战 [00:07:18]
骑士巡逻问题拥有超过1200年的悠久历史，其研究甚至早于许多人认为的图论起源——欧拉（Euler）的七桥问题。
- 图论的起源
- 许多人认为图论始于欧拉关于欧拉环游的论文，但骑士巡逻的历史可追溯到1200多年前。
- 历史上的研究
- 骑士巡逻的记载在800年代就出现在克什米尔和波斯的手稿中。
- 印度在1300-1500年代也有相关著作。
- 1700年代，欧拉发表了关于骑士巡逻的重要论文，标志着该领域研究的兴盛。
- 到1800年，已有约30多篇关于该主题的重要论文。
- 早期问题
- 最初的问题是：骑士巡逻是否可能？
- 1800年代，人们开始意识到可能存在多种巡逻方式，并开始思考其数量。
- Knuth教授提到一个魔术技巧，通过记住一个骑士巡逻，可以在64步内以最慢的方式捕捉到另一个棋子。
- 1891年提出的未解问题 [00:10:00]
- Knuth教授在1973年休假期间开始研究骑士巡逻，偶然发现了一个由Palanteier将军在1891年提出的未解决问题。
- 该问题询问：是否存在一种骑士巡逻，其64步中，每种可能的4种斜率（+2, +1/2, -1/2, -2）各出现16次？
- 当时，数学家Labernet估计，如果每页能画50个巡逻，需要10000令纸（一令500张）才能记录所有巡逻。
普查方法：利用楔形分析 [00:15:55]
Knuth教授为了解决Palanteier将军的问题，提出了一种名为“普查（census）”的计算方法，通过分析每个格子的“楔形（wedges）”来分解问题。
- 楔形的概念
- 每个格子有8种可能的骑士移动方向。
- 对于一个已确定的巡逻路径，每个格子会有一个进入的移动和一个离开的移动。
- 这意味着每个格子有8选2，即28种可能的“楔形”组合。
- Knuth教授为这些楔形赋予了字母名称 (a, b, c... A, B, C...) [00:16:27]。
- 这些楔形代表了不同的转角角度：37°、53°、90°、127°、143°和180°。
- 利用对称性进行优化 [00:17:17]
- Knuth教授提出了一种节省计算量的方法：通过分析棋盘中心四个格子的楔形组合，将所有骑士巡逻分为不同的“簇（bunch）”。
- 每组巡逻可以通过旋转和翻转产生八种变体，通过选择字母顺序最小的“规范簇（canonical bunch）”，可以将计算量减少约八分之一。
- “小a”楔形（在角落形成一个短循环）可以被忽略，因为其无法形成完整的巡逻，进一步将可能性从28^4减少到27^4。
- 伯恩斯坦引理（Bernstein's lemma）表明，规范簇的数量为66771个。
- 并行计算 [00:27:03]
- Knuth教授利用家中计算机的8个核心，以及斯坦福大学信息实验室提供的832个核心（26台机器，每台2个CPU，每个CPU16个核心），并行处理这67000个问题。
- 这种大规模并行计算将原本可能需要数月的工作缩短到几天。
- 结果显示，在一个特定的规范簇（H W Z L）中，发现了180万个巡逻，其中有228,000个满足Palanteier将军提出的每种斜率各16步的要求，从而解决了这一长期未解的问题 [00:26:01]。
计算骑士巡逻的总数 [00:31:10]
通过普查方法和大规模计算，Knuth教授验证了8x8棋盘上闭合骑士巡逻的总数。
- 总数公布
- 8x8棋盘上的闭合骑士巡逻总数为13,053,556,128个 [00:31:24]。
- 这个数字最初由Brendan McKay在1997年计算得出。
- Knuth教授的普查方法再次验证了这一数字，他表示每次普查都必须得到这个结果，否则程序就有问题。
- 完全平衡的巡逻
- 统计结果显示，其中有10,000,677,720个巡逻是“完全平衡”的，即每种斜率的移动次数均为16次，占总数的约1/128。
角度和交点的优化分析 [00:37:22]
Knuth教授和合作者对骑士巡逻中不同类型的角度和交点的最大/最小出现次数进行了详细分析。
- 角度优化
- 交点分析
盲数法：计算汉密尔顿路径/环 [00:56:02]
除了普查计数所有巡逻并分析其属性，Knuth教授还讨论了“盲计数（blind counting）”方法，即在不显式生成所有巡逻的情况下，直接计算其数量。
- 动态汉密尔顿环算法
- Brendan McKay在1997年计算总数时，就是使用了盲计数方法，无需逐一可视化所有巡逻。
- “n-配置”与“前沿（frontier）” [00:57:22]
- 算法通过逐步在一个棋盘上添加格子（“n-配置”）来构建路径，同时跟踪“前沿”，即已覆盖区域与未覆盖区域的边界。
- 每个配置都有一组边，满足：1) 小于等于n的顶点被两条边覆盖，2) 边连接的顶点至少一个小于等于n，3) 无环。
- 骑士图的前沿通常包含17个元素，而计算路径时则有18个。
- 内存需求与计算挑战
- 计算结果
- 8x32棋盘上的汉密尔顿路径数量已被计算出来，并已添加到在线整数序列百科全书。
旋转巡逻：特殊的骑士巡逻 [01:18:18]
Knuth教授还介绍了“旋转巡逻（whirling tours）”，这类特殊的骑士巡逻路径，其移动方向总是相对中心呈逆时针旋转。
- 定义与特性
- 旋转巡逻要求骑士的每一步都相对于棋盘中心保持逆时针方向移动，从不“回头”。
- 线圈（coils）：巡逻路径穿越假想的垂直线的次数。
- 8x8棋盘上有1120个旋转骑士巡逻，所有这些巡逻都有7个线圈。
- Knuth教授曾尝试构造一个具有N线圈的NxN旋转巡逻，但未能成功证明其存在性。
- 存在性证明
- 对称性巡逻
Q&A: 对骑士巡逻的持续热情与未来探索 [01:25:39]
问答环节中，Knuth教授分享了他对骑士巡逻持续研究的动机，以及该领域的未来研究方向。
- 持续研究动机
- Knuth教授表示，驱动他持续研究骑士巡逻的动力，是其内在的“纯粹美感”，以及在数学和计算机科学中寻找模式和美感的乐趣 [01:45:04]。
- 他认为，就像欣赏音乐和诗歌一样，数学和算法也能带来独特的审美体验。
- 他还喜欢分享这些美丽的发现，让更多人欣赏。
- 新问题方向与未来探索
- 三维骑士巡逻：听众提问是否考虑将研究扩展到三维棋盘，Knuth教授指出Vandermond曾扩展到三维，并提到了一个4x4x4的骑士巡逻，这是一个未解决的计数问题 [01:35:20]。
- 不同移动模式的骑士巡逻：他表示也可以研究具有不同移动模式的骑士巡逻。
- Knuth教授强调，虽然普查方法解决了许多长期开放的问题，但这并没有“扼杀乐趣”，反而开启了更多对不同棋盘形状、推广形式和“旋转国王巡逻（whirling kings tours）”等新世界的探索。
- “理论、实践与乐趣”：Knuth教授的工作哲学 [01:50:34]
- 他分享了自己的工作方法：每天优先处理那些“最不愿做但又必须做”的问题，以避免拖延。
- 他将自己的研究生涯总结为“理论、实践与乐趣”的结合，强调在严谨的学术工作中追求美感和创造力。
- 他的朋友Siobhan Roberts正在编辑一本关于Knuth教授生平与计算机科学发展的书籍，其标题正是“理论、实践与乐趣”。