一块木头日历，
拆成一个精确覆盖问题
下面每一节都可以点。转一转积木、跑一遍搜索、看两种算法赛跑——比读十页伪代码管用。
01一道被低估的题
木板上印着 12 个月、31 天、7 个星期，一共 50 个格子。配十块形状各异的木片，合计 47 格。 每天把木片铺进去，只让"今天"的月、日、星期露在外面。
规则一句话说得完，但它同时踩中了三个经典概念的交叉点：多联骨牌铺砌、精确覆盖、约束回溯。 更妙的是规模刚好——小到能在脑子里建模，大到不能靠蛮力。
先看清楚棋盘。8 行 × 7 列，但有三处不是格子：第 1、2 行最右边各缺一格，第 8 行左边四格是实心板（印着标语）。所以 56 − 6 = 50。
这 50 格的分工有讲究：12 个月占顶部两行，31 天接在下面五行， 7 个星期则沿右下角绕了半圈——第 6 行右端四格、第 7 行右端三格。
顺序是日、一、二、三、四、五、六（中文习惯），不是"一二三四五六日"。 差这一格，"星期二"就会落在完全不同的位置——照着国际版盘面来摆，必然错位。 本页所有计算都按下面这张图来。
整块板的构成：深色是先天实心板，不能放木片
12 + 31 + 7 = 50
02把格子变成数字
写搜索之前，先做一件更划算的事：把整块板压成一个整数。 50 个格子按行编号 0–49，每个格子占一个二进制位。把鼠标移到下面任意一格上看看。
悬停任意格子 → 看它对应第几位
这么做之后，三类操作全部退化成一个指令：放下一块是与运算，判断重叠是与运算， 求还剩哪些空格也是与运算。一次 CPU 指令代替五十次数组遍历——这就是为什么这类题一上来就要谈位运算。
03一块积木的八张脸
朝向不是"看两眼数出来"的，是算出来的。把一块拼块写成一组坐标 (行, 列)，然后：
- 旋转 90°：
(r, c) → (c, −r)，连做四次回到原样 - 翻面：
(r, c) → (r, −c)——木片是双面的，不翻就用不全 - 去重：把每种结果平移到左上角、按坐标排序、拼成一个字符串，重复的自然合并
4 次旋转 × 2 种翻面 = 8 个候选形状，但对称的会撞车：有一条对称轴的只剩 4 种， 转 180° 和自己重合的也只剩 4 种，2×3 长方形只有横竖 2 种。只有真正"手性"的那几块 （转过来和镜像不是同一个东西）才保得住完整的 8 种。
选一块，然后转它、翻它
这块算出来的全部朝向（点一下可以直接切过去）
十块加起来：54 种朝向（不是 10×8=80，也不是 46——46 是 8 块标准版的数字）。 每一块具体剩几种，下面这张表是程序算出来的，不是估的。
04从朝向到候选
朝向只说明"这块长什么样"，还说不了"它能待在哪儿"。一个候选 = 一块积木 + 一个朝向 + 一个平移量， 并且落下去必须同时满足两条：不出界、不压到那 6 个根本不是格子的地方。
做法很笨，但足够快：对每个朝向量出它的外接框 h × w，然后试遍
(8−h+1) × (7−w+1) 个平移量，压到实心板或越界的直接丢掉。
比如 3×2 的朝向有 6×6 = 36 个落点，2×3 的有 7×5 = 35 个；边角挡掉一些，实际数字比这更小。
选一块，看它在整块板上所有能待的位置。颜色越深，说明那个格子被这块的不同摆法反复踩到
这就是"一块积木的全部可能性"。十块各算一遍，加起来才是候选池。
十块逐个结算：
| 拼块 | 格数 | 朝向 | 板上位置 |
|---|
合计 54 种朝向、1,466 个候选。这个数比"朝向 × 落点"的理论值小一截， 差额就是被实心板挡掉的那些位置。
为什么要在这一步就穷举干净？因为搜索阶段只应该做一件事：挑。把所有"物理上放得下"的摆法提前算好、编好号， 后面每走一步就只是从表里取一行，不用再判断形状对不对。这是典型的预处理换搜索速度。
05精确覆盖
到这里，拼图已经被翻译成一个标准形式。把每个候选写成一行，每列代表"一个格子"或"一块积木"， 格子上填 1 表示这个候选占了它：
真实矩阵的 1,466 行里，随便取 8 行示意（橙 = 该候选覆盖此格）
左边是格子列（这里只显示前 30 列），右边单独那一列代表"这块积木被用掉了"
要求就两条：
- 47 个待覆盖的格子（50 减去留白三格），每列恰好一个 1——不重叠、不留缝
- 10 块积木，每块恰好用一次
于是矩阵的规模是 1,466 行 × 57 列：47 个格子列 + 10 个积木列。 留白三格不进矩阵——精确覆盖只表达"恰好一次"，表达不了"永远不要"，所以干脆不建那三列。
这就是 Knuth 说的 精确覆盖（Exact Cover）。听上去选择很多——1,466 行里挑 10 行， 组合数是 1019 量级。但注意，绝大多数的组合在第一行就矛盾了。
06搜索：试错的艺术
既然只能挑 10 行，那就一格一格地填：找出当前最靠前的空格，看哪些候选能盖住它，逐个试。 试不下去就退回来换下一个——这叫回溯。
点「开始」，你会看到它怎么一路试、怎么撞墙、怎么退。
演示日期：10 月 27 日 星期二（橙框三格为留白）
灰色 = 正在试（还没定）；实色 = 已放下；闪红 = 这条走不通，退回。
这个策略有个名字叫 first-empty-cell：永远处理"最靠前的空白"。它保证每次都在填最可能变成死角的地方， 一旦发现填不上，立刻回退，而不是等十块都摆完才发现漏了一格。
07剪枝：差三个数量级
同样是回溯，如果换一个顺序——按积木顺序一块块摆，每块试遍所有位置——会慢到什么程度？ 让两种策略同时跑同一道题（10 月 27 日 星期二）。
按积木顺序
一块一块摆，摆完再说
先填最前的空格
每次都在补最危险的那一格
节点 = 搜索树里访问过的分支数。这个数字直接决定要等多久。
点一下上面那个按钮，两边的数字会一起开始跳。剪枝那侧几百个节点就停住了， 暴力那侧要涨到千万级——按耗时算，差了三个数量级。 同一道题、同样的规则，区别只在于"多早承认自己错了"。
差别不在"算法"本身，而在什么时候发现自己错了。暴力要等十块摆完才知道铺不满；先填空格则在第一个格子无解时立刻放弃，把整棵子树一次性砍掉。
参考：同一道题用 Python 跑，剪枝侧 2,486 节点 / 15 毫秒；暴力侧跑到 93 秒、3,000 万节点还没找到。 不同实现的绝对数字会变，量级差距不会。
08数据与边界
把 366 天 × 7 个星期全部跑一遍：
| 指标 | 数值 |
|---|---|
| 组合总数 | 2,562 |
| 全部有解 | 2,562 / 2,562 |
| 单次求解（找第一个解） | 6–25 ms |
| 全部解枚举（同一天） | 10–13 秒 |
| 某一天的解数范围 | 129 ~ 3,304 |
还有两个反直觉的地方值得记一笔。解多不等于好拼：10 月 23 日有三千多个解，但人照样可能半天摆不出来—— 因为可选位置也多。反过来，10 月 27 日星期四只有 129 个解，程序也得搜得更久。
难度分布是有结构的：每月 26–28 日附近普遍更紧，因为那几格挨着日期区和星期区的交界， 一留白就形成凹角，能塞进去的形状骤减。这类"结构性难点"靠手感是摸不出来的，跑一遍才有。
再往下可以玩什么
下面三节，把这三条各展开一次。
- 换成 DLX。把 1,466×57 的 0/1 矩阵交给 Dancing Links，对比节点数——能直观看到"按列选最少"和"按格选最前"的细微差别。
- 从求解转向出题。给定一个完整铺法，反推它能露出哪些日期；反过来，按每天解数给拼图排难度序。
- 数本质不同的铺法。把十块看作带标号的，用 Burnside 引理能估出考虑对称性之后有多少种真正不同的摆法。
09换个引擎：DLX 与"先试哪一列"
回到那张矩阵。1,466 行，每个候选一行；57 列，由两部分组成： 47 个"待覆盖的格子" + 10 个"这块已经用过了"。
为什么不是 50 列？因为留白那三格根本不该进矩阵。精确覆盖要求每列恰好一个 1， 而"这一列永远是 0"是它表达不了的条件——所以建表时直接把这三列砍掉，不参与求解。 （候选的位掩码仍然按 50 位算，因为放下之前得先检查它有没有压到留白。两处宽度不同，是有意的。）
搜索每一步其实在做两个选择——挑一列（一个还没盖住的格子）， 再挑一行（一个候选）去盖它。挑哪一列，决定了这棵树有多胖。
同一道题（10 月 27 日 星期二），三种挑法，点一下现场跑：
节点 = 访问过的分支数；耗时 = 真实墙钟时间，包含"挑列"本身的开销。
注意第三行的反直觉处：MRV 只走了 53 个节点，是最靠前空格那条的七分之一， 可耗时反而更长——因为它每次都要把全盘 47 个格子扫一遍、逐个清点可用候选，这笔"选列税"比省下来的节点还贵。
DLX 存在的意义，就是把这笔税免掉。它把矩阵存成十字双向链表：每列一个表头，每行串成环。 删除一列、恢复一列都是 O(1) 的指针改写，不需要任何扫描。只有这时候， "选剩余 1 最少的列"才真正便宜，MRV 的优势才兑现——数独求解器几乎清一色用 DLX，就是这个原因。
| 挑法 | 节点 | 耗时 | 说明 |
|---|---|---|---|
| 按积木顺序 | 52,236,681 | ≈ 50 s | 块摆完才发现铺不满 |
| 最靠前的空格 | 399 | 3.4 ms | 本页用的策略 |
| 候选最少的空格（MRV） | 53 | 4.2 ms | 节点最少，但选列太贵 |
所以 DLX 不是"另一个算法"，它是同一套回溯的更快骨架 + 更好的分支顺序。你完全可以不用链表， 只把"选最靠前"换成"选最受限"，代价是每次选择都要扫一遍。规模越大，这笔账越偏向 DLX。
10从解到题：难度并不均匀
解完一天，很容易想问：哪天最难？把 12 个月 × 31 天 × 7 个星期全部跑一遍——2,604 个组合， 记录每个组合的搜索规模，就得到一张难度地图。下面这张是真实数据，不是示意图。 （这里按 12×31×7 算，含"2 月 30 日"这类不存在的日期——板上确实有 31 个日格，程序不知道谁真谁假； 只算真实日历时是 366×7 = 2,562 个。）
横轴是日期 1–31，纵轴是星期。颜色越深，程序找第一个解越费劲。
把 2,604 个格子看完，有三条规律是稳定的：
- 每月 26–28 日普遍最深。那几格紧挨着日期区和星期区的交界，一留白就形成凹角，能塞进去的形状骤减。
- 同一天换个星期，难度能差十倍。留白位置挪一格，剩下区域的可填充度就完全变了，跟"哪天"关系不大。
- 不是越靠后越难。最难的一档能到八万节点，最容易的只要十几个——由几何决定，不由日期大小决定。
"难度"在这里是对程序而言的搜索规模，不等于人的手感。人拼的时候还会受"哪块好拿、哪块形状好认"影响， 但两者大体同向：解越少的地方，人也越容易卡住。
11"有多少种解"取决于你怎么数
10 月 27 日星期二有 2,391 个解。这个数字不是随口说的，先把口径钉死，否则"多少种"根本没有意义：
- 块是带标号的。十块形状互不相同，所以"L 在左上"和"V 在左上"算两种解，不会混。
- 同一个几何铺法不会被重复计数。正因为块互不相同，每一组覆盖唯一对应一种块的分工。
- 板没有对称性。左上缺 2 格、左下缺 4 格，这两个缺口破坏了所有旋转和镜像对称——整体转一下，图就放不进这块板了。
每一格是一个完整铺法。它们覆盖的 47 格完全相同，只是十块的分工不一样。
如果换一块正方形、且积木里有两块同形，情况就不同了：整体旋转 90° 后的摆法在某些情况下要算同一个，
这时必须请出 Burnside 引理——数出"在某个变换下保持不变的摆法数"，再用
(1/|G|) Σ |Fix(g)| 求真正不同的轨道数。
这块板恰好一条都不满足：没有对称变换，块也两两不同。所以那套公式在这里退化成"什么都不用做"。 知道什么时候不用 Burnside，也是一种结论——但它成立的前提，是上面那三条你都验过了。