你一定见过填字游戏：一个方格，空白处填字母，横竖都要拼成单词。Kakuro 是它的数字版本——格子里填 1 到 9 的数字，横向和纵向的每段连续格子（称为一个 block）都要满足指定的求和约束，并且同一个 block 内的数字不能重复。

规则就这三条：

1. 每个白格填 1-9 中的一个数字
2. 同一 block 内数字不重复
3. 每个 block 的数字之和等于线索给出的目标值

下面这个小谜题展示了这些要素：

黑格上的斜线数字就是线索：斜线右下方是横向线索，左下方是纵向线索。

手推一遍

用一个 3 行 × 2 列白格的教学例题来说明推导过程：

        col1  col2
row2:    ?     ?    ← H0 横向线索 sum=3
row3:    ?     ?    ← H1 横向线索 sum=11
row4:    ?     ?    ← H2 横向线索 sum=4
         ↑     ↑
        V0=7  V1=11

第一步： 纵向 V0 的 sum=7，长度 3，digits 1-9 不重复。枚举一下：\(\{1,2,4\}\) 和 \(\{1,3,3\}\)（重复，不合法）……其实只有 \(\{1,2,4\}\) 满足条件。这是一个”魔法块”——数字集合完全确定。

第二步： 横向 H0 的 sum=3，长度 2，唯一组合是 \(\{1,2\}\)——又是魔法块。

第三步： 格子 \((2,1)\) 处于 V0 和 H0 的交叉。V0 的数字集合 \(\{1,2,4\}\)，H0 的数字集合 \(\{1,2\}\)，交集是 \(\{1,2\}\)，所以 \((2,1)\) 填 1 或 2。

第四步： H2 的 sum=4，长度 2，唯一组合是 \(\{1,3\}\)。格子 \((4,1)\) 也在 V0 里，V0 已经确定数字集合是 \(\{1,2,4\}\)，与 H2 的 \(\{1,3\}\) 取交集得 \(\{1\}\)。所以 \((4,1)=1\)。

第五步： 由 \((4,1)=1\) 知 H2 的另一格 \((4,2)=3\) （因为 1+3=4）。V0 剩余的两格 \((2,1)+(3,1)=7-1=6\)，且数字来自 \(\{1,2,4\}\setminus\{1\}=\{2,4\}\)，所以 \((2,1)=2,(3,1)=4\) 或反过来。

第六步： H0 sum=3，已知 \((2,1)=2\) 的话 \((2,2)=1\)；若 \((2,1)=4\) 则 \((2,2)=-1\) 不合法。于是唯一解是 \((2,1)=2,(2,2)=1\)，从而 \((3,1)=4\)。

第七步： V1 sum=11，格子 \((2,2)+(3,2)+(4,2)=1+(3,2)+3=11\)，所以 \((3,2)=7\)。验证 H1：\(4+7=11\)，正确。

唯一解：

2  1
4  7
1  3

人能推导，计算机如何系统化？

Read more

引言

用 12 块五格骨牌平铺 6×10 矩形共有 2339 种方法——但如果我要求相邻骨牌颜色不同，连角都不能碰，还剩几种？

这是《The Art of Computer Programming》Volume 4B 中的习题 7.2.2.1-277，难度评级 [25]（TAOCP 的评级范围 0–50，数字越大越难）。答案是：94 种，仅占约 4%。

Read more

引言

Donald Knuth 在《The Art of Computer Programming》Volume 4B 中提出了 Dancing Links (DLX) 算法——一种优雅地解决精确覆盖问题的回溯算法。本文将探讨习题 7.2.2.1-31 中提到的经典应用：五格骨牌平铺问题。

什么是五格骨牌？

五格骨牌（Pentominoes）是由 5 个单位正方形连接而成的多格骨牌。不考虑旋转和翻转，共有 12 种 不同的五格骨牌，通常用字母 F, I, L, P, N, T, U, V, W, X, Y, Z 来命名：

问题定义

经典问题：用全部 12 种五格骨牌各一片，能否精确平铺一个 6×10 的矩形区域？

这个问题可以推广到：

• 5×12 矩形
• 4×15 矩形
• 3×20 矩形

Read more