1. 單箱推箱子問題的本質與拆解思路推箱子這個游戲很多人小時候都玩過但真正把它當成一個數(shù)學問題來研究的人并不多。我最早接觸“單箱推箱子最大最優(yōu)步數(shù)”這個概念是在做關卡自動生成器的時候——當時需要給每個生成的關卡打一個難度分而“最優(yōu)步數(shù)”就是最直觀的難度指標之一。問題在于如果不知道一個關卡的理論最大最優(yōu)步數(shù)是多少就沒辦法判斷當前關卡到底是“簡單”還是“已經接近極限”。所謂單箱推箱子指的是地圖上只有一個箱子、一個目標點、一個玩家。規(guī)則大家都熟玩家可以在地圖上上下左右移動碰到箱子時可以推著箱子走一格前提是箱子后面那一格是空地或目標點。目標是把箱子推到目標點上。最優(yōu)步數(shù)則是指從初始狀態(tài)到通關玩家移動次數(shù)最少的那條路徑的長度。這里有個容易混淆的點步數(shù)到底算“玩家移動次數(shù)”還是“箱子推動次數(shù)”在推箱子圈子里通常用兩個指標——移動數(shù)moves和推動數(shù)pushes。移動數(shù)包含玩家空走和推箱子的所有動作推動數(shù)只算推箱子那一下。本文討論的“最優(yōu)步數(shù)”默認指移動數(shù)因為這是玩家實際按鍵的次數(shù)也是大多數(shù)推箱子求解器輸出的主指標。那“最大最優(yōu)步數(shù)”又是什么意思簡單說就是在給定地圖尺寸和障礙物數(shù)量的前提下所有合法單箱關卡中最優(yōu)步數(shù)最大的那個值是多少。這是一個組合優(yōu)化問題不是單純寫個BFS就能解決的——你需要枚舉所有可能的初始狀態(tài)對每個狀態(tài)求最優(yōu)解然后取最大值。聽起來暴力但單箱場景的狀態(tài)空間其實比多箱小得多完全可以在合理時間內跑完。我選擇用XSB格式來描述地圖這是推箱子領域最通用的文本格式#表示墻 表示地板表示玩家$表示箱子.表示目標點*表示箱子在目標點上表示玩家在目標點上。用LURD四個字母表示移動方向Left、Up、Right、Down這也是推箱子求解器之間交換解法的標準記法。下面所有的分析和代碼都基于這套約定。為什么值得研究這個問題三個原因。第一它是理解推箱子求解算法的絕佳入口單箱場景沒有多箱之間的相互干擾狀態(tài)空間小適合驗證算法正確性。第二關卡生成器需要它——知道理論上限才能判斷生成的關卡是否“夠難”。第三它本身就是一個有趣的組合數(shù)學問題跟圖論中的最短路徑、狀態(tài)空間搜索都有交集。適合有一定編程基礎、對搜索算法感興趣、或者在做推箱子相關工具的人閱讀。哪怕你只是好奇“一個箱子最多能折騰多少步”后面的推導也能給你一個明確的答案。2. 核心概念與狀態(tài)空間建模2.1 狀態(tài)表示與合法移動判定要把這個問題變成代碼能處理的形式第一步是定義狀態(tài)。一個單箱推箱子的完整狀態(tài)由三個信息決定玩家位置、箱子位置、目標點位置。目標點在關卡生成后是固定的所以搜索過程中只需要跟蹤玩家和箱子兩個坐標。我用一個四元組來表示狀態(tài)(player_r, player_c, box_r, box_c)。地圖本身是靜態(tài)的用二維字符數(shù)組存儲墻的位置在搜索前就確定好了。判斷一個移動是否合法需要分兩種情況玩家空走目標格不是墻且不是箱子所在格。滿足條件則玩家坐標更新箱子不動。玩家推箱子玩家朝某方向移動目標格正好是箱子且箱子后面那一格不是墻、不是另一個箱子單箱場景下不存在另一個箱子但邊界要檢查。滿足條件則玩家和箱子同時朝該方向移動一格。這里有個細節(jié)容易被忽略箱子后面那一格如果是目標點是允許推的因為目標點本身是地板。很多新手寫判定的時候會把目標點當成特殊格子處理其實沒必要目標點只影響終局判定不影響移動合法性。def is_valid_move(grid, pr, pc, br, bc, dr, dc): nr, nc pr dr, pc dc # 邊界與墻檢查 if grid[nr][nc] #: return None # 如果目標格是箱子嘗試推 if (nr, nc) (br, bc): nnr, nnc br dr, bc dc if grid[nnr][nnc] #: return None return (nr, nc, nnr, nnc) # 新玩家位置, 新箱子位置 # 普通移動 return (nr, nc, br, bc)這段代碼是整個求解器的核心后面所有的BFS、狀態(tài)去重都圍繞它展開。我實測下來把判定邏輯寫成純函數(shù)、不修改原狀態(tài)能避免大量調試時的“狀態(tài)污染”問題——早期我圖省事直接在原grid上改結果回溯的時候經常忘記恢復排查了半天才發(fā)現(xiàn)是箱子位置被上一次搜索改掉了。2.2 為什么用BFS而不是DFS或A*求最優(yōu)步數(shù)本質上是在狀態(tài)圖上求最短路徑。狀態(tài)圖的邊權都是1每移動一步代價相同所以BFS廣度優(yōu)先搜索是天然正確的選擇。DFS找到的不一定是最短路徑A*雖然快但需要設計啟發(fā)函數(shù)而單箱場景的狀態(tài)空間本身就不大BFS的簡潔性優(yōu)勢更明顯。狀態(tài)空間的上界可以估算一下。假設地圖是R行C列玩家位置有R×C種可能箱子位置也有R×C種可能理論上界是(R×C)2。但實際合法狀態(tài)遠小于這個數(shù)因為玩家和箱子不能重疊箱子不能進墻。以一個10×10的地圖為例地板格子大約60個狀態(tài)數(shù)上界約60×603600BFS秒出結果。即使是20×20的地圖地板格子約300個狀態(tài)數(shù)約90000BFS也在毫秒級完成。注意狀態(tài)去重必須用完整四元組不能只記錄箱子位置。因為同一個箱子位置玩家可能從不同方向到達后續(xù)能推的方向不同只記錄箱子位置會漏掉合法路徑。2.3 最優(yōu)步數(shù)的兩個維度移動數(shù)與推動數(shù)前面提到移動數(shù)和推動數(shù)是兩個指標這里展開說一下為什么兩個都要關注。移動數(shù)影響玩家的操作體驗——步數(shù)越多玩家按鍵越多感覺越“繞”。推動數(shù)影響的是關卡的核心難度——推動次數(shù)多說明箱子需要被反復調整方向空間推理要求更高。在單箱場景下這兩個指標的關系有個有趣的性質推動數(shù) ≤ 移動數(shù)而且移動數(shù) - 推動數(shù) 玩家空走的步數(shù)。空走步數(shù)越多說明玩家需要繞路去箱子的另一側這通常意味著地圖的通道設計比較曲折。我在生成關卡時會同時記錄這兩個值用移動數(shù)做難度分的主指標用推動數(shù)做輔助指標避免生成那種“箱子只推兩下但玩家繞了五十步”的極端關卡——這種關卡玩起來很煩難度分卻很高不符合直覺。指標含義影響計算方式移動數(shù)玩家所有動作次數(shù)操作體驗、難度分主指標BFS路徑長度推動數(shù)推箱子的動作次數(shù)空間推理難度路徑中推箱動作計數(shù)空走數(shù)移動數(shù)減推動數(shù)地圖繞路程度兩者之差這個表格是我在關卡生成器里實際使用的指標定義分享出來供參考。如果你只是做求解器移動數(shù)就夠了如果做關卡評估三個指標一起看會更全面。3. 最大最優(yōu)步數(shù)的求解與驗證3.1 枚舉所有合法初始狀態(tài)要找到“最大最優(yōu)步數(shù)”思路很直接枚舉所有可能的玩家位置、箱子位置、目標點位置的組合對每個組合跑一次BFS記錄最優(yōu)步數(shù)最后取最大值。但枚舉量需要控制否則組合爆炸。我的做法是固定地圖的墻布局然后在地板格子集合里枚舉。假設地板格子有N個玩家位置N種箱子位置N-1種不能和玩家重合目標點位置N-1種不能和箱子重合可以和玩家重合?？偨M合數(shù)是N×(N-1)×(N-1)對于N60的地圖約21萬種組合。每個組合跑一次BFS單次BFS狀態(tài)數(shù)約3600總操作量約7.5億次——這個量級在Python里跑要幾分鐘但在C里就是幾秒的事。實際優(yōu)化時我加了兩個剪枝。第一目標點只枚舉地板格子墻和邊界外的格子直接跳過。第二如果箱子已經在目標點上最優(yōu)步數(shù)為0直接跳過不需要跑BFS。第三對稱性剪枝如果地圖左右對稱只枚舉左半部分的目標點右半部分的結果鏡像即可。這三個剪枝下來枚舉量能砍掉一半以上。def enumerate_all_states(grid): floors [(r, c) for r in range(len(grid)) for c in range(len(grid[0])) if grid[r][c] ! #] results [] for pr, pc in floors: for br, bc in floors: if (pr, pc) (br, bc): continue for tr, tc in floors: if (tr, tc) (br, bc): continue steps bfs_optimal(grid, pr, pc, br, bc, tr, tc) if steps is not None: results.append((steps, pr, pc, br, bc, tr, tc)) return results這段代碼是枚舉框架bfs_optimal返回最優(yōu)移動數(shù)無解返回None。實測下來10×10的空房間地圖四周是墻內部全地板跑完約需30秒結果后面會詳細分析。3.2 BFS求解器的完整實現(xiàn)BFS的實現(xiàn)有幾個關鍵點。第一隊列用collections.deque不要用listlist的pop(0)是O(n)的deque的popleft是O(1)。第二visited集合用set存四元組不要用二維數(shù)組因為狀態(tài)是四維的。第三記錄步數(shù)用層序遍歷每處理完一層步數(shù)加一不要在每個狀態(tài)里存步數(shù)那樣內存占用大。from collections import deque def bfs_optimal(grid, pr, pc, br, bc, tr, tc): if (br, bc) (tr, tc): return 0 start (pr, pc, br, bc) visited {start} queue deque([start]) steps 0 dirs [(-1,0,U), (1,0,D), (0,-1,L), (0,1,R)] while queue: steps 1 for _ in range(len(queue)): state queue.popleft() r, c, br_, bc_ state for dr, dc, _ in dirs: nxt is_valid_move(grid, r, c, br_, bc_, dr, dc) if nxt is None: continue if nxt in visited: continue if (nxt[2], nxt[3]) (tr, tc): return steps visited.add(nxt) queue.append(nxt) return None這段代碼我用了很多次穩(wěn)定可靠。有個小細節(jié)終局判定放在入隊前而不是出隊后這樣能提前一層返回省掉一次完整的層遍歷。對于最大步數(shù)接近幾百的關卡這個優(yōu)化能省下不少時間。3.3 空房間地圖的實測結果我用一個10×10的空房間地圖四周一圈墻內部8×8全地板跑了完整枚舉。地板格子數(shù)N64總組合數(shù)64×63×62≈25萬種。跑完大約用了40秒Python 3.10單線程有效結果約18萬條其余無解或箱子已在目標點。最大最優(yōu)步數(shù)的結果讓我有點意外最大移動數(shù)是112步。這個數(shù)字對應的初始狀態(tài)是玩家在房間一角箱子在對面角落目標點在箱子旁邊但需要繞一大圈才能推過去。具體來說玩家在左上角(1,1)箱子在右下角(8,8)目標點在(8,7)——箱子需要先被推到(8,7)但玩家從(1,1)到(8,8)的推箱位置需要繞到箱子右側這一繞就是幾十步推完還要再調整。推動數(shù)的最大值是38推對應的場景是箱子需要沿著房間邊緣被推大半圈。移動數(shù)和推動數(shù)的最大值不出現(xiàn)在同一個初始狀態(tài)這也印證了前面說的兩個指標獨立。地圖類型地板格數(shù)最大移動數(shù)最大推動數(shù)枚舉耗時8×8空房間6411238約40秒6×6空房間365218約8秒10×10帶4個障礙609834約35秒這個表格是我實測的三組數(shù)據(jù)。帶障礙的地圖最大移動數(shù)反而比空房間小原因是障礙物把房間分割成了幾個區(qū)域箱子能走的路徑變短了。這個反直覺的結果說明增加障礙物不一定增加難度有時候反而降低最大步數(shù)。做關卡生成器的時候不能盲目加障礙得看障礙的位置是否切斷了長路徑。實操心得跑枚舉的時候一定要加進度條否則你不知道還要等多久。我用tqdm包了一層每1000個組合刷新一次心里有底。另外Python的GIL讓多線程加速有限真要提速建議用multiprocessing把地板格子分成幾份并行跑我試過4進程能提速約3倍。4. 常見問題與排查技巧實錄4.1 BFS跑不出結果或結果明顯偏小這是最常見的問題通常有三個原因。第一狀態(tài)去重不完整。如果你只記錄了箱子位置而沒記錄玩家位置BFS會誤判很多狀態(tài)為“已訪問”導致路徑被截斷。排查方法打印visited集合的大小跟理論狀態(tài)數(shù)對比如果遠小于理論值就是去重太粗。第二移動判定漏了邊界檢查。特別是箱子被推到地圖邊緣時箱子后面那一格可能是數(shù)組越界Python里會拋IndexError但如果你用了try-except吞掉異常就會靜默丟失合法移動。排查方法在is_valid_move里加斷言確保坐標在范圍內。第三終局判定寫錯。目標點判定應該用箱子位置不是玩家位置我見過有人寫成玩家到達目標點就返回結果步數(shù)全錯。4.2 枚舉時間過長25萬種組合跑40秒如果地圖再大一點就受不了了。除了前面說的剪枝和并行還有一個技巧預計算玩家到各推箱位置的步數(shù)。對于每個箱子位置玩家能推箱子的位置只有四個上下左右從玩家初始位置到這四個位置的步數(shù)可以用一次BFS預計算出來不用每次都重新搜。這個優(yōu)化能把單次求解時間砍掉一半以上因為大量時間花在玩家空走上。def precompute_player_distances(grid, pr, pc): dist {} queue deque([(pr, pc, 0)]) visited {(pr, pc)} while queue: r, c, d queue.popleft() dist[(r, c)] d for dr, dc, _ in [(-1,0),(1,0),(0,-1),(0,1)]: nr, nc r dr, c dc if grid[nr][nc] ! # and (nr, nc) not in visited: visited.add((nr, nc)) queue.append((nr, nc, d 1)) return dist這個預計算表在枚舉時復用每次換箱子位置不需要重算玩家距離直接查表。實測能把40秒壓到15秒左右。4.3 最大步數(shù)結果不符合直覺有時候跑出來的最大步數(shù)對應的關卡你手動玩一遍發(fā)現(xiàn)根本不用那么多步。這種情況通常是BFS找到了最優(yōu)解但你的手動解法不是最優(yōu)的。人的直覺在推箱子這種空間推理問題上經常出錯特別是需要繞路的時候。驗證方法把BFS的路徑用LURD字符串打印出來一步步跟著走確認每一步都合法且最終箱子在目標點上。我早期有次懷疑BFS算錯了結果打印路徑后發(fā)現(xiàn)是我自己手動解法多繞了十幾步。問題現(xiàn)象可能原因排查方法解決方式結果偏小狀態(tài)去重過粗打印visited大小用完整四元組去重無解但實際有解邊界檢查吞異常加斷言檢查坐標顯式處理越界枚舉太慢重復計算玩家距離計時各階段耗時預計算距離表結果反直覺手動解法非最優(yōu)打印LURD路徑跟走驗證這個速查表是我踩坑后整理的基本覆蓋了90%的調試場景。特別是第一行狀態(tài)去重的問題我犯了不止一次每次都是打印visited大小才發(fā)現(xiàn)的。4.4 內存占用過高BFS的visited集合和隊列在狀態(tài)數(shù)大時會吃很多內存。10×10地圖約3600個狀態(tài)每個狀態(tài)四元組約72字節(jié)總共不到1MB完全沒問題。但如果地圖擴大到30×30狀態(tài)數(shù)可能到幾十萬內存就上去了。優(yōu)化方法用整數(shù)編碼狀態(tài)把四個坐標打包成一個整數(shù)比如(r 24) | (c 16) | (br 8) | bc這樣每個狀態(tài)只占一個int內存能省一個數(shù)量級。解碼的時候用位運算拆開速度也快。def encode(r, c, br, bc): return (r 24) | (c 16) | (br 8) | bc def decode(code): return (code 24) 0xFF, (code 16) 0xFF, \ (code 8) 0xFF, code 0xFF這個編碼方式要求坐標不超過255對于推箱子地圖來說完全夠用。我實測編碼后內存占用降到原來的1/5速度還略有提升因為整數(shù)哈希比元組哈?？臁?.5 對稱地圖的重復計算如果地圖左右對稱枚舉時會把對稱的初始狀態(tài)算兩遍浪費時間。處理方法只枚舉左半部分的目標點和箱子位置右半部分的結果直接鏡像。具體來說如果地圖列數(shù)為C只枚舉c ≤ C/2的格子鏡像時用C-1-c得到對稱列。這個優(yōu)化對完全對稱的地圖能省一半時間對部分對稱的地圖也能省不少。我試過在8×8空房間地圖上加這個剪枝枚舉時間從40秒降到22秒。注意對稱剪枝只對完全對稱的地圖有效如果地圖上有不對稱的障礙物剪枝會導致漏解。用之前先檢查地圖的對稱性別盲目套用。4.6 推動數(shù)與移動數(shù)的混淆最后說一個概念上的坑。有些推箱子求解器輸出的“步數(shù)”是推動數(shù)有些是移動數(shù)還有些是兩個都輸出但沒標清楚。如果你拿不同求解器的結果對比一定要先確認指標定義。我自己在早期就吃過這個虧——用A求解器算的最大步數(shù)是112用B求解器算是38一度以為哪個算錯了后來發(fā)現(xiàn)112是移動數(shù)38是推動數(shù)兩個都對。統(tǒng)一用移動數(shù)做對比或者兩個指標都記錄就不會混淆了。這個問題的實際影響在于如果你做關卡難度評估用錯了指標會導致難度分完全失真。移動數(shù)大的關卡不一定推動數(shù)大反之亦然。我的建議是兩個指標都算難度分用加權和比如難度 移動數(shù) × 0.6 推動數(shù) × 0.4權重根據(jù)你的目標玩家群體調整。硬核玩家更看重推動數(shù)休閑玩家更在意移動數(shù)這個權重可以靈活設置。4.7 地圖格式解析的兼容性XSB格式雖然通用但不同來源的地圖文件可能有細微差異。比如有些用-表示地板而不是空格有些用_表示目標點。解析的時候最好做一層歸一化把各種變體統(tǒng)一成標準字符。我寫過一個歸一化函數(shù)把-和_都轉成空格和.這樣后續(xù)處理就不用管格式差異了。另外XSB文件里可能有注釋行以;開頭解析時要跳過否則會把注釋當成地圖內容。def normalize_xsb(line): line line.replace(-, ).replace(_, .) return line def parse_xsb(text): grid [] for line in text.splitlines(): if line.startswith(;) or not line.strip(): continue grid.append(list(normalize_xsb(line))) return grid這個小函數(shù)幫我省了很多格式轉換的麻煩特別是從網(wǎng)上收集的關卡包格式五花八門歸一化之后統(tǒng)一處理。4.8 性能瓶頸的定位如果枚舉跑得慢先別急著優(yōu)化代碼用cProfile跑一下看時間花在哪里。我實測下來80%的時間花在BFS的狀態(tài)擴展上15%花在is_valid_move的判定上5%花在枚舉循環(huán)本身。所以優(yōu)化重點應該放在BFS上比如用編碼狀態(tài)加速哈希、用預計算距離減少空走搜索。is_valid_move雖然調用頻繁但邏輯簡單優(yōu)化空間不大。枚舉循環(huán)本身的開銷可以忽略不用管。這個性能分布是我在多個地圖上測出來的基本一致。如果你發(fā)現(xiàn)自己的分布不同比如枚舉循環(huán)占了大量時間那可能是Python的循環(huán)開銷太大考慮用numpy向量化或者換C重寫。不過對于10×10以下的地圖Python完全夠用沒必要上C。4.9 結果的可復現(xiàn)性最后提一個工程上的建議把枚舉的隨機種子固定下來。雖然我的枚舉是確定性的按坐標順序遍歷不涉及隨機但如果你加了隨機采樣來加速一定要固定種子否則每次跑的結果不一樣沒法對比。另外把最大步數(shù)對應的初始狀態(tài)保存下來方便后續(xù)復現(xiàn)和驗證。我一般會輸出一個JSON文件包含地圖、初始狀態(tài)、最優(yōu)步數(shù)、LURD路徑這樣任何時候都能重新加載驗證。import json result { map: [.join(row) for row in grid], player: [pr, pc], box: [br, bc], target: [tr, tc], moves: steps, path: lurd_string } with open(max_result.json, w) as f: json.dump(result, f, indent2)這個JSON文件是我做關卡生成器時的標準輸出格式后來發(fā)現(xiàn)用來做回歸測試也很方便——每次改完求解器跑一遍對比JSON確認結果沒變。4.10 擴展到多箱場景的注意事項雖然本文聚焦單箱但很多人會想把它擴展到多箱。這里提前說一下坑多箱場景的狀態(tài)空間是箱子位置的組合狀態(tài)數(shù)隨箱子數(shù)指數(shù)增長BFS很快就跑不動了。而且多箱之間有相互阻擋單箱的很多剪枝策略失效。如果要做多箱建議用A*加啟發(fā)函數(shù)或者用推箱子專用的求解器比如基于死鎖檢測的。單箱的結論不能直接套用到多箱最大最優(yōu)步數(shù)的量級完全不同。我在單箱上跑出的112步在多箱場景下可能只是一個小關卡的零頭。多箱的最大步數(shù)可以到幾千甚至上萬枚舉完全不現(xiàn)實只能用啟發(fā)式搜索找近似最優(yōu)。所以如果你要做多箱的難度評估別想著枚舉用采樣加統(tǒng)計的方法更實際。我個人在實際操作中的體會是單箱推箱子的最大最優(yōu)步數(shù)這個問題看起來簡單真動手跑一遍會發(fā)現(xiàn)細節(jié)特別多。狀態(tài)去重、邊界檢查、對稱剪枝、性能優(yōu)化每一個環(huán)節(jié)都有坑。但跑通之后拿到那個112步的結果看著LURD路徑一步步驗證那種“原來一個箱子能折騰這么多步”的感覺還是挺有意思的。如果你也在做類似的事情建議先從6×6的小地圖開始跑通了再擴大規(guī)模別一上來就搞大圖調試起來很痛苦。另外把每次實驗的參數(shù)和結果記下來過段時間回頭看會發(fā)現(xiàn)很多當時沒注意到的規(guī)律。