14 · 回溯与约束传播

⏱ 34 分钟 ｜ ⭐⭐ 同一个死局，三种方法分别在第 5、第 4、第 3 步发现它

🎯 一句话

回溯是「撞了墙才知道有墙」，前向检查是「看一步就知道前面有墙」，弧相容是「把删值的后果一路传下去，还没走就知道整片区域都是墙」。

三者用的是同一张澳大利亚地图，差别只在发现失败的时刻 —— 而早一层，剪掉的子树就小一个数量级。

🌲 一、回溯搜索：每层赋一个变量的深度优先

上一章说过 CSP 的赋值可交换。把这个性质用足就得到回溯搜索：初始状态 ＝ 空赋值； 后继函数 ＝ 挑一个未赋值变量、给它一个和已赋值变量不冲突的值；目标测试 ＝ 全部赋值且零违反； 失败时退回最近那个赋值的变量换值，值也用完了就继续往回退。

⭐ 这就是深度优先搜索，只是状态空间被「每层固定一个变量」压过一遍： 没这个压缩叶子有 $n! \cdot d^n$ 个，压缩后是 $d^n$ —— 7 变量 3 色是 $2187$，而不是 $\approx 1.1 \times 10^7$。

手算：在澳大利亚地图上跑一遍

变量按 WA → NT → NSW → Q → SA → V → T 赋值，颜色按 红 → 绿 → 蓝 试。

回溯：退回 Q，它只剩蓝可试（红被 NSW 占、绿被 NT 占），没有备选 → 继续退回 NSW。 NSW 改成绿，于是 Q = 红、SA = 蓝、V = 红、T = 红 —— 解出来了。

⚠️⚠️ 注意第 ⑤ 步的浪费：SA 其实在第 ④ 步 Q 取蓝的那一刻就已经无路可走， 可回溯要等到轮到 SA、真的去找值才发现。

⭐ 回溯只在「撞墙」时得到信息。 墙一直在那儿，它只是没往那边看。

⚠️ 讲义给的经验值：朴素回溯大约能解到 25 皇后，再大就趴窝。本章和下一章就是把这个数往上推。

⚠️ 这是个经验值，别当成硬边界：实测（本机、下一章第四节那套口径）静态序 20 皇后要 3,992,510 次试值、24 皇后 9,878,316 次， 而 25 皇后反而只要 1,216,775 次 —— ⭐ N 皇后的难度随 n 起伏，不是单调上升的， 所以「能解到几皇后」取决于你撞上哪个实例。真正稳定的差别是增长曲线，下一章那张表会看得很清楚。

🔦 二、前向检查：赋完值立刻去删邻居的值域

想法：给每个未赋值变量维护一份还剩哪些合法值的清单。每次赋值 $X = v$ 之后， 立刻把所有与之冲突的值从 $X$ 每个未赋值邻居的值域里删掉；任一值域被删空，就地回溯。

同一条路径，值域的变化是这样的：

⭐ 失败在第 ④ 步就暴露了，比裸回溯早整整一层。 实测这张地图上裸回溯要试 17 次取值，加前向检查只要 9 次；8 皇后差得更狠：876 次 vs 88 次。

⚠️ 但它有个明确的盲区

前向检查只做一件事：从「刚赋值的变量」推到「它的未赋值邻居」，一步，就停。 它从不检查两个都还没赋值的变量之间的关系。

看讲义给的这个局面 —— 搜索走到了 WA = 红、Q = 绿，此时 NT 只剩蓝（红被 WA 排除、绿被 Q 排除）， SA 也只剩蓝（同样两条）。每个值域都非空，前向检查报「一切正常」。可是 NT 和 SA 是相邻的 ——

⚠️⚠️ NT 和 SA 不可能都是蓝。这个局面已经死了，前向检查看不见。

原因很简单：NT 和 SA 之间那条约束两端都还没赋值，而前向检查只从已赋值的一端往外推。

🔁 三、弧相容与 AC-3

修补方法：别只从已赋值的变量推，把每一条约束都拿来反复过筛。

⭐ 弧相容：弧 $(X,Y)$ 相容 ⟺ $X$ 值域里每一个值 $x$，都能在 $Y$ 的值域里找到至少一个 $y$ 使约束成立。 找不到这样的 $y$，就把 $x$ 从 $X$ 的值域里删掉 —— 它永远不可能是解的一部分。

⚠️ 弧是有向的：$(X,Y)$ 相容不代表 $(Y,X)$ 相容。一条无向边要当成两条弧处理。

AC-3 算法

1. 把所有弧放进一个队列
2. 取出一条弧 $(X,Y)$，执行 REVISE：删掉 $X$ 值域里所有「在 $Y$ 里没有支持」的值
3. $X$ 的值域被删空 → 当前赋值下无解，失败
4. $X$ 的值域被删过（哪怕只少一个值）→ 把所有 $(Z, X)$ 重新入队（$Z$ 是 $X$ 的邻居且 $Z \ne Y$） —— ⭐⭐ 这一步就是「传播」：$X$ 少了一个值，本来相容的邻居可能就不相容了
5. 队列空 ＝ 每条弧都相容

⭐ 复杂度 $O(c\,d^3)$（$c$ ＝ 弧数，$d$ ＝ 值域大小）：每条弧最多重新入队 $d$ 次（每次都因为对面少了一个值，而值总共只有 $d$ 个），单次 REVISE 是 $O(d^2)$。

⭐ 手算：AC-3 怎么看穿前向检查的盲区

还是 WA = 红、Q = 绿 那个局面，其余值域全满。逐弧处理：

失败，而且是在一个变量都没有新赋值的情况下推出来的。

⚠️ 关键在最后一行：$(SA, NT)$ 会被处理，是因为第 3 行删掉 NT 的绿之后算法把它重新扔回了队列 —— 这就是第 4 步那条规则的价值。

⭐⭐ 本章的核心洞察

前向检查只看一步；AC-3 把删值的后果一路传播下去。 有时候还没开始搜，解就已经被推出来了。

数独就是最好的例子：把每行、每列、每宫的 AllDiff 拆成两两不等再跑 AC-3 —— 很多标着「简单」的题在传播结束时就已经填满了，一次分支都没有。 难题则会卡住，传播停下来时每格还剩两三个候选，这时才需要真正开始搜。 ⭐ 你用铅笔做的「这一格只能是 7」，干的就是 REVISE 这件事。

⚠️ 弧相容不完备

每条弧都相容 ≠ 有解。 最小的反例只要三个变量：$X, Y, Z \in \{红, 绿\}$ 且两两不等 —— 三个变量抢两种颜色显然无解，可每条弧都相容（$X$ 取红则 $Y$ 能取绿，反之亦然，每个值都有支持）， AC-3 一个值都删不掉，队列空了还报告「一切正常」。

⭐ 所以传播不能取代搜索，只能给搜索减负。（更强的路径相容、$k$-相容代价更高，通常不划算。）

🧰 四、把两者接进回溯，和它们的代价

回溯 + 前向检查是默认组合，开销极小；回溯 + AC-3（叫 MAC，维持弧相容）每次赋值后再跑一遍传播。

⚠️ 传播不是白来的。 讲义写得很直白：对某些问题弧相容能极大加速搜索，对另一些反而因为计算开销拖慢它。 经验：约束稠密、值域小、死局藏得深（数独、排班）→ 传播赚翻；约束稀疏（这张地图才 9 条边）→ 开销可能比省下的搜索还多。 ⭐ 工业求解器通常默认开前向检查，把完整 AC-3 留成可调选项。

一份能跑的求解器（回溯 + 前向检查）

from collections import defaultdict

AU = {"WA": ["NT", "SA"], "NT": ["WA", "SA", "Q"], "SA": ["WA", "NT", "Q", "NSW", "V"],
      "Q": ["NT", "SA", "NSW"], "NSW": ["Q", "SA", "V"], "V": ["SA", "NSW"], "T": []}
ORDER = ["WA", "NT", "NSW", "Q", "SA", "V", "T"]          # 正文手算用的那个顺序

def solve(order, base, nb, ok, fc=True):
    dom = {v: list(d) for v, d in base.items()}
    assign, st = {}, {"试值": 0}
    def bt():
        if len(assign) == len(order):
            return dict(assign)
        var = next(v for v in order if v not in assign)   # ⭐ 静态顺序，下一章换成 MRV
        for val in dom[var]:
            st["试值"] += 1
            if any(not ok(var, val, n, assign[n]) for n in nb[var] if n in assign):
                continue
            assign[var], cut, alive = val, defaultdict(list), True
            for n in (nb[var] if fc else []):              # ⭐ 前向检查：删邻居的值域
                if n in assign:
                    continue
                for x in [x for x in dom[n] if not ok(n, x, var, val)]:
                    dom[n].remove(x); cut[n].append(x)
                if not dom[n]:                             # ⭐ 值域空了，不用往下走
                    alive = False; break
            if alive:
                r = bt()
                if r:
                    return r
            for n, xs in cut.items():                      # 撤销时按原顺序还原值域
                dom[n] = [x for x in base[n] if x in set(dom[n]) | set(xs)]
            del assign[var]
        return None
    return bt(), st

ne = lambda a, x, b, y: x != y
print("地图着色：", *solve(ORDER, {v: ["红", "绿", "蓝"] for v in AU}, AU, ne))

qs = ["Q%d" % i for i in range(1, 9)]                      # ⭐ 换个问题只换三样：
qok = lambda a, x, b, y: x != y and abs(x-y) != abs(int(a[1:])-int(b[1:]))  # 变量、值域、ok
A, D = {a: [b for b in qs if b != a] for a in qs}, {a: list(range(1, 9)) for a in qs}
print("8 皇后 FC:", solve(qs, D, A, qok)[1], " 关掉:", solve(qs, D, A, qok, fc=False)[1])

在 Python 3.13 上实跑，输出 {'WA': '红', 'NT': '绿', 'NSW': '绿', 'Q': '红', 'SA': '蓝', 'V': '红', 'T': '红'} {'试值': 9} 和 8 皇后 FC: {'试值': 88} 关掉: {'试值': 876}。

⭐ 地图的解和上面手算的完全一致，9 次试值也和前向检查那张表对得上。 ⭐ solve 完全不知道自己在解什么 —— 变量、值域、一个 ok 函数，三样一换就是另一个问题。

🔗 这一章连到哪里

✅ 检查点

1. 回溯搜索的初始状态、后继函数、目标测试各是什么？「每层固定一个变量」把 7 变量 3 色的叶子数从多少降到多少？
2. 手算那条路径：死局在第几步、为什么？要退到哪个变量才有备选值？
3. ⚠️ 那个死局实际上在第几步就注定了？为什么裸回溯更晚才发现？
4. 前向检查具体做什么？早几层发现失败？地图和 8 皇后的试值次数各是多少对多少？
5. ⚠️ 前向检查的盲区是什么？用 WA = 红、Q = 绿 这个局面说清楚。
6. 弧 $(X,Y)$ 相容的定义是什么？为什么说弧是有向的？AC-3 哪一步是「传播」？$d^3$ 从哪来？
7. 在 WA = 红、Q = 绿 上手跑 AC-3，写出删值顺序，说明哪条弧最终判死、它为什么会被处理。
8. ⚠️ 举一个「每条弧都相容但无解」的例子。这说明了什么？什么时候用完整 AC-3、什么时候只用前向检查？

🛑 可以停在这里

⚡ 走神救援

回溯搜索 ＝ 每层固定一个变量的 DFS（空赋值起步，挑不冲突的值，失败就退回最近那个变量换值）。因为赋值可交换，叶子数从 $7!\times3^7 \approx 1.1\times10^7$ 压到 $3^7 = \mathbf{2187}$。⭐ 主线手算（顺序 WA→NT→NSW→Q→SA→V→T，颜色红→绿→蓝）：① WA=红 ② NT=绿 ③ NSW=红（邻居全没赋值，取第一个）④ Q=蓝（红绿都被占）⑤ 轮到 SA，三色全被邻居占光 → 死局；退回 Q 没有备选，退到 NSW 改绿才活，解是 WA红 NT绿 NSW绿 Q红 SA蓝 V红 T红。⚠️⚠️ 死局在第 ④ 步就注定了，回溯却要到第 ⑤ 步才发现 —— 它只在撞墙时得到信息。 前向检查：赋值后立刻删掉每个未赋值邻居值域里的冲突值，任一值域空就地回溯，失败提前到第 ④ 步。实测地图 17 次试值 vs 9 次，8 皇后 876 次 vs 88 次。⚠️ 盲区：只从已赋值的一端往外推一步，从不看两个都未赋值的变量之间。WA=红、Q=绿 之后 NT 和 SA 都只剩蓝，值域非空所以它报正常，可两者相邻、不可能都是蓝。⭐⭐ 弧相容补上这个洞：$(X,Y)$ 相容 ⟺ $X$ 的每个值都能在 $Y$ 里找到支持，找不到就删；弧有向，一条边算两条弧。AC-3：全部弧入队 → REVISE 删值 → 空值域即失败 → ⭐删过值就把所有 $(Z,X)$ 重新入队（这就是传播） → 队列空即全相容；$O(c\,d^3)$。同一局面手跑：$(NT,WA)$ 删红、$(SA,WA)$ 删红、$(NT,Q)$ 删绿、$(SA,Q)$ 删绿、$(NSW,Q)$ 删绿，最后 $(SA,NT)$ 把 SA 删空判死 —— 全程一个新值都没赋。⭐⭐ 核心洞察：前向检查只看一步，AC-3 把删值的后果一路传下去，很多标「简单」的数独在传播结束时就已填满、一次分支都没有。⚠️ 但弧相容不完备：三个变量两两不等却只有两色，显然无解，每条弧却都相容 —— 传播不能取代搜索，只能减负。⚠️ 代价也真实：稠密问题用 MAC 赚翻，稀疏问题开销可能超过收益，所以工业求解器默认只开前向检查。

下一节 👉 15-CSP的启发式.md

去那里的理由：本章的变量顺序是写死的 —— 而正是那个顺序亲手制造了第 ⑤ 步的死局。 下一章只改「先赋值谁、先试哪个值」这两件事，一行约束都不动： 同一张地图零回溯（本章这个顺序要回溯 2 次），16 皇后从 160712 次试值掉到 584 次。 ⚠️ 而且这两件事的挑选方向正好相反 —— 那是全章最容易搞反的一点。