约束满足回溯

回溯与约束搜索 · HTML

数学 / 逻辑形态

dfs(partial_assignment)：若完整则输出；选择未赋值变量 x，遍历 domain(x) 中与当前约束一致的 v，apply(x=v)，传播/递归，再 undo。

识别信号

• 需要构造满足多项局部约束的棋盘、填数、分割或路径。
• 变量域有限且规模适合搜索。
• 部分赋值即可检测冲突。
• 要求具体 witness 或全部解。
• 可用 MRV、最受限变量或候选排序显著剪枝。

容易误判的相似信号

核心不变量

进入递归时 partial assignment 满足所有已激活约束，辅助集合/计数与赋值完全同步；被剪分支不可能扩展为合法完整解。

状态、转移与处理顺序

Python 骨架

def color_graph(graph, color_count):
    n = len(graph)
    color = [-1] * n
    def dfs(done):
        if done == n: return True
        candidates = [u for u in range(n) if color[u] < 0]
        u = max(candidates, key=lambda x: sum(color[v] >= 0 for v in graph[x]))
        forbidden = {color[v] for v in graph[u] if color[v] >= 0}
        for c in range(color_count):
            if c in forbidden: continue
            color[u] = c
            if dfs(done + 1): return True
            color[u] = -1
        return False
    return color if dfs(0) else None

正确性思路

1. 不变量使每个被尝试的部分赋值合法。
2. 对所选变量遍历所有当前合法值；任何完整解必给它其中一个值，所以不会漏解。
3. 只有立即违反约束或所有候选失败时返回失败；回滚恢复父状态，故找到的完整赋值合法且失败结论可靠。

复杂度

边界条件

• 空变量集
• 变量初始预填
• 无候选变量
• 自环/矛盾约束
• 求一个还是全部解
• 辅助状态回滚异常

错误模式

选择与排除规则

• 先找能在部分赋值时检测的局部约束。
• 封装 apply/undo 让状态原子同步。
• 优先最受限变量，再排序最有希望的值。
• 在使用通用搜索前排除 matching、SAT 特例或结构化 DP。

相关模板

原创微型例子

Recall prompts

• 回溯剪枝必须证明什么？
• 为什么 MRV 常比固定变量顺序快？
• apply/undo 应同步哪些状态？

我的补充