最近跟朋友聊起算法題無意間聊到24點游戲順手用Python寫了個枚舉法求解器。這個題目看起來簡單——給4張牌用加減乘除湊出24但真正落地成代碼時涉及排列組合、表達式構造、求值精度這些細節(jié)踩了一圈坑之后倒是個不錯的算法練手項目。這篇文章就用枚舉法一步步拆解24點問題的求解過程分享一份可直接運行的Python實現代碼以及我自己調試時踩過的幾個坑。1. 24點問題的本質與枚舉法選型1.1 題目定義與問題拆解24點游戲的核心規(guī)則很簡單從一副撲克牌中隨機抽取4張牌每張牌的點數在1到13之間J/Q/K分別對應11/12/13允許使用加、減、乘、除四種運算以及括號要求4張牌全部且僅使用一次最終計算結果等于24。很多人小時候玩過這個游戲但用程序解決時需要把“手算”的思路翻譯成計算機能執(zhí)行的邏輯。我先把這個問題的本質拆開來看數字層面4張牌每張牌必須且只能使用一次。運算層面3個運算符每個運算符從加減乘除中任選其一允許重復。結構層面3個運算符決定表達式的結構但括號的存在讓結構變得復雜比如(ab)×(cd)和ab×cd是兩種完全不同的表達式結構。枚舉法的核心思路就是“窮舉所有可能性”——把所有可能的數字排列方式、運算符組合方式、括號結構方式全部列出來逐一計算看哪個組合的結果等于24。這個思路直白但關鍵在于搜索空間到底有多大、怎么組織枚舉順序才不重不漏。1.2 為什么枚舉法足夠解決這類問題先說結論24點的搜索空間非常小用枚舉法完全可行而且代碼寫起來比動態(tài)規(guī)劃、回溯搜索要直白得多。計算一下搜索空間的大小4張牌的全排列4! 24種。3個運算符的排列4^3 64種每個位置有加減乘除四種選擇允許重復。括號結構如果直接枚舉括號需要區(qū)分5種基本結構后面會詳細說。三者相乘24 × 64 × 5 7680種情況。哪怕是Python這種解釋型語言在一秒內跑完7680次四則運算也毫無壓力實際計算耗時基本在幾十毫秒級別。這個規(guī)模意味著我們不需要什么高深的剪枝優(yōu)化老老實實把每種可能都算一遍就是最穩(wěn)妥的方案。當然如果想要更高性能可以事先把所有可能的表達式樹結構固化下來避免運行時重復構造也可以先用奇偶性、整除性做簡單剪枝。但對于學習算法、或者只是做個工具腳本來說這些優(yōu)化不是必須的。枚舉法的價值在于“邏輯簡單、不容易出錯、一定能找到解如果有解的話”——這三點在做算法題時比性能更寶貴。2. 枚舉策略與表達式結構2.1 三層枚舉數字排列、運算符選擇、括號形狀枚舉過程可以分成三個獨立維度分別枚舉后再組合成完整表達式第一層數字排列4張牌的全排列用itertools.permutations一行搞定。這里有個小細節(jié)如果輸入的4張牌里存在重復點數比如[3, 3, 8, 8]permutations會生成重復排列。稍后去重時可以考慮這點但在基礎版里先不做處理因為計算結果不受影響只是會輸出多條重復解。第二層運算符組合3個運算符的64種組合用itertools.product生成。注意product(ops, repeat3)和permutations的區(qū)別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 用逆波蘭表達式統(tǒng)一處理括號直接枚舉中綴表達式再套括號代碼寫起來容易出錯尤其是要動態(tài)生成(ab)×(c-d)這種字符串。我的做法是改用逆波蘭表達式Reverse Polish NotationRPN來統(tǒng)一表達。逆波蘭表達式的特點是操作數在前運算符在后不需要括號就能唯一確定運算順序。比如中綴表達式(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]。每種模板都可以預先定義好這兩個序列這樣枚舉時就只需要填充具體數值和具體運算符不需要動態(tài)生成表達式樹。3. 完整代碼實現3.1 基礎版全排列枚舉 RPN求值我先把基礎版代碼貼出來。這份代碼能跑、能求出結果但存在重復解的問題后面會逐步優(yōu)化。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層面操作符順序一樣但求值時因為棧的運算順序不同 # 實際效果也不同這里簡化處理用操作符順序來區(qū)分。 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序列構造出來再統(tǒng)一求值 rpn [] # 4個數字 3個運算符的RPN序列可以預先用模板構建 # 這里為了演示邏輯先用一個輔助函數計算 return _eval_from_rpn(nums, ops) def _eval_from_rpn(nums, ops): # 這個函數負責真正計算下文給出完整實現 pass看到這里你應該發(fā)現了上面只是骨架真正的計算邏輯還沒寫完。下面給出可以落地的完整版。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個位置是運算符這個假設需要模板保證 # 更穩(wěn)妥的方法是根據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]這里有個值得注意的細節(jié)RPN求值時運算符彈出操作數的順序是后進的先彈出。也就是說對于減法a - b棧頂第一個彈出的是b第二個是a計算時應該是a - b而不是b - a。很多初學者在這里寫反導致減法順序錯誤、結果全對不上。除法同理。3.3 輸出人眼可讀的中綴表達式RPN適合計算但直接輸出8 3 8/3 3 ÷ - ÷給用戶看閱讀成本太高。所以要把RPN轉回帶括號的中綴表達式。轉換思路是給每個操作數包一層“括號保護”每次運算時把兩個子表達式拼接成(左表達式 運算符 右表達式)。由于每個子運算都加了括號最終表達式雖然冗余比如(8 ÷ (3 - (8 ÷ 3)))但優(yōu)先級完全正確不需要額外判斷。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} )) 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} ) {op2} {c}) {op3} zxl6ubaz 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 記錄計算路徑輸出準確表達式我在實戰(zhàn)中更傾向于讓計算函數同時返回結果和計算表達式而不是事后靠猜。做法是給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) 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, fzxl6ubaz) 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) if v1 is None: return None, None v2, e2 apply_op_expr(c, d, op3, f{c}, fzxl6ubaz) 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. 去重優(yōu)化與性能表現4.1 重復解的產生原因跑一次[8, 3, 8, 3]就會發(fā)現輸出結果里有大量“看似不同實則一樣”的表達式。比如((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里減屬于同一路徑不同寫法。如果目標是“求解”重復解不影響功能如果目標是“給出一份優(yōu)雅的解列表”就必須去重。去重策略可以從兩個層面做字符串層面去重對外層括號和多余括號做歸一化比如全角半角統(tǒng)一、去掉最外層括號。結構層面去重記錄每個解的計算樹結構將等價樹合并。這個實現較重適合大規(guī)模搜索。我在工具腳本里用的是輕量方案——把表達式字符串中的所有等號、空格去掉統(tǒng)一成緊湊形式再用集合去重。順手把((ab)c)和(a(bc))這類結合律導致的重復也合并掉因為這類重復在數學上完全等價用戶看多了會煩。4.2 耗時實測用[1, 2, 3, 4]測試完整枚舉7680種組合Python跑完大約需要純枚舉RPN計算約30毫秒。增加表達式字符串構造約80毫秒。不去重直接打印解的數量大約在110條左右。對于一個簡單腳本來說完全夠用。就算你想一次性求解所有可能的4張牌組合13^4 28561種總耗時也在幾分鐘級別屬于可以接受的批量任務范圍。4.3 小優(yōu)化直接內置“形狀函數組”enumeration的性能瓶頸主要在Fraction運算和字符串拼接上。如果只是判斷“有沒有解”可以放棄字符串構造只做數值計算同時把5個形狀函數合并成一個循環(huán)內部的函數調用列表減少Python函數調用開銷。實測能把單局耗壓到10毫秒以內但寫代碼的復雜度會上升。對學習用途來說清晰優(yōu)先于極致性能。5. 常見問題與排查實錄5.1 除數為零導致程序崩潰這個最容易踩。枚舉過程中會頻繁出現類似3 ÷ (4 - 4)這種除零情況。如果你直接寫a / b而不判斷b是否為0程序會拋出ZeroDivisionError。解決方案是在apply_op里顯式判斷如果除數為0直接返回None上層收到None就放棄這條分支。不要小看這一步——不做判斷的話看似偶爾觸發(fā)但枚舉量一大幾乎每局都會崩。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這類“冗余括號”做檢測刪除。注意清洗時不能改變運算優(yōu)先級所以要用一個簡單表達式求值器驗證清洗前后結果一致。我這里偷了個懶直接不去括號保持原樣避免清洗邏輯引入新bug。5.5 無解的情況怎么提示[1, 1, 1, 1]這種組合無解。代碼返回空列表即可。但排查時需要確認到底是“真無解”還是“代碼有bug漏解”。我的自查方法是拿一組已知有解的輸入比如[1, 2, 3, 4]驗證求解器能輸出解再拿“手算過確認無解”的組合比如[1, 1, 1, 1]驗證返回空。兩步都過了基本可以確認枚舉邏輯沒問題。6. 擴展思路與后續(xù)優(yōu)化方向24點枚舉求解器雖然代碼簡單但延伸出來的知識點不少。順著這個項目往下走可以做幾個有意思的擴展擴展一求解全部4張牌組合遍歷13^4種組合統(tǒng)計可解率。我試過跑全量結果可以畫成一張“難度分布圖”——有些數字組合有幾十個解有些只有一兩個解還有些完全無解。這個過程對理解“數字空間中的表達式覆蓋范圍”挺有幫助。擴展二生成24點題目供游戲使用反向思考如果我想生成一個“保證有解的24點題目”可以先枚舉所有組合挑出語句結構優(yōu)雅、解法數適中的組合比如1~5個解的作為題庫。輸出成cards - expr的映射文件存成JSON可以直接作為小游戲的后端數據。擴展三多解匯總與解法排序對每個有解組合按“解法的復雜度”排序比如優(yōu)先展示只用加減、或只用乘除的簡潔解法把復雜的長表達式排后面。這需要定義復雜度分數最簡單的做法是統(tǒng)計表達式中運算符的種類數——種類越少越“優(yōu)雅”。擴展四可視化表達式樹把每個解對應的運算樹畫出來配合matplotlib或graphviz可以讓用戶直觀看到哪兩個數先算、哪兩個再算。該擴展對教學場景特別有用能幫助新手理解運算順序和括號的作用。7. 寫代碼時踩過的兩個坑最后分享兩個實際操作中印象深刻的坑。第一個坑是減法順序。RPN求值里先彈棧的是右操作數很多初版代碼在apply_op直接寫成a - b但變量名指代不清。我曾經在一個版本里把a、b搞反導致[1, 2, 3, 4]這種簡單輸入都解不出來。排查方法很簡單打印中間每一步的棧內容和計算結果肉眼對照一遍就知道哪一步算反了。寫算法題不要怕用print調試小邏輯越復雜越需要即時反饋。第二個坑是“形狀函數漏寫”。五種子結構對應五種二叉樹形態(tài)但只要漏掉任何一種某些特殊組合就會漏解。比如[1, 5, 5, 5]的經典解5 × (5 - 1 ÷ 5)依賴形狀4a op1 (b op2 (c op3 d))如果只實現了前三種形狀這個解就永遠找不到。把5個形狀函數都寫好之后我建議跑一個“全組合自檢”——遍歷1到13的所有四元組確保每種組合都能找到解或有明確無解的結論防止形狀遺漏。我在實際使用中發(fā)現枚舉法解決24點的經典之處不在于“寫得快”而在于“思路直白、便于驗證”。沒有復雜的貪心策略沒有狀態(tài)轉移方程就是老老實實列所有可能、算所有結果。對于算法入門的同學來說這個題目麻雀雖小五臟俱全有排列組合、有表達式解析、有精度處理、有去重邏輯是一道性價比極高的練手題。之后如果再做類似的窮舉類題目這套“枚舉維度劃分、中間結果緩存、路徑記錄”的套路可以反復套用。