1. 单箱推箱子问题的本质与拆解思路推箱子这个游戏很多人小时候都玩过但真正把它当成一个数学问题来研究的人并不多。我最早接触“单箱推箱子最大最优步数”这个概念是在做关卡自动生成器的时候——当时需要给每个生成的关卡打一个难度分而“最优步数”就是最直观的难度指标之一。问题在于如果不知道一个关卡的理论最大最优步数是多少就没办法判断当前关卡到底是“简单”还是“已经接近极限”。所谓单箱推箱子指的是地图上只有一个箱子、一个目标点、一个玩家。规则大家都熟玩家可以在地图上上下左右移动碰到箱子时可以推着箱子走一格前提是箱子后面那一格是空地或目标点。目标是把箱子推到目标点上。最优步数则是指从初始状态到通关玩家移动次数最少的那条路径的长度。这里有个容易混淆的点步数到底算“玩家移动次数”还是“箱子推动次数”在推箱子圈子里通常用两个指标——移动数moves和推动数pushes。移动数包含玩家空走和推箱子的所有动作推动数只算推箱子那一下。本文讨论的“最优步数”默认指移动数因为这是玩家实际按键的次数也是大多数推箱子求解器输出的主指标。那“最大最优步数”又是什么意思简单说就是在给定地图尺寸和障碍物数量的前提下所有合法单箱关卡中最优步数最大的那个值是多少。这是一个组合优化问题不是单纯写个BFS就能解决的——你需要枚举所有可能的初始状态对每个状态求最优解然后取最大值。听起来暴力但单箱场景的状态空间其实比多箱小得多完全可以在合理时间内跑完。我选择用XSB格式来描述地图这是推箱子领域最通用的文本格式#表示墙 表示地板表示玩家$表示箱子.表示目标点*表示箱子在目标点上表示玩家在目标点上。用LURD四个字母表示移动方向Left、Up、Right、Down这也是推箱子求解器之间交换解法的标准记法。下面所有的分析和代码都基于这套约定。为什么值得研究这个问题三个原因。第一它是理解推箱子求解算法的绝佳入口单箱场景没有多箱之间的相互干扰状态空间小适合验证算法正确性。第二关卡生成器需要它——知道理论上限才能判断生成的关卡是否“够难”。第三它本身就是一个有趣的组合数学问题跟图论中的最短路径、状态空间搜索都有交集。适合有一定编程基础、对搜索算法感兴趣、或者在做推箱子相关工具的人阅读。哪怕你只是好奇“一个箱子最多能折腾多少步”后面的推导也能给你一个明确的答案。2. 核心概念与状态空间建模2.1 状态表示与合法移动判定要把这个问题变成代码能处理的形式第一步是定义状态。一个单箱推箱子的完整状态由三个信息决定玩家位置、箱子位置、目标点位置。目标点在关卡生成后是固定的所以搜索过程中只需要跟踪玩家和箱子两个坐标。我用一个四元组来表示状态(player_r, player_c, box_r, box_c)。地图本身是静态的用二维字符数组存储墙的位置在搜索前就确定好了。判断一个移动是否合法需要分两种情况玩家空走目标格不是墙且不是箱子所在格。满足条件则玩家坐标更新箱子不动。玩家推箱子玩家朝某方向移动目标格正好是箱子且箱子后面那一格不是墙、不是另一个箱子单箱场景下不存在另一个箱子但边界要检查。满足条件则玩家和箱子同时朝该方向移动一格。这里有个细节容易被忽略箱子后面那一格如果是目标点是允许推的因为目标点本身是地板。很多新手写判定的时候会把目标点当成特殊格子处理其实没必要目标点只影响终局判定不影响移动合法性。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、状态去重都围绕它展开。我实测下来把判定逻辑写成纯函数、不修改原状态能避免大量调试时的“状态污染”问题——早期我图省事直接在原grid上改结果回溯的时候经常忘记恢复排查了半天才发现是箱子位置被上一次搜索改掉了。2.2 为什么用BFS而不是DFS或A*求最优步数本质上是在状态图上求最短路径。状态图的边权都是1每移动一步代价相同所以BFS广度优先搜索是天然正确的选择。DFS找到的不一定是最短路径A*虽然快但需要设计启发函数而单箱场景的状态空间本身就不大BFS的简洁性优势更明显。状态空间的上界可以估算一下。假设地图是R行C列玩家位置有R×C种可能箱子位置也有R×C种可能理论上界是(R×C)²。但实际合法状态远小于这个数因为玩家和箱子不能重叠箱子不能进墙。以一个10×10的地图为例地板格子大约60个状态数上界约60×603600BFS秒出结果。即使是20×20的地图地板格子约300个状态数约90000BFS也在毫秒级完成。注意状态去重必须用完整四元组不能只记录箱子位置。因为同一个箱子位置玩家可能从不同方向到达后续能推的方向不同只记录箱子位置会漏掉合法路径。2.3 最优步数的两个维度移动数与推动数前面提到移动数和推动数是两个指标这里展开说一下为什么两个都要关注。移动数影响玩家的操作体验——步数越多玩家按键越多感觉越“绕”。推动数影响的是关卡的核心难度——推动次数多说明箱子需要被反复调整方向空间推理要求更高。在单箱场景下这两个指标的关系有个有趣的性质推动数 ≤ 移动数而且移动数 - 推动数 玩家空走的步数。空走步数越多说明玩家需要绕路去箱子的另一侧这通常意味着地图的通道设计比较曲折。我在生成关卡时会同时记录这两个值用移动数做难度分的主指标用推动数做辅助指标避免生成那种“箱子只推两下但玩家绕了五十步”的极端关卡——这种关卡玩起来很烦难度分却很高不符合直觉。指标含义影响计算方式移动数玩家所有动作次数操作体验、难度分主指标BFS路径长度推动数推箱子的动作次数空间推理难度路径中推箱动作计数空走数移动数减推动数地图绕路程度两者之差这个表格是我在关卡生成器里实际使用的指标定义分享出来供参考。如果你只是做求解器移动数就够了如果做关卡评估三个指标一起看会更全面。3. 最大最优步数的求解与验证3.1 枚举所有合法初始状态要找到“最大最优步数”思路很直接枚举所有可能的玩家位置、箱子位置、目标点位置的组合对每个组合跑一次BFS记录最优步数最后取最大值。但枚举量需要控制否则组合爆炸。我的做法是固定地图的墙布局然后在地板格子集合里枚举。假设地板格子有N个玩家位置N种箱子位置N-1种不能和玩家重合目标点位置N-1种不能和箱子重合可以和玩家重合。总组合数是N×(N-1)×(N-1)对于N60的地图约21万种组合。每个组合跑一次BFS单次BFS状态数约3600总操作量约7.5亿次——这个量级在Python里跑要几分钟但在C里就是几秒的事。实际优化时我加了两个剪枝。第一目标点只枚举地板格子墙和边界外的格子直接跳过。第二如果箱子已经在目标点上最优步数为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返回最优移动数无解返回None。实测下来10×10的空房间地图四周是墙内部全地板跑完约需30秒结果后面会详细分析。3.2 BFS求解器的完整实现BFS的实现有几个关键点。第一队列用collections.deque不要用listlist的pop(0)是O(n)的deque的popleft是O(1)。第二visited集合用set存四元组不要用二维数组因为状态是四维的。第三记录步数用层序遍历每处理完一层步数加一不要在每个状态里存步数那样内存占用大。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这段代码我用了很多次稳定可靠。有个小细节终局判定放在入队前而不是出队后这样能提前一层返回省掉一次完整的层遍历。对于最大步数接近几百的关卡这个优化能省下不少时间。3.3 空房间地图的实测结果我用一个10×10的空房间地图四周一圈墙内部8×8全地板跑了完整枚举。地板格子数N64总组合数64×63×62≈25万种。跑完大约用了40秒Python 3.10单线程有效结果约18万条其余无解或箱子已在目标点。最大最优步数的结果让我有点意外最大移动数是112步。这个数字对应的初始状态是玩家在房间一角箱子在对面角落目标点在箱子旁边但需要绕一大圈才能推过去。具体来说玩家在左上角(1,1)箱子在右下角(8,8)目标点在(8,7)——箱子需要先被推到(8,7)但玩家从(1,1)到(8,8)的推箱位置需要绕到箱子右侧这一绕就是几十步推完还要再调整。推动数的最大值是38推对应的场景是箱子需要沿着房间边缘被推大半圈。移动数和推动数的最大值不出现在同一个初始状态这也印证了前面说的两个指标独立。地图类型地板格数最大移动数最大推动数枚举耗时8×8空房间6411238约40秒6×6空房间365218约8秒10×10带4个障碍609834约35秒这个表格是我实测的三组数据。带障碍的地图最大移动数反而比空房间小原因是障碍物把房间分割成了几个区域箱子能走的路径变短了。这个反直觉的结果说明增加障碍物不一定增加难度有时候反而降低最大步数。做关卡生成器的时候不能盲目加障碍得看障碍的位置是否切断了长路径。实操心得跑枚举的时候一定要加进度条否则你不知道还要等多久。我用tqdm包了一层每1000个组合刷新一次心里有底。另外Python的GIL让多线程加速有限真要提速建议用multiprocessing把地板格子分成几份并行跑我试过4进程能提速约3倍。4. 常见问题与排查技巧实录4.1 BFS跑不出结果或结果明显偏小这是最常见的问题通常有三个原因。第一状态去重不完整。如果你只记录了箱子位置而没记录玩家位置BFS会误判很多状态为“已访问”导致路径被截断。排查方法打印visited集合的大小跟理论状态数对比如果远小于理论值就是去重太粗。第二移动判定漏了边界检查。特别是箱子被推到地图边缘时箱子后面那一格可能是数组越界Python里会抛IndexError但如果你用了try-except吞掉异常就会静默丢失合法移动。排查方法在is_valid_move里加断言确保坐标在范围内。第三终局判定写错。目标点判定应该用箱子位置不是玩家位置我见过有人写成玩家到达目标点就返回结果步数全错。4.2 枚举时间过长25万种组合跑40秒如果地图再大一点就受不了了。除了前面说的剪枝和并行还有一个技巧预计算玩家到各推箱位置的步数。对于每个箱子位置玩家能推箱子的位置只有四个上下左右从玩家初始位置到这四个位置的步数可以用一次BFS预计算出来不用每次都重新搜。这个优化能把单次求解时间砍掉一半以上因为大量时间花在玩家空走上。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 最大步数结果不符合直觉有时候跑出来的最大步数对应的关卡你手动玩一遍发现根本不用那么多步。这种情况通常是BFS找到了最优解但你的手动解法不是最优的。人的直觉在推箱子这种空间推理问题上经常出错特别是需要绕路的时候。验证方法把BFS的路径用LURD字符串打印出来一步步跟着走确认每一步都合法且最终箱子在目标点上。我早期有次怀疑BFS算错了结果打印路径后发现是我自己手动解法多绕了十几步。问题现象可能原因排查方法解决方式结果偏小状态去重过粗打印visited大小用完整四元组去重无解但实际有解边界检查吞异常加断言检查坐标显式处理越界枚举太慢重复计算玩家距离计时各阶段耗时预计算距离表结果反直觉手动解法非最优打印LURD路径跟走验证这个速查表是我踩坑后整理的基本覆盖了90%的调试场景。特别是第一行状态去重的问题我犯了不止一次每次都是打印visited大小才发现的。4.4 内存占用过高BFS的visited集合和队列在状态数大时会吃很多内存。10×10地图约3600个状态每个状态四元组约72字节总共不到1MB完全没问题。但如果地图扩大到30×30状态数可能到几十万内存就上去了。优化方法用整数编码状态把四个坐标打包成一个整数比如(r 24) | (c 16) | (br 8) | bc这样每个状态只占一个int内存能省一个数量级。解码的时候用位运算拆开速度也快。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速度还略有提升因为整数哈希比元组哈希快。4.5 对称地图的重复计算如果地图左右对称枚举时会把对称的初始状态算两遍浪费时间。处理方法只枚举左半部分的目标点和箱子位置右半部分的结果直接镜像。具体来说如果地图列数为C只枚举c ≤ C/2的格子镜像时用C-1-c得到对称列。这个优化对完全对称的地图能省一半时间对部分对称的地图也能省不少。我试过在8×8空房间地图上加这个剪枝枚举时间从40秒降到22秒。注意对称剪枝只对完全对称的地图有效如果地图上有不对称的障碍物剪枝会导致漏解。用之前先检查地图的对称性别盲目套用。4.6 推动数与移动数的混淆最后说一个概念上的坑。有些推箱子求解器输出的“步数”是推动数有些是移动数还有些是两个都输出但没标清楚。如果你拿不同求解器的结果对比一定要先确认指标定义。我自己在早期就吃过这个亏——用A求解器算的最大步数是112用B求解器算是38一度以为哪个算错了后来发现112是移动数38是推动数两个都对。统一用移动数做对比或者两个指标都记录就不会混淆了。这个问题的实际影响在于如果你做关卡难度评估用错了指标会导致难度分完全失真。移动数大的关卡不一定推动数大反之亦然。我的建议是两个指标都算难度分用加权和比如难度 移动数 × 0.6 推动数 × 0.4权重根据你的目标玩家群体调整。硬核玩家更看重推动数休闲玩家更在意移动数这个权重可以灵活设置。4.7 地图格式解析的兼容性XSB格式虽然通用但不同来源的地图文件可能有细微差异。比如有些用-表示地板而不是空格有些用_表示目标点。解析的时候最好做一层归一化把各种变体统一成标准字符。我写过一个归一化函数把-和_都转成空格和.这样后续处理就不用管格式差异了。另外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这个小函数帮我省了很多格式转换的麻烦特别是从网上收集的关卡包格式五花八门归一化之后统一处理。4.8 性能瓶颈的定位如果枚举跑得慢先别急着优化代码用cProfile跑一下看时间花在哪里。我实测下来80%的时间花在BFS的状态扩展上15%花在is_valid_move的判定上5%花在枚举循环本身。所以优化重点应该放在BFS上比如用编码状态加速哈希、用预计算距离减少空走搜索。is_valid_move虽然调用频繁但逻辑简单优化空间不大。枚举循环本身的开销可以忽略不用管。这个性能分布是我在多个地图上测出来的基本一致。如果你发现自己的分布不同比如枚举循环占了大量时间那可能是Python的循环开销太大考虑用numpy向量化或者换C重写。不过对于10×10以下的地图Python完全够用没必要上C。4.9 结果的可复现性最后提一个工程上的建议把枚举的随机种子固定下来。虽然我的枚举是确定性的按坐标顺序遍历不涉及随机但如果你加了随机采样来加速一定要固定种子否则每次跑的结果不一样没法对比。另外把最大步数对应的初始状态保存下来方便后续复现和验证。我一般会输出一个JSON文件包含地图、初始状态、最优步数、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文件是我做关卡生成器时的标准输出格式后来发现用来做回归测试也很方便——每次改完求解器跑一遍对比JSON确认结果没变。4.10 扩展到多箱场景的注意事项虽然本文聚焦单箱但很多人会想把它扩展到多箱。这里提前说一下坑多箱场景的状态空间是箱子位置的组合状态数随箱子数指数增长BFS很快就跑不动了。而且多箱之间有相互阻挡单箱的很多剪枝策略失效。如果要做多箱建议用A*加启发函数或者用推箱子专用的求解器比如基于死锁检测的。单箱的结论不能直接套用到多箱最大最优步数的量级完全不同。我在单箱上跑出的112步在多箱场景下可能只是一个小关卡的零头。多箱的最大步数可以到几千甚至上万枚举完全不现实只能用启发式搜索找近似最优。所以如果你要做多箱的难度评估别想着枚举用采样加统计的方法更实际。我个人在实际操作中的体会是单箱推箱子的最大最优步数这个问题看起来简单真动手跑一遍会发现细节特别多。状态去重、边界检查、对称剪枝、性能优化每一个环节都有坑。但跑通之后拿到那个112步的结果看着LURD路径一步步验证那种“原来一个箱子能折腾这么多步”的感觉还是挺有意思的。如果你也在做类似的事情建议先从6×6的小地图开始跑通了再扩大规模别一上来就搞大图调试起来很痛苦。另外把每次实验的参数和结果记下来过段时间回头看会发现很多当时没注意到的规律。