约束满足问题

约束满足问题（Constraint Satisfaction Problem, CSP）是一类特殊的搜索与规划问题：不需要找最短路径，只需要给一组变量各赋一个值，让所有约束同时成立。前置阅读：搜索与规划、符号主义 AI 概览。

CSP 在符号 AI 中地位独特——它把”搜索”和”推理”融合在一起：变量赋值是搜索，而约束传播本质上是一种高效推理。一个 CSP 由三个要素定义：

变量集合 $X = \{X_1, X_2, \ldots, X_n\}$ ：需要赋值的对象。
值域集合 $D = \{D_1, D_2, \ldots, D_n\}$ ：每个变量 $X_i$ 可取的候选值集合 $D_i$ 。
约束集合 $C = \{C_1, C_2, \ldots, C_m\}$ ：限制若干变量取值组合的条件。一条约束涉及一组变量，并规定这些变量的取值组合中哪些是合法的。

目标是找到一个赋值（assignment）——给每个变量从其值域中选一个值——使得所有约束同时被满足。如果还需要最小化/最大化某个目标函数（如总成本），那就升级为约束优化问题（Constraint Optimization Problem, COP）。

核心直觉

CSP 的本质是填空游戏——给每个空格填一个合法值，让所有规则都不被违反：

变量与值域（Variable & Domain，每个变量可取的所有候选值的集合）= 数独的每个格子是一个变量，每个变量能填的数字 1–9 就是值域。
约束（Constraint，限制变量取值组合的条件）= “同一行不能有重复数字""同一列不能重复""同一个九宫格不能重复”——这些就是变量之间的约束关系。约束可以是一元的（只涉及一个变量，如 $X_3 \neq 5$ ）、二元的（涉及两个变量，如 $X_1 \neq X_2$ ），或高阶/全局的（涉及多个变量，如 $\text{allDifferent}(X_1, \ldots, X_9)$ 要求九个变量互不相同）。
回溯搜索（Backtracking Search，深度优先地逐个赋值，遇到矛盾就退回上一步换值的策略）= 先随便填一个，发现后面走不通就退回来换一个值——本质是深度优先搜索（DFS）+ 剪枝。朴素回溯在最坏情况下要枚举所有组合，时间复杂度是指数级的 $O(d^n)$ ，所以需要下面这些技术来压缩搜索树。
前向检查（Forward Checking，赋值后立即删除邻居不兼容候选值的剪枝技术）= 每填一个值，立刻把相邻变量中不合法的候选值划掉——提前发现矛盾，避免一条路走到黑。它只做”一步向前”的检查，计算量小但效果显著。
约束传播（Constraint Propagation，反复利用约束删除不可能的候选值的过程）的核心是弧一致性（Arc Consistency，对每条约束弧反复删除无兼容值的候选值的状态），代表算法是 AC-3：反复划掉不可能的候选值，直到不再变化——有时候不需要任何搜索，光靠传播就能求解或判定无解。

原理图解

CSP 求解流程：搜索 + 传播交替推进

一个完整的 CSP 求解器将”回溯搜索”和”约束传播”交替执行：每次选一个变量赋值，然后做约束传播提前发现矛盾：

约束传播 AC-3 的核心思想

AC-3（Arc Consistency Algorithm #3）反复检查每条约束弧 (Xi, Xj)：如果 Xi 的某个值在 Xj 的值域中找不到任何兼容值，就把该值从 Xi 的值域中删除：

AC-3 的时间复杂度为 $O(e \cdot d^2)$ ，其中 $e$ 是约束弧数量， $d$ 是最大值域大小。对于很多问题，纯约束传播就能大幅缩小搜索空间，甚至直接求解。

动手实践

地图着色问题：回溯 + 前向检查

经典的地图着色 CSP——相邻区域不能同色。用纯 Python 实现 MRV 启发式 + 前向检查：

# 澳大利亚地图着色：7 个区域，3 种颜色，相邻不能同色
neighbors = {                       # 各区域的相邻关系
    "WA": ["NT", "SA"], "NT": ["WA", "SA", "Q"], "SA": ["WA", "NT", "Q", "NSW", "V"],
    "Q": ["NT", "SA", "NSW"], "NSW": ["SA", "Q", "V"], "V": ["SA", "NSW", "T"],
    "T": ["V"],
}
colors = ["红", "绿", "蓝"]

def forward_check(assignment, var, domains):
    """赋值后做前向检查：删掉邻居中同色的候选值"""
    new_domains = {k: list(v) for k, v in domains.items()}
    for nb in neighbors[var]:
        if nb not in assignment and assignment[var] in new_domains[nb]:
            new_domains[nb].remove(assignment[var])   # 删掉冲突值
            if not new_domains[nb]:                   # 值域空了 = 矛盾
                return None
    return new_domains

def backtrack(assignment, domains):
    """回溯搜索：MRV 策略（候选最少的变量优先）"""
    if len(assignment) == len(neighbors):             # 所有变量已赋值
        return assignment
    var = min((v for v in neighbors if v not in assignment),
              key=lambda v: len(domains[v]))           # MRV：选候选最少的
    for color in domains[var]:
        new_domains = forward_check({**assignment, var: color}, var, domains)
        if new_domains:
            result = backtrack({**assignment, var: color}, new_domains)
            if result:
                return result
    return None

init_domains = {r: list(colors) for r in neighbors}   # 初始值域：每个区域可选全部颜色
print(backtrack({}, init_domains))
# 输出示例: {'WA':'红', 'NT':'绿', 'SA':'蓝', 'Q':'红', 'NSW':'绿', 'V':'红', 'T':'绿'}

CSP 求解策略速查

策略	英文	核心思想	效果
最小剩余值	MRV (Minimum Remaining Values)	优先选候选值最少的变量赋值	快速发现矛盾，减少分支
最少约束值	LCV (Least Constraining Value)	优先选对邻居限制最少的值	保留更多后续可能性
前向检查	Forward Checking	赋值后立刻删除邻居的不兼容值	提前发现死路
弧一致性	AC-3	反复传播约束直到值域稳定	可能直接求解或判定无解
路径一致性	Path Consistency (PC)	考虑三元组的一致性	比 AC-3 更强的传播

实践要点

MRV 启发式是性价比最高的优化：选择候选值最少的变量优先赋值，能极大减少搜索分支数。对于数独这类问题，MRV 往往能让搜索树缩小几个数量级。
前向检查是最基本的剪枝：每次赋值后立刻检查邻居值域是否为空，比纯回溯快得多；AC-3 约束传播则更强，建议两者结合使用。
问题建模决定求解效率：同一个问题，添加冗余约束（如 all-different 可拆解为两两不等）或使用全局约束（如 allDifferent）可以让传播更有效。
SAT 求解器是 CSP 的强力后端：现代 CDCL SAT 求解器（如 MiniSat）在处理大规模布尔约束时极为高效，很多 CSP 问题转成 SAT 后反而更快。
混合方法：对于组合优化（不只是满足），可以用 CP 求解器找初始解，再用局部搜索（如模拟退火）优化。

典型应用

数独求解器：标准数独是一个经典的 CSP——9x9 格子的变量、1–9 的值域、行/列/宫的三类约束。任何回溯 + 约束传播求解器都能在毫秒级求解。相关推理基础见逻辑推理与知识表示。
N 皇后问题：在 NxN 棋盘上放 N 个皇后互不攻击，是 CSP 的教科书案例，用于验证约束传播算法的效率。
排课与排班：大学排课系统中，每门课的教室、教师、时间段都是变量，“同一教室同一时段不能排两门课""教师不能同时上两门课”等是约束。实际产品如 UniTime、Moodle 排课插件均基于 CP 求解器。
工业排程：工厂车间作业调度（Job-Shop Scheduling）是 CSP 的工业级应用，Google OR-Tools 和 IBM CP Optimizer 在此领域广泛使用。
配置与选型：PC 配置器（选 CPU/主板/内存时检查兼容性）、电信网络配置等场景中，产品配置规则就是约束。
生物信息学：蛋白质折叠、DNA 序列比对中的部分子问题可建模为 CSP。

典型类库与工具

类库	语言	说明
OR-Tools CP-SAT	C++/Python	Google 开源的 CP-SAT 求解器，将约束规划与 SAT 求解结合，性能极强
python-constraint	Python	轻量级 CSP 求解库，支持回溯和约束传播，适合教学和原型
Gecode	C++	高性能约束求解器，支持多种约束传播策略
Chuffed	C++	惰性子句生成约束求解器，学术前沿
MiniZinc	建模语言	声明式约束建模语言，可对接 Gecode、Chuffed、OR-Tools 等后端
Z3	C++/Python	微软研究院的 SMT 求解器，支持整数/实数约束，也可用于 CSP

术语表

术语	英文	解释
约束满足问题	CSP (Constraint Satisfaction Problem)	为一组变量赋值使其满足所有约束的问题
变量	Variable	CSP 中需要赋值的对象，如数独中的每个格子
值域	Domain	每个变量可取的所有候选值的集合
约束	Constraint	限制变量取值组合的条件，如”相邻不同色”
回溯搜索	Backtracking Search	深度优先地逐个赋值，遇到矛盾就退回上一步换值的策略
前向检查	Forward Checking	赋值后立即删除邻居不兼容候选值的剪枝技术
弧一致性	Arc Consistency	对每条约束弧反复删除无兼容值的候选值的状态
AC-3	AC-3 Algorithm	经典的弧一致性传播算法，时间复杂度 $O(e \cdot d^2)$
MRV	Minimum Remaining Values	优先选候选值最少的变量赋值的启发式策略
全局约束	Global Constraint	封装多个变量间复杂关系的预定义约束，如 allDifferent