国际象棋的马能不能不重复地走遍整个棋盘？这个问题看起来简单，但暴力搜索在 8×8 棋盘上根本跑不动——解的数量是 260 亿级别。
Knuth 2025 年圣诞讲座重新讲了这个问题，给出了一个非常漂亮的转化：不去想"走过哪些格子"，而是想"选了哪些步"，问题就变成了精准匹配，可以用 Dancing Links 高效求解。
看完这篇你会知道：
- 一个把"路径搜索"变成"集合覆盖"的思维转换，适用于很多类似问题
- 这个转化里藏着的坑——DLX 找到的解 99.98% 都是错的，为什么
- 一个只加一行代码就能从"封闭回路"扩展到"开放路径"的技巧
原文： https://morefreeze.github.io/2026/03/knight-tour.html 代码： https://github.com/morefreeze/morefreeze.github.io/blob/master/code/knight_tour.py
Select Language