Python约束求解实战：2018刑侦科推理测试题穷举与剪枝

1. 这道题到底在考什么第一次看到2018刑侦科推理测试题这个标题很多人以为是某个真实案件的卷宗点进去才发现是一道纯逻辑推理题。它最早在2018年刷屏号称是某类推理能力测试的题目一共10道选择题每道题的选项互相引用、互相约束最后要求找出唯一满足所有条件的答案序列。Python圈子里很快有人把它做成了程序题用穷举、约束求解、逻辑编程等方式来解于是就有了python-网红题2018刑侦科推理测试题这个项目方向。这道题的核心不是刑侦也不是推理小说而是自指命题系统。10道题的答案构成一个长度为10的序列每道题的题干又在描述这个序列本身的性质比如第2题答案是A的题目有几道答案中出现次数最少的字母是哪个等等。你没法一题一题顺着做因为第1题的答案依赖后面题目的答案后面题目的答案又依赖第1题。这种题目在逻辑学里叫自指约束满足问题在工程上就是典型的约束求解Constraint Satisfaction Problem, CSP。它能解决什么问题说白了它训练的是把自然语言描述的约束翻译成可计算条件的能力。这个能力在实际工作里非常值钱配置校验、排班系统、依赖解析、规则引擎、甚至游戏关卡设计本质都是同一类问题。适合谁来参考只要你会Python基础语法想练一练逻辑建模和搜索剪枝这道题就是极好的练手材料。哪怕你完全没接触过约束求解跟着走一遍也能上手。我先把结论放前面这道题用暴力穷举也能出结果但真正值得学的是怎么把题干翻译成约束、怎么剪枝、怎么验证唯一解。下面我按自己的实操过程把整件事拆开讲。2. 题目结构与约束建模思路2.1 先把10道题的题干抄清楚做这类题最忌讳的就是凭记忆写代码。题干里一个最少最多相邻连续的措辞差异直接决定约束怎么写。我建议第一步不是打开编辑器而是拿张纸或者开个文档把10道题一字不差地抄下来然后逐题标注它涉及哪些位置、涉及哪些字母。这道题的10道题大致可以归成几类计数类问某个字母在全部答案里出现了几次或者某类题有几道。位置类问某个答案第一次/最后一次出现在第几题。比较类问出现次数最多/最少的字母是哪个。自指类选项本身描述的是本题答案是X这种直接自指或者第N题答案是X这种间接引用。分类的意义在于不同类型的约束在代码里的写法完全不同。计数类需要先统计整个序列位置类需要扫描索引比较类需要排序或求极值自指类则是直接对当前位赋值。你把这些类型分清楚后面写约束函数就是填空题。提示抄题干时把以下哪项这种措辞单独标出来因为哪项往往意味着选项之间是互斥的可以用异或或者枚举来处理。2.2 为什么选穷举而不是直接上求解器很多人第一反应是装一个约束求解库比如python-constraint或者z3几行代码就出结果。这当然可以而且我后面也会讲z3的写法。但对于这道题我更推荐先用纯Python穷举剪枝做一遍原因有三个。第一这道题的搜索空间是4的10次方也就是1048576种组合。这个量级对现代计算机来说微不足道纯Python循环一秒内就能跑完根本不需要求解器。第二穷举的过程能让你彻底看清约束是怎么起作用的哪条约束剪掉了多少分支心里有数。第三面试或者分享的时候能手写穷举说明你真的理解问题而不是调库。当然如果你要把它扩展成20题、30题搜索空间指数爆炸那就必须上求解器或者写更聪明的剪枝。所以我的建议是先用穷举建立正确性基线再用求解器做扩展。这个顺序不能反否则你连答案对不对都不知道。2.3 约束翻译的三个关键原则把中文题干翻译成代码约束我总结了三条原则踩过坑之后觉得特别管用。原则一先定义答案序列再定义辅助统计。答案序列就是一个长度为10的列表每个元素取值在[A,B,C,D]里。辅助统计包括每个字母出现的次数、每个选项被选中的题目编号列表等。这些统计量在每道题的约束里反复用到提前算好能避免重复计算。原则二约束函数只返回布尔值。每道题对应一个函数输入是答案序列输出是True或False。这样组合起来非常干净所有10个函数都返回True这个序列就是合法解。不要在一个函数里既判断又修改保持纯函数。原则三题干里的唯一最少最多要小心处理。比如出现次数最少的字母如果有多个字母并列最少怎么办题干通常会补一句如果有多个选字母序靠前的或者类似限定。这种边界条件是最容易写错的地方必须逐字确认。3. 纯Python穷举实现全过程3.1 基础框架搭建先搭一个最朴素的框架用itertools.product生成所有组合然后逐个验证。代码大概长这样import itertools LETTERS [A, B, C, D] def solve_bruteforce(): for ans in itertools.product(LETTERS, repeat10): if check_all(ans): print(找到解:, ans) return ans return Nonecheck_all函数里依次调用10个约束函数。这个框架跑起来大概几秒钟因为1048576次循环乘以10个约束每次约束里还有统计操作纯Python确实会慢一点。但作为基线足够用了。我第一次跑的时候犯了个错把答案序列当成字符串处理结果索引和切片老是搞混。后来统一用tuple或者list索引从0开始对应第1题清晰很多。这个细节虽小但能省掉大量调试时间。3.2 逐题写约束函数这是最耗时的部分也是最容易出错的部分。我拿几道典型题举例说明写法。假设有一道题问答案中A出现的次数是选项是1、2、3、4。那么约束就是def q_count_A(ans): cnt ans.count(A) options {0: 1, 1: 2, 2: 3, 3: 4} # 选项索引到数值的映射 return options[LETTERS.index(ans[某题索引])] cnt注意这里有个坑选项是A/B/C/D但题目问的是次数所以要把选项字母映射成数字。这个映射关系必须和题干完全一致不能想当然。再比如位置类题目答案A第一次出现在第几题。约束就是def q_first_A(ans): first ans.index(A) 1 # 转成1-based options {0: 1, 1: 2, 2: 3, 3: 4} return options[LETTERS.index(ans[某题索引])] first如果A根本没出现index会抛异常所以要先判断A in ans。这种边界情况在写的时候一定要考虑否则程序跑到一半崩了你还以为是逻辑错了。比较类题目更麻烦一点。比如出现次数最少的字母要先统计所有字母次数找出最小值再找出所有达到最小值的字母然后按题干规则通常是字母序选一个。代码def q_least_common(ans): counts {c: ans.count(c) for c in LETTERS} min_cnt min(counts.values()) candidates [c for c in LETTERS if counts[c] min_cnt] least sorted(candidates)[0] # 字母序靠前 options {0: A, 1: B, 2: C, 3: D} return options[LETTERS.index(ans[某题索引])] least这段代码里sorted(candidates)[0]就是处理并列情况的关键。如果题干没说并列怎么办那这道题可能有多解需要重新审视题干。3.3 剪枝优化让速度起飞纯穷举能跑但慢。加剪枝之后速度能提升一个数量级。剪枝的核心思想是在生成答案序列的过程中一旦发现某个前缀已经违反某条只依赖前缀的约束就立即停止这条分支。比如第1题的约束只依赖第1题自己的答案那在生成第1位之后就能判断不满足直接跳过后面9位的所有组合。这样能砍掉大量分支。实现方式有两种。一种是用递归生成每填一位就检查一次另一种是用itertools.product但配合生成器提前过滤。我推荐递归控制力更强def search(ans, pos): if pos 10: return ans if check_all(ans) else None for letter in LETTERS: ans.append(letter) if partial_check(ans, pos): # 只检查依赖前pos1位的约束 result search(ans, pos 1) if result: return result ans.pop() return Nonepartial_check里只放那些当前已知前缀就能判断的约束。哪些约束满足这个条件需要你逐题分析。通常自指类和只涉及前面位置的题目可以提前判断涉及全局统计的必须等填完。实测下来加了剪枝之后这道题基本是毫秒级出结果。而且剪枝的过程本身加深了你对约束依赖关系的理解一举两得。4. 用求解器做扩展与交叉验证4.1 z3求解器的写法如果你要处理更复杂的自指题或者想验证自己的穷举结果z3是非常好的工具。它的思路是把每个答案定义成一个整数变量取值范围0到3然后把题干翻译成z3的约束表达式。from z3 import Int, Solver, Distinct, Sum, If def solve_z3(): s Solver() ans [Int(fa{i}) for i in range(10)] for a in ans: s.add(a 0, a 3) # 例如约束A出现次数等于某题选项对应的数字 count_a Sum([If(a 0, 1, 0) for a in ans]) s.add(count_a ans[某题索引] 1) # 其他约束类似翻译 if s.check() sat: m s.model() return [m[a].as_long() for a in ans]z3的好处是它内部做了大量剪枝和推理你只需要关心约束本身不用管搜索顺序。缺点是翻译约束时容易写错而且报错信息不如自己写的代码直观。所以我一般用它来交叉验证穷举出一个解z3也出一个解两者一致才放心。4.2 唯一性验证不能省这道题号称有唯一解但你不能假设它真的有。必须验证。验证方法很简单把所有满足约束的解都找出来看是不是只有一个。用穷举的话把return改成收集所有解即可。用z3的话找到一个解之后加一条答案不等于这个解的约束再check一次如果unsat就说明唯一。我见过有人直接拿网上的答案交差结果那道题其实有两个解只是出题人没发现。所以唯一性验证是负责任的做法也是这道题真正有意思的地方——它逼你去思考约束是否足够强。4.3 两种方法的性能对比方法代码量运行时间可读性扩展性纯穷举中秒级高差穷举剪枝中毫秒级中中z3求解器少毫秒级中好从表里能看出来z3在扩展性上优势明显。如果你想把题目改成15题、20题纯穷举的搜索空间会爆炸z3依然能处理。但学习阶段我还是建议先手写穷举理解透了再用工具。5. 常见问题与排查技巧实录5.1 答案对不上怎么办这是最常见的问题。你跑出一个解但和网上流传的答案不一样。先别急着怀疑自己按下面顺序排查核对题干。网上流传的题干版本可能有出入尤其是最少最多这类措辞。找几个不同来源对比一下。检查选项映射。A对应1还是0这个映射错一位结果全错。检查索引基准。第1题在代码里是索引0还是1混用必出bug。检查并列处理。出现次数并列时选哪个题干有没有明确。验证唯一性。如果有多解你和网上的答案可能都对。我踩过最大的坑就是第3条。有一次写位置类约束一会儿用0-based一会儿用1-based跑出来的解看着像对的实际上错得离谱。后来统一在函数入口把索引转成1-based问题就没了。5.2 程序跑得慢怎么优化如果纯穷举要跑十几秒先别急着换语言。按这个顺序优化把check_all里重复计算的统计量提到循环外或者用缓存。加剪枝这是提升最大的。把答案序列从list换成tuple减少开销。用itertools.product替代手写嵌套循环。一般做到前两条速度就够了。真要到毫秒级再考虑z3。5.3 常见错误速查表现象可能原因解决方向无解约束写太严逐条放松定位哪条约束导致unsat多解约束写太松检查是否漏了题干条件结果和预期差一位索引基准混用统一0-based或1-based程序崩溃边界未处理检查index、min、max的空值情况速度极慢无剪枝加前缀检查提示调试约束问题时把每条约束单独拿出来用一个已知的部分答案测试它返回True还是False比整体调试快得多。5.4 几个容易被忽略的细节第一题干里以下哪项有时候意味着选项之间是恰好一个成立而不是至少一个成立。这两种语义在约束里写法不同前者要加Distinct或者Sum1。第二涉及相邻两题答案相同的约束要注意边界第10题没有下一题。第三如果题干说本题答案与第N题答案相同而N恰好等于本题那就是直接自指需要特殊处理否则会陷入循环依赖。这些细节在写代码前就要想清楚写的时候才不会返工。6. 从这道题能学到什么把这道题做完你收获的不只是一个答案。你练的是把模糊的自然语言需求翻译成精确的可执行约束的能力。这个能力在写业务代码时天天用到产品经理说这个优惠券不能和那个叠加你得翻译成互斥约束运营说每个用户每天最多领三张你得翻译成计数约束。本质和这道题一模一样。另外这道题还教会我一件事先建立正确性基线再优化。很多人一上来就想写最优解结果连答案对不对都不知道。先用最笨的方法跑通再用剪枝和求解器优化这个顺序在工程上屡试不爽。如果你想把这道题继续扩展可以试试这几个方向把题目改成15题看搜索空间怎么变化用遗传算法或者模拟退火来解对比和精确解法的差异把约束写成配置文件做一个通用的自指题求解器。这些扩展都能让你对约束满足问题理解更深。最后分享一个小技巧做这类题时把每道题的约束写成一句自然语言注释放在函数上面代码和题干一一对应。这样过几天回头看或者分享给别人都能秒懂。我现在的习惯是约束函数名直接用题号比如q1、q2注释里写题干原文维护起来特别省心。