你一定见过这种东西:

C A N T O R
G A U S S .
E U L E R .
A B E L . .
. . . . . .
. . . . . .

一个字母方格,藏着若干单词——横着、竖着,有时候斜着。找到它们是游戏,但出这道题才是有趣的工程问题:给你几个单词,怎么把它们都塞进格子里?

这件事比看起来难。单词可以斜放,可以反向,两个单词可能在某个格子相交——相交处的字母必须相同。暴力枚举所有摆法代价太大,还容易遗漏。

这篇文章介绍一种优雅的做法:把”出谜题”变成一个填色游戏,然后用舞蹈链算法自动求解。顺带揭露一个很容易写错的细节——以及 Knuth 用来修复它的一个小技巧。

阅读全文


引言

一个宋朝就有文献记载的传统玩具,和现代 5G 手机的信号调制算法,共享着同一个数学结构——你信吗?

前面几篇我们一直在和精准匹配、Dancing Link 打交道,解决的核心问题是”在组合空间里找满足条件的子集”。这篇换个方向——不是挑选,而是遍历:怎样把所有 n 位二进制串走一遍,而且每一步只改变一个 bit?

答案藏在一个中国传统智力玩具里。

阅读全文


引言精准匹配和 Dancing Link 里我们用的都是标准精准匹配:每一项(item)必须被恰好覆盖一次。这个约束很整洁,但现实问题经常不那么整齐。智慧珠那类问题天然吻合——每块形状用且仅用一次,每个坐标被填满恰好一次。但换一个问题就卡住了:N 皇后要求每一行、每一列恰好放一个皇后——这还是精准匹配;但对角线上最多一个皇后,而不是”恰好一个”。棋盘边缘有很多对角线根本不需要被占据。标准 DLX 对”最多一次”没有干净的表达方式,只能靠手工预处理凑合——远不够优雅。Knuth 在 TAOCP 4B 里给出了解决方案:次要项(secondary items)和颜色(colors)。这两个扩展一起构成了 Algorithm C,把...

阅读全文


引言

2025 年 12 月,87 岁的 Knuth 在斯坦福做了他的第 29 届圣诞讲座,主题是骑士巡游(Knight’s Tours)。台下的人估计没想到,这老爷子 1973 年就开始研究这个问题,找了五十多年才把当年的笔记翻出来,在 2025 年做出了新的突破——把 8×8 棋盘上所有满足 180° 旋转对称的封闭巡游数清楚了:2,432,932 个,占全部封闭巡游的不到 0.1%。这个数字是怎么来的,后面慢慢说。

这篇文章是 TAOCP 系列的续集。我们已经聊过精准匹配、Dancing Link 和回溯算法,骑士巡游是把这些东西串起来的绝佳例子——它是一个哈密顿路径问题,但 Knuth 有个漂亮的技巧把它变成精准匹配。

阅读全文


整理博客归档的时候,偶然翻到了十年前写的一篇笔记——Learning how to learn。那是我在Coursera上完同名课程后整理的要点,当时不知道怎么想的,居然只用英文写了。

正好最近我的博客加上了中英文切换功能,每个主题可以同时存在中英文两个版本,访客可以根据自己的语言偏好阅读。既然基础功能已经搭好了,那就把这个坑填上吧。

阅读全文


博客信息与导航