高级 · coloring / AIC / 回溯

高级技巧：链，以及逻辑的尽头

到高级层，所有技巧都归到一个核心：链（chain）。链只有两种砖块：

强链（strong link）——至少有一个为真，非 A 即 B。来源可以是「某 house 里一个数只剩两格」，也可以是「某格只剩两个候选」。
弱链（weak link）——至多有一个为真，不能同真。典型来源是两格互相看得见。

本章从最直观的单数字着色出发，经双值格链，最后收在 AIC 这套统一语言上；当链也无能为力时，还剩最后一招——试错与回溯，那已经是机器解数独的办法。

1 · 着色法：单数字的真假二染色

盯一个数字，把强链连成的格子交替染两色，同色的格「同生共死」——最终必是一色全真、另一色全假。谁真谁假还不知道，但已经够删候选了。

强链连起来的两格非此即彼，一格是该数，另一格就不是。沿强链交替染色，于是同色格的真假完全一致：要么蓝色这组全是它，要么绿色那组全是它，两种情况必居其一。所以任何同时看得见一个蓝格和一个绿格的外部格，无论哪种情况成真都会与它冲突，因此绝不可能是这个数——这叫颜色陷阱（color trap）。

图 1-1 · 数字 9 的强链被交替染成蓝、绿两色；同时看见一蓝一绿的格落入颜色陷阱，删去 9。可单步观察染色如何沿强链展开。

另有一条对称的规则叫颜色矛盾（color wrap）：若同色的两格落进了同一 house，那这色必假，另一色直接全部为真。着色其实就是把 X-Wing 那种单数字结构拉成任意形状的网——X-Wing 与 Swordfish 是它的规整特例；多个数字一起染，就是 3D Medusa。

2 · XY-Chain：把连环拉成任意长

XY-Wing 是三个双值格的连环，XY-Chain 把它拉长成一串：每个格只有两个候选，相邻两格互相看得见且共享一个数，链的两端格都含同一个数 Z。结论与 XY-Wing 一致：沿链推下去会发现两端之中必有一个等于 Z，于是任何同时看见两端的格都不可能是 Z。

沿链推一遍即可验证。假设起点不是 Z，那它只能是另一个候选；相邻格因此不能取那个共享数，被迫取自己的另一个候选；如此逐格传递，最后把另一端逼成 Z。反过来，若起点本就是 Z，那这端是 Z。两种情况，总有一端等于 Z——这正是 XY-Wing「殊途同归」的加长版。

图 2-1 · 五个双值格首尾相接，两端都含 5；连锁推导把另一端逼成 5，同时看见两端的格因此删去 5。可单步观察推导如何沿链传递。

链里每个双值格内部是一条强链，格与格之间是弱链——强弱交替，正是下一节 AIC 的骨架。XY-Wing 就是长度最短（三格）的 XY-Chain。

3 · AIC：链的大一统

Alternating Inference Chain（交替推理链）是高级数独的统一语言：强、弱链严格交替、两头都是强链的链。推理规则极简——沿着「若这头假，顺链推，那头真」，得出两头不可能同时假。

图 3-1 · 同一条链改用强 / 弱链的眼光重看：每个双值格内部是强链，相邻格之间是弱链。可单步切换两种链的高亮。

强链可以来自格内（一格只剩两个候选）或 house 内（一个数只剩两格），弱链同理；不限定来源、允许任意交替，就得到最一般的 AIC。
技巧	链的样子	强链来自
X-Wing / 鱼	单数字、矩形或网	house 里某数只剩两格
着色 Coloring	单数字、长链	同上（conjugate pair）
XY-Wing	3 个双值格	双值格内部 {X,Y}
XY-Chain	n 个双值格	双值格内部
AIC	任意混合	两者都行

把链尾接回链头形成环，就是 Nice Loop；强链一端换成一组格，是 Grouped AIC；换成「几乎锁定数组」就是 ALS-AIC。到这里，人类数独技巧基本到顶——更难的技巧（Death Blossom、Exocet、SK Loop 等）要么是 AIC 的复杂组合，要么是针对极少数极端难盘的专用模式。

4 · 逻辑的尽头：试错、回溯与机器解法

如果链也找不到，还有最后一招，它永远可行：试错（trial and error，日式叫法 Nishio）。挑一个双值格，假设它填某个数，顺着推下去；若推出矛盾（某格无数可填），那这个假设就是错的，另一个值被迫成立。把这招系统化、配上「错了就退回上一步重试」，就是回溯（backtracking）。

图 4-1 · 假设双值格 r4c3 填 3，连锁推导在 r2c9 处推出「一个数都填不进」的矛盾，反证它只能是 1。可单步跟随推导链走到死路。

计算机解数独的核心正是深度优先搜索加回溯：选一个空格，逐个试它的候选，每填一个就用约束往下推；一旦走进死胡同就退回上一个选择点换下一个值。因为合格谜面解唯一，这棵搜索树一定能走到唯一的叶子。朴素回溯就能解任何数独，只是慢。

注 · 高效的实现会把数独转换成精确覆盖（exact cover），再用 Knuth 的 Dancing Links（DLX）搜索——用双向循环链表让「删一列 / 还原一列」都是 O(1)，回溯开销极低。本站另有一整个系列讲它：Dancing Links、数独归约成 exact cover。人脑靠逻辑「看出」答案，机器靠搜索「试出」答案——一道数独，两条路。

5 · 相关链接

SudokuWiki · Singles Chains (Coloring) · sudokuwiki.org——对应第 1 节：着色法的两条规则 color trap 与 color wrap。
SudokuWiki · XY-Chains · sudokuwiki.org——对应第 2 节：XY-Chain 的定义与更多例子。
SudokuWiki · Alternating Inference Chains · sudokuwiki.org——对应第 3 节：AIC 与 Nice Loops 的完整规则。
Dancing Links · 数独归约成 exact cover——对应第 4 节：机器解法的极致工程实现，回溯开销降到 O(1)。
综合实战：把技巧串成解题流程——四章技巧的取用顺序与难度的判据。