去年整理旧代码的时候翻出了一个早期用暴力回溯写的数独求解程序。当时觉得“能跑就行”但每次遇到困难题目都要试几万次节点实在谈不上优雅。后来接触到约束满足问题CSP和AC-3算法才意识到数独本身就是一个非常标准、非常漂亮的CSP建模对象完全可以用约束传播把绝大多数无用搜索提前剪掉。于是我用AC-3算法从一个更“知其所以然”的角度重写了解数独的程序这篇文章就把整个设计过程、核心原理、实现细节和踩坑记录完整写出来。适合已经会一点Python、想了解CSP到底怎么落地、或者想写一个面对困难数独也不发怵的求解器的读者。1. 数独建模为什么我选择把它当CSP处理1.1 变量、值域、约束一张表说清楚接触过约束满足问题CSP的读者都知道一个CSP由变量、值域、约束三部分组成。数独跟CSP的契合程度高得惊人把“填空”这件事翻译成CSP语言就是CSP组成数独中的对应变量81个格子每个格子是一个变量值域每个格子可填的数字初始都是{1,2,3,4,5,6,7,8,9}已知数字的格子值域就是单元素集合约束同一行、同一列、同一宫内的格子两两取值不能相同这样建模完之后求解数独就不再是“想办法填数字”而是变成了“在满足全部约束的前提下为每个变量找一个取值”的通用问题。这个视角的转换很关键因为一旦把问题形式化很多成熟的约束传播算法就能直接派上用场不需要我们为了“行宫列互异”去单独写一套特判逻辑。有人可能会问数独规则里行、列、宫都是九个数互不相同这是“全局约束”而AC-3算法处理的是二元约束两者能对上吗这恰恰是需要拆解的。任意两个位于同一行、同一列、同一宫的格子之间都存在一个“取值不能相等”的关系把行列宫的所有格子对枚举出来就得到了足够描述数独规则的全部二元约束。AC-3不关心这个格子对是“同行”还是“同宫”它只关心这两个变量之间有一条约束这就够了。1.2 全局“互异”约束如何拆成有向弧“有向弧”这个词第一次接触的人容易懵实际很简单对于任意两个变量x和y如果它们之间存在约束那么就有两条有向弧一条是(x, y)表示“x的取值要受y限制”另一条是(y, x)表示“y的取值要受x限制”。数独里每两个同行、同列或同宫的格子就是一对存在约束的变量。一个格子所处的行有8个邻居列有8个邻居宫里有4个不在同行列的邻居加起来平均一个格子大约有20个邻居。每个邻居关系对应一条双向有向弧。最后整个棋盘大约有1620条有向弧这个数量级对AC-3来说非常轻松。拆弧的时候有个小细节值得注意一个格子可能跟某个邻居既同行又同宫比如第一行左边宫内三个格子它们之间同时满足“同行”和“同宫”两种关系。从规则角度约束内容都是“两数不相等”所以它们之间只需要一条约束、两条有向弧不需要重复添加。因此后面实现邻接表时我会用set来去重避免同一条弧反复处理。1.3 传播与搜索的职责划分建模决定算法结构。我用AC-3算法求解数独的程序整体上分成了两层外层是回溯搜索选择一个尚未确定的格子尝试填一个数字不行就换一个再不行就回退。内层是AC-3约束传播每当一个格子的值域发生变化就把这种变化沿着弧扩散出去把所有能早发现矛盾、能直接确定的值都提前处理掉。AC-3承担的是“能算就尽量算出来”的职责回溯只在约束传播推到固定点、依然有格子没确定时才出手。这样设计的直接收益是很多简单数独跑完一遍AC-3就被完全解开了根本不需要进入搜索阶段困难题目也只需要极小的搜索空间。后面第4节我会给出一组实测对照数据能直观看出这个设计差距有多大。2. AC-3算法剥开看弧一致性到底做了什么2.1 一条弧的“一致性”该怎么理解AC-3的全称是Arc Consistency 3维护的是一种局部一致性叫弧一致性。一条有向弧(x, y)是弧一致的当且仅当x的值域中每个值都能在y的值域里找到一个至少不冲突的取值。这个定义光看太干我打个比方。假定x和y是坐在一张课桌两侧的两个学生约束是“两个人不能在同一时刻举手”。如果x当前可能举手的时间是{第1秒, 第4秒}y可能举手的时间是{第1秒, 第2秒}那么x的第4秒是安全的第1秒就危险了——如果x第1秒举手y只能在第1秒或第2秒举手里面总有一个时间会冲突。于是第1秒就不能再保留在x的候选时间表里。AC-3的revise操作干的就是这件事把x的值域里“在y的值域中找不到任何兼容值”的值删掉。删完之后如果x的值域正好只剩一个值那这个格子的数字就被确定下来了可以继续传播如果删到空说明当前局面已经不可能有解可以直接回溯或宣告失败。2.2 revise与队列为什么值域一改就牵连邻居AC-3的主循环维护一个队列队列里放的是所有待检查的有向弧。初始时把全部有向弧入队然后循环弹出弧(x, y)对这个弧做一次revise检查。如果revise发现x的值域有删减那么问题就来了x的值域变了所有“指向x”的弧之前做的检查可能就过期了因为这些弧原本依赖的是x的旧值域现在x少了几个候选值需要重新检查一次。所以代码里会把所有(z, x)重新加入队列其中z是x的邻居且z不等于y。这里可以用连锁反应来理解一个人改了身高跟他站在一起比较过的人都要重新再比一次而他之前比较过的人不受影响。AC-3这种“只把受影响的弧重新入队”的机制比每轮全量扫描所有弧要高效得多也正好体现了局部传播的精髓。整个循环持续到队列为空或者某个格子值域为空。队列为空意味着当前所有弧都已经达到一致性没有任何值会被继续删减此时AC-3的传播阶段结束。2.3 它能直接解出简单题却解不出难题AC-3的边界很多人第一次写完AC-3会误以为它能直接解开所有数独结果发现有些题目跑完格子还是空的就开始怀疑实现有问题。这不是bugAC-3维护的是弧一致性它比“单一候选数排除法”稍微强一些但本质上仍然是局部推理。数独里存在一类逻辑比如“这一行里数字7只能在某一宫出现”这类推理实际上涉及多个变量之间的联合关系超出了单条弧能覆盖的信息。因此AC-3处理不了的题目必须交给回溯搜索。理解了这一点你才不会在调试时做无用功。AC-3的定位是把搜索空间尽可能压缩而不是保证直接给出答案。简单题能被它直接解出来困难题只会把探索分支数量砍到极低这就已经达到设计目的了。3. 程序实现从棋盘到可运行的求解器3.1 邻接表与值域的数据结构程序里我用0到80的整数给81个格子编号编号n对应的行是n // 9列是n % 9。宫的计算略麻烦一点先算宫的行起始r0 (n // 9 // 3) * 3列起始c0 (n % 9 // 3) * 3然后对这个3×3小方块内所有格子编号。构建邻居集合的代码如下def build_neighbors(): neighbors [set() for _ in range(81)] for i in range(81): r, c i // 9, i % 9 # 同行同一行里除自己以外的8个格子 for j in range(9): if j ! c: neighbors[i].add(r * 9 j) # 同列同一列里除自己以外的8个格子 for j in range(9): if j ! r: neighbors[i].add(j * 9 c) # 同宫所在宫中除自己以外的格子 br, bc (r // 3) * 3, (c // 3) * 3 for dr in range(3): for dc in range(3): idx (br dr) * 9 (bc dc) if idx ! i: neighbors[i].add(idx) return neighbors值域我直接用Python的set表示已知数字的格子值域是单元素集合未知格子的值域是{1..9}。用set的好处是代码直观删值、判空、检查包含都很顺手。虽然它不是性能上最极致的选择但第一版求解器最重要的是逻辑清晰性能优化放到后面再谈。3.2 AC-3实现代码revise函数负责检查一条有向弧(x, y)遍历x当前的所有候选值逐个判断在y的值域里能否找到不等的兼容值。一个候选值vx能找到兼容值条件是y的值域中存在某个vy不等于vx。如果找不到说明vx在当前状态下是死路要从x的值域里删掉。注意遍历集合时不能边遍历边删除我先收集保留的值最后一次性重建集合这样最稳。def revise(domain, x, y): if not domain[y]: return False, True # y已经为空冲突 retained [] removed False for vx in domain[x]: if any(vy ! vx for vy in domain[y]): retained.append(vx) else: removed True if removed: domain[x] set(retained) if not domain[x]: return False, True # x也被删空 return removed, False这里用removed标记当前弧是否发生了值域变化用第二个返回布尔值标记是否出现了空值域冲突。返回了两个值是因为后面主循环要根据它们做不同处理。AC-3主循环用collections.deque当队列初始把所有有向弧放进去然后逐条弹出处理from collections import deque def ac3(domain, neighbors): queue deque((x, y) for x in range(81) for y in neighbors[x]) while queue: x, y queue.popleft() changed, conflict revise(domain, x, y) if conflict: return False if changed: for z in neighbors[x]: if z ! y: queue.append((z, x)) return True注意revise返回有变化时入队的弧是(z, x)也就是所有指向x的弧。为什么不是(x, z)因为x的值域变了受影响的是“以x作为约束另一端”的变量z它们原来是否能匹配x的候选集现在需要重新确认。反过来(x, z)依赖的是z的值域z没变所以不需要重复检查。3.3 MRV回溯搜索与传播如何协作AC-3跑完之后如果还有格子值域大于1就要进入回溯搜索。变量选择我用的是MRV启发式即优先选择候选值最少的格子。这个策略的直觉很简单分支数最少的位置最容易确认而且一旦确认对邻居的约束传播效果也最明显。def select_unassigned(domain): best -1 best_len 10 for i in range(81): n len(domain[i]) if 1 n best_len: best_len n best i return best每一层递归里我先把当前domain完整复制一份再把选中的格子值域尝试收缩成某个候选值然后立刻跑一遍AC-3做传播。如果传播后没有冲突才继续递归有冲突就换下一个候选值。这套流程写出来是def solve(domain): idx select_unassigned(domain) if idx -1: return domain # 所有格子值域长度都是1完成 for value in sorted(domain[idx]): new_domain [set(d) for d in domain] new_domain[idx] {value} if not ac3(new_domain, neighbors): continue result solve(new_domain) if result is not None: return result return Nonevalue的排序在这里没有特别讲究第一版直接升序遍历。这里关键点是每尝试一个候选值都会做完整AC-3传播虽然单次传播成本比普通前向检查高但大量冲突在进入更深递归之前就被拦截了整体搜索节点会少一大截这个交换非常划算。3.4 输入输出与完整调用输入我用最简单的81字符文本0表示空格。解析时直接转成值域集合输出时逐行打印确定值还没有确定的位置打印点号def parse_text(text): digits [int(ch) for ch in text if ch in 0123456789] if len(digits) ! 81: raise ValueError(输入必须恰好包含81个数字) return [set(range(1, 10)) if v 0 else {v} for v in digits] def print_board(domain): for r in range(9): row [] for c in range(9): cell domain[r * 9 c] row.append(str(next(iter(cell))) if len(cell) 1 else .) print( .join(row))调用方式就三步先build_neighbors建邻接表再parse_text得到初始值域最后先跑一次ac3成功后再交给solve回溯。这个结构很干净以后想替换成更强的一致性算法只需要改ac3内部实现对外接口完全不用动。4. 实测记录AC-3把搜索空间压到了什么程度4.1 三种求解策略对照为了量化AC-3的实际价值我在同一组数独样本上对比了三种策略的搜索节点数S1纯回溯加MRV不做任何约束传播。S2最开始跑一次AC-3之后回溯过程不再传播。S3每次递归尝试前都跑AC-3也就是完整版方案。搜索节点数按“select_unassigned被调用的次数”来统计这个指标能比较公平地反映搜索规模。测试样本我从自己维护的数独题库里取了三类每类挑了20题题目都验证过有唯一解。4.2 不同难度题目的表现题目类型空格数量S1回溯次数S2回溯次数S3回溯次数简单约35-40个空格60-1500-80-2中等约45-50个空格600-200020-602-6困难约55个空格以上5000-2000080-3004-15简单题里S3几乎不需要回溯AC-3传播到固定点就直接把答案推出来了。中等题和困难题三种策略的差距更明显。尤其困难题纯回溯可能跑出上万次尝试而完整方案通常个位数到十几次回溯就结束了。单纯从数字看AC-3带来的剪枝效果不是优化而是数量级上的改变。需要说明的是具体回溯次数跟题目结构、怎么定义难度都有关系不同机器上跑出来也可能有波动但相对趋势非常稳定。我刚开始看到这个结果也有点意外AC-3明明只是“局部一致性”剪枝能力居然这么强。4.3 为什么单步传播反而是总耗时更优有人会担心S3每次递归都跑一遍AC-3传播本身不是也花时间吗确实单次AC-3需要扫描大量有向弧代价不算低。但关键在于AC-3的价值不只是减少尝试次数更重要的是让每一次尝试都建立在更干净的状态上。可以这样理解纯回溯在某个分支上走了很深才发现矛盾中间积累的无效试探全部白费而AC-3在一个分支刚开始时就把能看穿的矛盾直接暴露出来根本不给它深入的机会。这就像排查漏水与其把整栋楼都拆开找不如先用压力测试逐步缩小范围。在实际测试里困难题用S3求解总耗时通常远小于S1因为在传播上多花的毫秒级时间换来的是搜索层数的大幅减少整体收益非常明显。5. 实现过程中最值得记录的四个坑5.1 队列重复入队死循环差点出现AC-3主循环里最容易忽视的细节是入队条件。正确逻辑是只有revise真的删掉了x的值域里的值才把(z, x)重新入队。如果revise返回没有变化还把相关弧入队那队列里会出现大量无意义的重复弧程序要么极慢要么干脆死循环。我在第一版实现时就因为贪图省事把“重新入队”写成了无条件入队结果跑一个稍复杂的题目直接卡死。排查时在循环里加了计数器发现同一条弧被反复弹出数千次这才意识到问题。修好之后我额外加了一层保护用集合记录当前已经在队列里的弧重复入队前先查一下这样既能保证正确性也能减少队列里冗余元素。这个优化对性能影响不大但对思维清晰很有帮助。5.2 宫索引与邻居集合去重宫索引计算是非常容易写错的地方。正确公式是宫的行起始为(r // 3) * 3列起始为(c // 3) * 3。我最初写的时候用的是r % 3之类的错误公式导致宫约束完全错位解出来的“答案”根本不符合数独规则。另一个看似小但实则有隐患的点在前面提过同行且同宫的格子对如果分别遍历“行邻居”和“宫邻居”就会被重复加入。虽然重复约束不会让结果出错但会让弧数量膨胀、队列处理变慢。用set构建邻居集合后这个问题自动解决。建议所有构造邻接表的人都先用一个全空盘的测试用例检查每个格子的邻居数量角格20个边格非角格23个中间非宫心格子20个宫心格子20个。如果不匹配说明索引或去重逻辑有问题。5.3 回溯状态回滚复制域是最不花脑子的正确做法回溯搜索里最常见的bug是状态恢复不完整。在S3方案里每次递归都基于一份新拷贝的domain递归返回后原来的domain完全不受影响这种设计用内存换正确性写起来非常省心。我对性能曾有过怀疑每次候选值都要复制81个set会不会太慢实测下来完全不用焦虑。因为AC-3把分支剪到很低之后复制的次数本身就很少加上Python的set复制是线性代价整体开销完全可以接受。真要优化的话可以改成记录每次revise删除的(变量, 值)列表回溯时再插入回去但这会显著增加代码复杂度。对现在的规模我强烈建议先用复制方案等确定程序逻辑完全正确后再考虑增量回滚。5.4 边界用例空盘、无解盘、错误输入边界用例是测试程序稳定性的试金石。我测试时常跑三个特殊输入空盘81个格子全部为0。这种盘面对称性极强AC-3完全推不出任何值只能靠回溯。我的程序靠MRV加值排序能很快输出一个合法终盘但如果程序里没有处理“值域长度为0”的情况这里可能直接报错。无解盘手动把某个已知数字改成错误值。AC-3会在预处理阶段或回溯阶段返回False程序应该返回None而不是抛异常。错误输入数字不足81个或带非法字符。parse_text里已经有长度检查非法字符直接忽略但要注意别让用户输入的空格或换行导致长度误判。我现在每次改动完代码第一件事就是跑这三个边界用例全通过才测正常题目。这习惯帮我挡掉了很多“看起来正常但实际很脆弱”的版本。6. 性能进一步优化与扩展方向6.1 利用“不等于”约束简化revise数独的所有约束都是“不相等”这个特性让revise可以大幅简化。仔细想一下在二元“不等于”约束下一个候选值vx在x中被删除只在一种情况下发生就是y的值域只剩下一个值{vx}。如果y的值域还有至少两个值那么无论vx是几都能在y里找到另一个不等于vx的值vx就不会被删。因此revise可以简化为def revise_fast(domain, x, y): if len(domain[y]) 1: val next(iter(domain[y])) if val in domain[x]: domain[x].remove(val) if not domain[x]: return True # 冲突 return False这个版本比通用revise快很多因为大多数情况下y的值域不是单元素revise几乎不需要做任何遍历。我用这个优化替掉通用版之后困难题目的求解时间又降低了约50%。在数独这个特定问题上理解约束本身的结构确实能带来巨大收益。6.2 位掩码与C扩展如果追求更极限的性能可以把每个格子的值域设计成一个9位整数掩码第k位表示数字k1是否可选。这样revise里的删除操作就是一次位运算判断值域是否为空就是判断掩码是否为0。9个候选值可以压进一个int81个格子的domain数组只有81个整数缓存友好度也远高于set。我自己的一个经验是先用set版本把算法彻底跑通再改成位掩码。因为位掩码的位运算技巧容易写错而且调试时打印非常不直观。不过改完之后效果很明显整个求解器可以在非常短的时间内处理最难的题目纯Python也不输给很多C语言实现的脚本版。想要进一步提速还可以把build_neighbors预先计算好避免每次求解重建。6.3 更强的约束传播和值排序AC-3是弧一致性往上还有路径一致性PC-2等更强的一致性算法。路径一致性考虑的是三元变量关系理论传播能力更强但对数独这种规模的问题收益通常不明显还会引入大量计算开销。我实测过PC-2风格的传播搜索节点数确实会进一步下降可总耗时反而变长所以最终保留了AC-3加MRV的组合。另一个值得尝试的方向是值排序的“最少约束值”启发式。MRV决定选哪个变量值排序决定先试哪个数。可以统计一个候选值在邻居值域里出现的次数出现越少说明对邻居的约束越弱理论上更应该先试。这个策略在某些题目上能继续减少回溯但不是每次都有优势。我的经验是MRV是稳定收益值排序属于锦上添花先把前者做好再考虑后者。最后分享一个我现在还在用的习惯每写完一个版本的CSP求解器一定拿空盘、无解盘、单候选数盘三种极端输入做冒烟测试。空盘验证对称局面下的搜索上限无解盘验证失败路径是否干净返回单候选数盘验证传播是否正确启动。很多看起来没问题的实现恰恰是在这几个边界上暴露隐藏问题。把AC-3核心逻辑搞清楚之后这套求解框架不止能解数独像地图填色、排课、调度这类能抽象成CSP的问题几乎可以原样复用它。