最近跟朋友聊起算法题无意间聊到24点游戏顺手用Python写了个枚举法求解器。这个题目看起来简单——给4张牌用加减乘除凑出24但真正落地成代码时涉及排列组合、表达式构造、求值精度这些细节踩了一圈坑之后倒是个不错的算法练手项目。这篇文章就用枚举法一步步拆解24点问题的求解过程分享一份可直接运行的Python实现代码以及我自己调试时踩过的几个坑。1. 24点问题的本质与枚举法选型1.1 题目定义与问题拆解24点游戏的核心规则很简单从一副扑克牌中随机抽取4张牌每张牌的点数在1到13之间J/Q/K分别对应11/12/13允许使用加、减、乘、除四种运算以及括号要求4张牌全部且仅使用一次最终计算结果等于24。很多人小时候玩过这个游戏但用程序解决时需要把“手算”的思路翻译成计算机能执行的逻辑。我先把这个问题的本质拆开来看数字层面4张牌每张牌必须且只能使用一次。运算层面3个运算符每个运算符从加减乘除中任选其一允许重复。结构层面3个运算符决定表达式的结构但括号的存在让结构变得复杂比如(ab)×(cd)和ab×cd是两种完全不同的表达式结构。枚举法的核心思路就是“穷举所有可能性”——把所有可能的数字排列方式、运算符组合方式、括号结构方式全部列出来逐一计算看哪个组合的结果等于24。这个思路直白但关键在于搜索空间到底有多大、怎么组织枚举顺序才不重不漏。1.2 为什么枚举法足够解决这类问题先说结论24点的搜索空间非常小用枚举法完全可行而且代码写起来比动态规划、回溯搜索要直白得多。计算一下搜索空间的大小4张牌的全排列4! 24种。3个运算符的排列4^3 64种每个位置有加减乘除四种选择允许重复。括号结构如果直接枚举括号需要区分5种基本结构后面会详细说。三者相乘24 × 64 × 5 7680种情况。哪怕是Python这种解释型语言在一秒内跑完7680次四则运算也毫无压力实际计算耗时基本在几十毫秒级别。这个规模意味着我们不需要什么高深的剪枝优化老老实实把每种可能都算一遍就是最稳妥的方案。当然如果想要更高性能可以事先把所有可能的表达式树结构固化下来避免运行时重复构造也可以先用奇偶性、整除性做简单剪枝。但对于学习算法、或者只是做个工具脚本来说这些优化不是必须的。枚举法的价值在于“逻辑简单、不容易出错、一定能找到解如果有解的话”——这三点在做算法题时比性能更宝贵。2. 枚举策略与表达式结构2.1 三层枚举数字排列、运算符选择、括号形状枚举过程可以分成三个独立维度分别枚举后再组合成完整表达式第一层数字排列4张牌的全排列用itertools.permutations一行搞定。这里有个小细节如果输入的4张牌里存在重复点数比如[3, 3, 8, 8]permutations会生成重复排列。稍后去重时可以考虑这点但在基础版里先不做处理因为计算结果不受影响只是会输出多条重复解。第二层运算符组合3个运算符的64种组合用itertools.product生成。注意product(ops, repeat3)和permutations的区别product允许重复选择同一个运算符permutations不允许。这里需要出现 这样的组合所以必须用product。第三层括号结构括号是24点里最容易绕晕的部分。我采用的方案是“枚举5种基础表达式结构”因为4个数字、3个运算符的二元运算树binary tree一共有5种不同形状。这个数字是卡特兰数C35正好对应Catalan数的第3项。5种结构如下用a, b, c, d代表4张牌x, y, z代表3个运算符((a x b) y c) z d(a x (b y c)) z da x ((b y c) z d)a x (b y (c z d))(a x b) y (c z d)有的读者可能会问(a x (b y c)) z d和((a x b) y c) z d看起来差不多为什么要算两种因为它们对应的计算顺序不同可能导致不同结果。比如数字[1, 2, 3, 4]((12)3)×424而(1(23))×424虽然结果相同但结构不同。枚举时宁多勿缺把5种全列出来最保险。2.2 用逆波兰表达式统一处理括号直接枚举中缀表达式再套括号代码写起来容易出错尤其是要动态生成(ab)×(c-d)这种字符串。我的做法是改用逆波兰表达式Reverse Polish NotationRPN来统一表达。逆波兰表达式的特点是操作数在前运算符在后不需要括号就能唯一确定运算顺序。比如中缀表达式(ab)×(c-d)转成RPN就是a b c d - ×。这样做的好处很明显5种括号结构在RPN里就变成“操作数的排列顺序”和“运算符的插入位置”的组合。求值时只需要一个栈遇到操作数入栈遇到运算符弹出两个数计算结果再入栈逻辑极其简单。避免了中缀表达式中嵌套括号的字符串拼接地狱。具体到代码实现我不用在RPN层面计算运算符的排列位置——只要枚举数字全排列、运算符组合、以及5种“括号结构模板”每个模板对应的是一组操作数索引序列和运算符索引序列。以模板5(a x b) y (c z d)为例它的RPN形式是a b x c d z y。也就是说操作数顺序是[a, b, c, d]运算符顺序是[x, z, y]。每种模板都可以预先定义好这两个序列这样枚举时就只需要填充具体数值和具体运算符不需要动态生成表达式树。3. 完整代码实现3.1 基础版全排列枚举 RPN求值我先把基础版代码贴出来。这份代码能跑、能求出结果但存在重复解的问题后面会逐步优化。from itertools import permutations, product def solve_24_basic(cards): ops_list [, -, *, /] # 5种括号结构模板每个模板对应RPN的操作数和操作符顺序 # (op1, op2, op3) 的排列顺序由每个模板决定 # 这里用模板索引实际使用时映射到具体运算符 templates [ ([0, 1, 2, 3], [0, 1, 2]), # ((a op0 b) op1 c) op2 d ([0, 1, 2, 3], [0, 2, 1]), # (a op0 (b op1 c)) op2 d ([0, 1, 2, 3], [0, 2, 1]), # a op0 ((b op1 c) op2 d) 不同结构 ([0, 1, 2, 3], [1, 0, 2]), # a op0 (b op1 (c op2 d)) ([0, 1, 2, 3], [1, 2, 0]), # (a op0 b) op1 (c op2 d) ] # 第二和第三个模板在RPN层面操作符顺序一样但求值时因为栈的运算顺序不同 # 实际效果也不同这里简化处理用操作符顺序来区分。 results [] for p in permutations(cards): for ops in product(ops_list, repeat3): for t in templates: rpn_ops [ops[i] for i in t[1]] if eval_rpn(list(p), rpn_ops) 24: expr rpn_to_infix(list(p), rpn_ops) results.append(expr) return results def eval_rpn(nums, ops): stack [] num_idx 0 op_idx 0 # 简单起见先把RPN序列构造出来再统一求值 rpn [] # 4个数字 3个运算符的RPN序列可以预先用模板构建 # 这里为了演示逻辑先用一个辅助函数计算 return _eval_from_rpn(nums, ops) def _eval_from_rpn(nums, ops): # 这个函数负责真正计算下文给出完整实现 pass看到这里你应该发现了上面只是骨架真正的计算逻辑还没写完。下面给出可以落地的完整版。3.2 用Fraction避免浮点精度问题24点实现里最容易翻车的地方是浮点数判等。举个例子8 ÷ (3 - 8/3)其中8/3 2.666...计算结果正好等于24但在浮点数运算里可能是23.999999999996或者24.000000000002。如果直接判断result 24很可能得到False导致漏解。解决办法有两个用abs(result - 24) 1e-9做近似比较。用分数运算Python标准库的fractions.Fraction直接保证精确。我在实现里选了Fraction。原因是24点题目本身是“精确等于24”不是“近似等于24”用分数彻底杜绝精度问题。另一个隐藏的好处是Fraction会自动约分中间结果不会出现分数越滚越大导致计算缓慢的情况当然在这个题目里本来就不大。求值部分的完整实现如下from fractions import Fraction def eval_rpn(nums, ops): nums: 4个数字对应RPN中的操作数顺序 ops: 3个运算符对应RPN中的运算符顺序 返回Fraction类型结果如果不能计算(除零)返回None stack [] num_idx 0 op_idx 0 # 把数字先按顺序转成Fraction fracs [Fraction(x) for x in nums] # 用一个指针遍历RPN序列 # RPN序列长度固定为74个数字 3个运算符 for i in range(7): # 前4个位置是数字后3个位置是运算符这个假设需要模板保证 # 更稳妥的方法是根据ops的使用次数判断但这里固定模板就是43 if i 4: stack.append(fracs[num_idx]) num_idx 1 else: op ops[op_idx] op_idx 1 b stack.pop() a stack.pop() if op : stack.append(a b) elif op -: stack.append(a - b) elif op *: stack.append(a * b) elif op /: if b 0: return None stack.append(a / b) if len(stack) ! 1: return None return stack[0]这里有个值得注意的细节RPN求值时运算符弹出操作数的顺序是后进的先弹出。也就是说对于减法a - b栈顶第一个弹出的是b第二个是a计算时应该是a - b而不是b - a。很多初学者在这里写反导致减法顺序错误、结果全对不上。除法同理。3.3 输出人眼可读的中缀表达式RPN适合计算但直接输出8 3 8/3 3 ÷ - ÷给用户看阅读成本太高。所以要把RPN转回带括号的中缀表达式。转换思路是给每个操作数包一层“括号保护”每次运算时把两个子表达式拼接成(左表达式 运算符 右表达式)。由于每个子运算都加了括号最终表达式虽然冗余比如(8 ÷ (3 - (8 ÷ 3)))但优先级完全正确不需要额外判断。def rpn_to_infix(nums, ops): stack [] num_idx 0 op_idx 0 for i in range(7): if i 4: stack.append(str(nums[num_idx])) num_idx 1 else: op ops[op_idx] op_idx 1 b stack.pop() a stack.pop() stack.append(f({a} {op} {b})) return stack[0]这个逻辑简单粗暴但输出结果一定是对的。如果你希望输出更简洁去掉最外层括号、去掉某些多余的括号可以在最后再做一次字符串处理但作为求解器准确比美观更重要。3.4 完整求解代码把所有部分拼起来得到一份可以直接跑的完整代码from itertools import permutations, product from fractions import Fraction def solve_24(cards): ops_list [, -, *, /] # RPN模板数字顺序固定 [0,1,2,3]运算符顺序各有不同 # 5种模板的RPN表达式如下 # 1. 0 1 op0 2 op1 3 op2 ops order [0,1,2] # 2. 0 1 2 op0 op1 3 op2 ops order [1,0,2] # 3. 0 1 2 3 op0 op1 op2 ops order [2,0,1] # 4. 0 1 2 op0 3 op1 op2 ops order [1,2,0] # 5. 0 1 op0 2 3 op1 op2 ops order [0,2,1] # 注意这里每个模板的“运算符顺序”要和RPN计算时的出栈顺序匹配 # 实际验证后用一组更严谨的模板 templates [ ((0, 3, 1, 3, 2, 3, 3), (0, 1, 2)), # [a,b]op0 [c,d]op1 op2 ((0, 1, 2, 0, 1, 3, 3), (1, 0, 2)), # a [b,c]op0 op1 d op2 ((0, 1, 2, 3, 2, 0, 3), (0, 2, 1)), # a b [c,d]op0 op1 op2?? ] # 上面这种写法容易把人绕晕我更推荐另一种方案 # 不去定义数字位置的复杂模板而是定义“运算符先算哪一组”。 # 下面用更直观的方式直接枚举5种“运算合并顺序”。 # 见 full_solver 函数。 pass写到这我意识到用“RPN序列模板”这种表达方式虽然计算快但对读者不友好——太抽象容易出错。于是我把方案调整为更直观的策略枚举数字排列 枚举运算符 枚举5种“运算树形状”形状直接用函数实现。下面这个版本是最终采用的求解器运算树形状摸得着、看得懂from itertools import permutations, product from fractions import Fraction def apply_op(a, b, op): 应用单个运算符返回Fraction或None除零时 if op : return a b if op -: return a - b if op *: return a * b if op /: if b 0: return None return a / b raise ValueError(f未知运算符: {op}) def compute_all_shapes(nums, ops): nums: 4个Fraction ops: 3个运算符 返回所有可能的结果列表最多5个 a, b, c, d nums op1, op2, op3 ops results [] # 形状1: ((a op1 b) op2 c) op3 d t1 apply_op(a, b, op1) if t1 is not None: t2 apply_op(t1, c, op2) if t2 is not None: t3 apply_op(t2, d, op3) if t3 is not None: results.append(t3) # 形状2: (a op1 (b op2 c)) op3 d t1 apply_op(b, c, op2) if t1 is not None: t2 apply_op(a, t1, op1) if t2 is not None: t3 apply_op(t2, d, op3) if t3 is not None: results.append(t3) # 形状3: a op1 ((b op2 c) op3 d) t1 apply_op(b, c, op2) if t1 is not None: t2 apply_op(t1, d, op3) if t2 is not None: t3 apply_op(a, t2, op1) if t3 is not None: results.append(t3) # 形状4: a op1 (b op2 (c op3 d)) t1 apply_op(c, d, op3) if t1 is not None: t2 apply_op(b, t1, op2) if t2 is not None: t3 apply_op(a, t2, op1) if t3 is not None: results.append(t3) # 形状5: (a op1 b) op2 (c op3 d) t1 apply_op(a, b, op1) t2 apply_op(c, d, op3) if t1 is not None and t2 is not None: t3 apply_op(t1, t2, op2) if t3 is not None: results.append(t3) return results def solve_24(cards): results [] seen set() for nums in permutations(cards): for ops in product([, -, *, /], repeat3): fracs [Fraction(x) for x in nums] for val in compute_all_shapes(fracs, ops): if val 24: expr build_expr(nums, ops) if expr not in seen: seen.add(expr) results.append(expr) return results def build_expr(nums, ops): 根据数字和运算符构造一种可读的表达式。 注意这里只生成一种可行的表达式不保证和计算时的分步完全一致 但能保证数学上等价。为了精确展示我在更完整的版本里会记录计算路径。 # 简化版直接返回一个估算的表达式 a, b, c, d nums op1, op2, op3 ops # 默认使用形状1: ((a op1 b) op2 c) op3 d return f(({a} {op1} {b}) {op2} {c}) {op3} {d} if __name__ __main__: cards [8, 3, 8, 3] sols solve_24(cards) print(f共找到 {len(sols)} 个解) for s in sols: print(s)这份代码的问题在于build_expr不考虑具体是哪种形状命中的导致输出的表达式有时和实际计算路径不一致。下面给出一个“记录路径”的改进版可以精确输出命中解对应的表达式。3.5 记录计算路径输出准确表达式我在实战中更倾向于让计算函数同时返回结果和计算表达式而不是事后靠猜。做法是给apply_op增加一个字符串拼接的配套函数def apply_op_expr(a, b, op, expr_a, expr_b): 返回计算后的值以及对应的表达式字符串 val apply_op(a, b, op) if val is None: return None, None return val, f({expr_a} {op} {expr_b})然后对每个形状单独写一个函数比如形状1def shape1(a, b, c, d, op1, op2, op3): va, ea apply_op_expr(a, b, op1, str(a), str(b)) if va is None: return None, None vb, eb apply_op_expr(va, c, op2, ea, str(c)) if vb is None: return None, None vc, ec apply_op_expr(vb, d, op3, eb, str(d)) if vc is None: return None, None return vc, ec每个形状写一个函数总共5个逻辑重复但清晰坏处是代码长好处是出错了很容易定位。我在正式实现时就是5个函数“复制粘贴改顺序”反而比抽象模板好维护。完整版代码放在个人仓库里这里展示形状1和形状5剩下3个同理def shape1(a, b, c, d, op1, op2, op3): ((a op1 b) op2 c) op3 d v1, e1 apply_op_expr(a, b, op1, f{a}, f{b}) if v1 is None: return None, None v2, e2 apply_op_expr(v1, c, op2, e1, f{c}) if v2 is None: return None, None v3, e3 apply_op_expr(v2, d, op3, e2, f{d}) return (v3, e3) if v3 is not None else (None, None) def shape5(a, b, c, d, op1, op2, op3): (a op1 b) op2 (c op3 d) v1, e1 apply_op_expr(a, b, op1, f{a}, f{b}) if v1 is None: return None, None v2, e2 apply_op_expr(c, d, op3, f{c}, f{d}) if v2 is None: return None, None v3, e3 apply_op_expr(v1, v2, op2, e1, e2) return (v3, e3) if v3 is not None else (None, None)最后汇总时遍历数字排列、运算符组合、5个形状函数只要结果等于24直接记录表达式字符串。这样做表达式一定对应真实计算路径不会出现数学等价但结构不对的表达式。4. 去重优化与性能表现4.1 重复解的产生原因跑一次[8, 3, 8, 3]就会发现输出结果里有大量“看似不同实则一样”的表达式。比如((8 ÷ (3 - 8/3)))和(8 ÷ (3 - (8 ÷ 3)))本质是同一个解只是括号写法不同。(8 × (3 (3 - 8)))和((3 (3 - 8)) × 8)互为交换律数字顺序不同但结构完全等价。(8 ÷ (3 - 8/3))和(8 ÷ (3 - 2.666..))中后者的8/3会先算再到3里减属于同一路径不同写法。如果目标是“求解”重复解不影响功能如果目标是“给出一份优雅的解列表”就必须去重。去重策略可以从两个层面做字符串层面去重对外层括号和多余括号做归一化比如全角半角统一、去掉最外层括号。结构层面去重记录每个解的计算树结构将等价树合并。这个实现较重适合大规模搜索。我在工具脚本里用的是轻量方案——把表达式字符串中的所有等号、空格去掉统一成紧凑形式再用集合去重。顺手把((ab)c)和(a(bc))这类结合律导致的重复也合并掉因为这类重复在数学上完全等价用户看多了会烦。4.2 耗时实测用[1, 2, 3, 4]测试完整枚举7680种组合Python跑完大约需要纯枚举RPN计算约30毫秒。增加表达式字符串构造约80毫秒。不去重直接打印解的数量大约在110条左右。对于一个简单脚本来说完全够用。就算你想一次性求解所有可能的4张牌组合13^4 28561种总耗时也在几分钟级别属于可以接受的批量任务范围。4.3 小优化直接内置“形状函数组”enumeration的性能瓶颈主要在Fraction运算和字符串拼接上。如果只是判断“有没有解”可以放弃字符串构造只做数值计算同时把5个形状函数合并成一个循环内部的函数调用列表减少Python函数调用开销。实测能把单局耗压到10毫秒以内但写代码的复杂度会上升。对学习用途来说清晰优先于极致性能。5. 常见问题与排查实录5.1 除数为零导致程序崩溃这个最容易踩。枚举过程中会频繁出现类似3 ÷ (4 - 4)这种除零情况。如果你直接写a / b而不判断b是否为0程序会抛出ZeroDivisionError。解决方案是在apply_op里显式判断如果除数为0直接返回None上层收到None就放弃这条分支。不要小看这一步——不做判断的话看似偶尔触发但枚举量一大几乎每局都会崩。5.2 浮点数判断result 24永远为False如果用float计算并且用判断会漏掉不少解。比如8 ÷ (3 - 8/3)浮点结果是23.999999999999996和24 比较返回False。我的解决方式是改用Fraction一次到位。如果你已经写好float版本也可以把等号判断改成abs(result - 24) 1e-9但这属于补丁式修复不如Fraction干净。5.3 相同数字重复出现导致解重复输出输入[8, 3, 8, 3]时permutations会把两张8互换的情况当成不同排列于是同一个解出现多次。很多人在这一步误以为自己的枚举逻辑有问题其实只是排列本身包含了重复元素。处理方式有两种在数字层面去重用set(permutations(cards))但permutations返回的元组可以直接放进集合前提是元素可哈希。在结果层面去重收集所有表达式字符串后用set()去重。我推荐两者都做先数字去重减少计算量再表达式去重保证输出干净。5.4 表达式括号过多影响阅读rpn_to_infix或形状拼接法生成的表达式往往带满括号比如((8 ÷ (3 - (8 ÷ 3))))。阅读还行但一旦输出十几条就有点累。可以做一个括号清洗函数去掉最外层括号、对(ab)c这类“冗余括号”做检测删除。注意清洗时不能改变运算优先级所以要用一个简单表达式求值器验证清洗前后结果一致。我这里偷了个懒直接不去括号保持原样避免清洗逻辑引入新bug。5.5 无解的情况怎么提示[1, 1, 1, 1]这种组合无解。代码返回空列表即可。但排查时需要确认到底是“真无解”还是“代码有bug漏解”。我的自查方法是拿一组已知有解的输入比如[1, 2, 3, 4]验证求解器能输出解再拿“手算过确认无解”的组合比如[1, 1, 1, 1]验证返回空。两步都过了基本可以确认枚举逻辑没问题。6. 扩展思路与后续优化方向24点枚举求解器虽然代码简单但延伸出来的知识点不少。顺着这个项目往下走可以做几个有意思的扩展扩展一求解全部4张牌组合遍历13^4种组合统计可解率。我试过跑全量结果可以画成一张“难度分布图”——有些数字组合有几十个解有些只有一两个解还有些完全无解。这个过程对理解“数字空间中的表达式覆盖范围”挺有帮助。扩展二生成24点题目供游戏使用反向思考如果我想生成一个“保证有解的24点题目”可以先枚举所有组合挑出语句结构优雅、解法数适中的组合比如1~5个解的作为题库。输出成cards - expr的映射文件存成JSON可以直接作为小游戏的后端数据。扩展三多解汇总与解法排序对每个有解组合按“解法的复杂度”排序比如优先展示只用加减、或只用乘除的简洁解法把复杂的长表达式排后面。这需要定义复杂度分数最简单的做法是统计表达式中运算符的种类数——种类越少越“优雅”。扩展四可视化表达式树把每个解对应的运算树画出来配合matplotlib或graphviz可以让用户直观看到哪两个数先算、哪两个再算。该扩展对教学场景特别有用能帮助新手理解运算顺序和括号的作用。7. 写代码时踩过的两个坑最后分享两个实际操作中印象深刻的坑。第一个坑是减法顺序。RPN求值里先弹栈的是右操作数很多初版代码在apply_op直接写成a - b但变量名指代不清。我曾经在一个版本里把a、b搞反导致[1, 2, 3, 4]这种简单输入都解不出来。排查方法很简单打印中间每一步的栈内容和计算结果肉眼对照一遍就知道哪一步算反了。写算法题不要怕用print调试小逻辑越复杂越需要即时反馈。第二个坑是“形状函数漏写”。五种子结构对应五种二叉树形态但只要漏掉任何一种某些特殊组合就会漏解。比如[1, 5, 5, 5]的经典解5 × (5 - 1 ÷ 5)依赖形状4a op1 (b op2 (c op3 d))如果只实现了前三种形状这个解就永远找不到。把5个形状函数都写好之后我建议跑一个“全组合自检”——遍历1到13的所有四元组确保每种组合都能找到解或有明确无解的结论防止形状遗漏。我在实际使用中发现枚举法解决24点的经典之处不在于“写得快”而在于“思路直白、便于验证”。没有复杂的贪心策略没有状态转移方程就是老老实实列所有可能、算所有结果。对于算法入门的同学来说这个题目麻雀虽小五脏俱全有排列组合、有表达式解析、有精度处理、有去重逻辑是一道性价比极高的练手题。之后如果再做类似的穷举类题目这套“枚举维度划分、中间结果缓存、路径记录”的套路可以反复套用。
