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

规则就这三条：

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

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

一个小型 Kakuro 谜题示例

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

手推一遍

用一个 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

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

Sum Table——组合数学的基石

在手推过程中，关键步骤是”找出和为 n、长度 k 的所有合法数字集合”。Kakuro 求解器需要对所有可能的 \((n, k)\) 预先建好这张表——这就是 Sum Table。

n-in-k 问题

正式定义：给定目标和 \(n\)（1 到 45）和格子数 \(k\)（1 到 9），找出所有从 \(\{1,\ldots,9\}\) 中选 \(k\) 个不同数字、使其之和等于 \(n\) 的子集。

Bitmap 枚举

Knuth 用位掩码（bitmask）来枚举：用一个 9 位整数 \(x\) 表示哪些数字被选中，第 \(i\) 位（从 0 开始）为 1 表示选了数字 \(i+1\)。

  • \(x=0b000000011=3\) 表示 \(\{1,2\}\)，长度 2，和 3
  • \(x=0b000000101=5\) 表示 \(\{1,3\}\)，长度 2，和 4
  • \(x=0b111111111=511\) 表示 \(\{1,2,\ldots,9\}\)，长度 9，和 45

遍历所有 \(3 \le x < 512\)（至少两位，最多九位），按 \((n, k)\) 分组，核心代码只需几行：

for mask in range(3, 512):
    count = bin(mask).count('1')
    sum_val = sum(i + 1 for i in range(9) if mask & (1 << i))
    C[(sum_val, count)].append(mask)

位运算天然保证了数字不重复（每位只有 0 或 1），枚举的总次数只有 \(2^9 - 3 = 509\) 次（排除了空集 0、单元素集 1 和 2），非常高效。

数据概览

运行 build_sum_table() 之后：

  • 总共 127 个 \((n, k)\) 对有合法组合
  • 41 个 magic block：这些 \((n, k)\) 对只有唯一一种数字组合
  • 最多 12 种组合，出现在 \((20, 4)\) 和 \((25, 5)\) 两处

Magic Block：解题的突破口

当 $$ C(n,k) =1$$ 时，这个 block 的数字集合完全确定，是约束传播的最佳起点。最极端的两个例子：
  • \((3, 2)\)：只有 \(\{1,2\}\)（1+2=3 是两个不同数字之和的最小值）
  • \((45, 9)\)：只有 \(\{1,2,3,4,5,6,7,8,9\}\)（九格必须填满所有数字）

完整的 41 个 magic block 构成了 Kakuro 求解的”免费约束”库。

Dual 性质

Sum Table 有一个优雅的对称性：如果把每个数字 \(d\) 替换为 \(10-d\)，一个和为 \(s\)、长度 \(k\) 的合法组合就变成了和为 \(10k-s\)、长度 \(k\) 的合法组合。两个 \((n, k)\) 和 \((10k-n, k)\) 的组合数完全相同，合法组合之间存在一一对应关系。这个对偶性意味着 Sum Table 天然关于 \(n=5k\) 对称。

下图是 Sum Table 的热图，颜色越深表示该 \((n, k)\) 的组合数越多：

Sum Table 热图：各 (sum, length) 对应的组合数量

XCC 编码——把 Kakuro 变成精确覆盖问题

有了 Sum Table，下一步是把 Kakuro 翻译成 XCC（带颜色的精确覆盖）问题，交给 Algorithm C 求解。

朴素想法的问题

最直接的想法：把每个 block 的所有排列都列举出来。一个 4 格 block 的组合可能有 12 种数字集合，每种集合有 \(4!=24\) 种排列，共 288 个选项；如果有多个这样的 block，选项数量组合爆炸。

Knuth 在 TAOCP 4B Exercise 430 的答案（answer 430d）给出了一个高效编码，利用 XCC 的颜色机制大幅压缩。

Knuth 高效编码

Primary items（主要项）：每个白格 \(c_{ij}\) 对应一个主要项，必须被精确覆盖一次，表示”这个格子恰好填一个数字”。

Colored secondary items（带颜色的次要项）：对每个 block \(B\)，每种可能的数字集合（bitmask）\(p\) 对应一个次要项 \(\langle B, p\rangle\)，其颜色表示该格子实际填入的数字。

Options（选项）：对每个格子 \((i,j)\)，设其所在横向 block 为 \(B_h\) （可能的 bitmask 集合为 \(P\)），纵向 block 为 \(B_v\)（可能的 bitmask 集合为 \(Q\)）。对每对 \((p \in P, q \in Q)\) 及其交叉数字 \(x \in p \cap q\)，生成一个选项：

\[c_{ij} \quad \langle B_h, p\rangle \mathbin{:} x \quad \langle B_v, q\rangle \mathbin{:} x\]

这里”\(\langle B, p\rangle \mathbin{:} x\)“表示次要项 \(\langle B, p\rangle\) 被赋予颜色 \(x\)。

Absorber 选项：对每个次要项 \(\langle B, p\rangle\)，生成一个吸收器选项：

\[\langle B, p\rangle \mathbin{:} 0\]

吸收器的作用是处理”未被任何格子选中的 bitmask”——XCC 要求每个次要项都必须有确定的颜色，吸收器给它一个特殊颜色 0 表示”此组合未被选用”。

颜色的关键作用

为什么把格子里的数字 \(x\) 作为颜色？

同一个格子 \((i,j)\) 属于横向 block \(B_h\) 和纵向 block \(B_v\)。从 \(B_h\) 的视角生成的选项携带颜色 \(x\)，从 \(B_v\) 的视角生成的选项也携带颜色 \(x\)——XCC 的颜色一致性约束自动保证：如果选了 \(B_h\) 的 bitmask \(p\) 且格子 \((i,j)\) 填数字 \(x\)，那么 \(B_v\) 也必须使用含 \(x\) 的 bitmask \(q\)，且在格子 \((i,j)\) 处同样填 \(x\).

这就是关键：用颜色表示数字，XCC 自动保证横纵 block 在交叉格的一致性，完全不需要任何额外的约束代码。

教学例题的完整编码

回到 3×2 的教学例题，逐步列出所有 items 和 options：

Primary items（6个）： \(c_{2,1},\ c_{2,2},\ c_{3,1},\ c_{3,2},\ c_{4,1},\ c_{4,2}\)

Secondary items：

  • H0 sum=3, len=2 → 唯一 bitmask \(\{1,2\}\) → 1 个次要项 \(\langle H0, 0\rangle\)
  • H1 sum=11, len=2 → 4 种 bitmask（\(\{2,9\},\{3,8\},\{4,7\},\{5,6\}\)）→ 4 个次要项 \(\langle H1, 0\rangle \ldots \langle H1, 3\rangle\)
  • H2 sum=4, len=2 → 唯一 bitmask \(\{1,3\}\) → 1 个次要项 \(\langle H2, 0\rangle\)
  • V0 sum=7, len=3 → 唯一 bitmask \(\{1,2,4\}\) → 1 个次要项 \(\langle V0, 0\rangle\)
  • V1 sum=11, len=3 → 5 种 bitmask（\(\{1,2,8\},\{1,3,7\},\{1,4,6\},\{2,3,6\},\{2,4,5\}\)）→ 5 个次要项 \(\langle V1, 0\rangle \ldots \langle V1, 4\rangle\)

格子 \((2,1)\) 的选项： H0 唯一 bitmask \(\{1,2\}\) 与 V0 唯一 bitmask \(\{1,2,4\}\) 的交集是 \(\{1,2\}\)，生成：

c_{2,1}  <H0,0>:1  <V0,0>:1    （格子填 1）
c_{2,1}  <H0,0>:2  <V0,0>:2    （格子填 2）

格子 \((2,2)\) 的选项： H0 bitmask \(\{1,2\}\) 与 V1 的 5 种 bitmask 分别取交集：

  • \(\{1,2\} \cap \{1,2,8\} = \{1,2\}\) → 生成 \(c_{2,2}\ \langle H0,0\rangle\mathbin{:}1\ \langle V1,0\rangle\mathbin{:}1\) 和 \(c_{2,2}\ \langle H0,0\rangle\mathbin{:}2\ \langle V1,0\rangle\mathbin{:}2\)
  • \(\{1,2\} \cap \{1,3,7\} = \{1\}\) → 生成 \(c_{2,2}\ \langle H0,0\rangle\mathbin{:}1\ \langle V1,1\rangle\mathbin{:}1\)
  • \(\{1,2\} \cap \{1,4,6\} = \{1\}\) → 生成 \(c_{2,2}\ \langle H0,0\rangle\mathbin{:}1\ \langle V1,2\rangle\mathbin{:}1\)
  • \(\{1,2\} \cap \{2,3,6\} = \{2\}\) → 生成 \(c_{2,2}\ \langle H0,0\rangle\mathbin{:}2\ \langle V1,3\rangle\mathbin{:}2\)
  • \(\{1,2\} \cap \{2,4,5\} = \{2\}\) → 生成 \(c_{2,2}\ \langle H0,0\rangle\mathbin{:}2\ \langle V1,4\rangle\mathbin{:}2\)

其他格子类似，再加上每个次要项各自的 absorber 选项。

Absorber 选项（共 12 个）： \(\langle H0,0\rangle\mathbin{:}0,\ \langle H1,0\rangle\mathbin{:}0,\ \ldots,\ \langle V1,4\rangle\mathbin{:}0\)

XCC 求解器最终会选出唯一一组覆盖所有主要项、颜色一致的选项，对应唯一解 \(2,1,4,7,1,3\)。

编码实现

代码结构非常清晰，三步完成：

C = build_sum_table()          # 预计算 Sum Table
puzzle = KakuroPuzzle.from_teaching_example()
solutions = solve_kakuro(puzzle, C)   # XCC 求解

solve_kakuro() 内部调用 solve_kakuro_with_labels() 将谜题翻译成 XCC 格式，再交给 DLX_C（Algorithm C 的实现）搜索，最后把解码结果转换成 \((r, c) \to \text{digit}\) 的字典。实现采用了与上节略有差异的变体：每个 block 用单个次要项（颜色 = 排列索引）而非每个组合一个次要项，无需 absorber，两者逻辑等价。

build_sum_table() 的核心循环：

def build_sum_table():
    C = {}
    for mask in range(3, 512):
        count = bin(mask).count('1')
        sum_val = sum(i + 1 for i in range(9) if mask & (1 << i))
        key = (sum_val, count)
        if key not in C:
            C[key] = []
        C[key].append(mask)
    return C

运行教学例题，输出：

求解结果：找到 1 个解

  2  1
  4  7
  1  3

Mini Kakuro（2×2 白格，线索 H0=3, H1=7, V0=4, V1=6）：

  1  2
  3  4

验证：H0: 1+2=3，H1: 3+4=7，V0: 1+3=4，V1: 2+4=6，全部正确。

完整代码见 kakuro.py，依赖同目录下的 dlx_colors.py，直接运行即可。

Pentomino Kakuro——跨界的彩蛋

Kakuro 本身已经足够有趣，但 Knuth 在 TAOCP 4B Exercise 402 还藏了一道彩蛋：Pentomino Kakuro。

谜题在一个 12×12 的格子上进行。格子里被划分成若干个 “cage”——每个 cage 的形状恰好是一种五格骨牌（pentomino）。12 种标准五格骨牌中，Knuth 选用了 10 个（F、I、L、P、T、U、W、X、Y、Z），每个骨牌形状对应一个 cage，cage 的名字就是骨牌的字母。

每个 cage 给出一个约束：cage 内所有格子的数字之和（或乘积）等于线索值，且 cage 内数字不重复。解题规则和标准 Kakuro 完全相同，只是 block 的形状从矩形条变成了任意五格骨牌形状。

Pentomino Kakuro：每个 cage 形如一种五格骨牌

这道谜题把两个完全不同领域的美丽事物拼在了一起：五格骨牌的形状约束和 Kakuro 的数字求和约束。我们在五格骨牌三着色一文里看到过骨牌的组合结构；这里，每个骨牌形状同时也是一道数字谜题的线索——形状即线索，视觉美与组合美融为一体。

XCC 编码完全可以处理这种不规则 cage：把每个 cage 的白格坐标列出来，把 cage 内的 \((n, k)\) 约束编码成 sum table 查询，其余步骤与标准 Kakuro 相同。

谜题设计——什么样的 Kakuro 是好题？

解题算法很直接，但设计一道好的 Kakuro 谜题却非易事。

随机填数很少唯一

Knuth 做过实验：随机取一张合法填写的 Kakuro 网格，统计满足这组线索的解的数量，平均大约有 75 个解，极少数情况下才能得到唯一解。谜题设计者需要精心选择线索和网格形状，才能让解唯一。

Magic Block 的价值

好题的设计往往从 magic block 出发。41 个 magic block 是约束传播的起点：如果谜题里包含若干 magic block，解题者（人或算法）可以立刻锁定这些 block 的数字集合，然后向周围扩散约束。缺少 magic block 的谜题往往有大量解，难以构成有趣的谜题。

对称性陷阱

对称设计的谜题几乎总有对称解。如果把所有数字 \(d\) 替换为 \(10-d\)，整个谜题依然合法（利用前面提到的 dual 性质）。因此，纯粹对称的网格布局会产生至少两个解，除非额外约束打破这种对称。

用 \(\pi\) 出题

Knuth 在 Exercise 435 里展示了一个用 \(\pi\) 设计 Kakuro 的方法：取 \(\pi = 3.14159265\ldots\) 的数字，用 31、41、59、26、53、58、97 作为线索值，构造一张有趣的谜题。\(\pi\) 的数字本身没有规律性，使得线索分布均匀，不容易被人直接推测出来。这类”数学常数 Kakuro”既有视觉上的趣味，也保证了足够的约束强度。

起源

Kakuro 最早出现在 1966 年 Jacob E. Funk 在 Dell Pencil Puzzles and Word Games 上发表的谜题中，当时叫做 “Cross Sums”。经过几十年演变，日本益智杂志将其推广为 Kakuro 这个名字（”加法”+”クロス（Cross）”的缩写），并在 2000 年代随数独热潮一起风靡全球。

Kakuro 的纯粹之处

回头看这一切：Kakuro 的规则极简，却能产生层次丰富的推导链。它不依赖语言（不像填字游戏），不依赖记忆（不像数独的某些变体），全部约束来自最基本的加法和”不重复”原则。

Sum Table 揭示了它底层的组合结构：127 个可能的线索类型，41 个 magic block，最多 12 种组合的对称热图——这些数字都蕴含在 9 个数字的集合里，完全由加法和排列决定。

一道好的 Kakuro 谜题，就是在这个组合结构里精心选取一条路径，使得每一步推导都严丝合缝，最终汇成唯一一个答案。

完整代码

kakuro.py 包含 build_sum_table()、KakuroPuzzle 类、encode_kakuro()、solve_kakuro() 以及教学示例和 mini kakuro 的 demo，依赖同目录下的 dlx_colors.py。

本系列的其他文章：