一、游戏介绍与问题建模
推箱子（Sokoban）是一款经典的益智游戏，最早由日本游戏设计师 Thinking Rabbit 于 1982 年发布。游戏的核心玩法非常简单：玩家控制一个工人，在仓库中将所有箱子推到指定的目标位置上。
1.1 游戏规则
推箱子的基本规则：
- 工人（Player）：可以上下左右移动，每次移动一格
- 箱子（Box）：工人可以推动箱子，但不能拉动箱子
- 墙壁（Wall）：不可穿越的障碍物
- 目标点（Goal）：箱子需要被推到的位置
- 胜利条件：所有箱子都位于目标点上
几个关键约束：
1. 工人一次只能推一个箱子（不能同时推两个相邻的箱子）
2. 箱子不能推入墙壁或另一个箱子的位置
3. 工人不能穿过箱子或墙壁
1.2 问题建模
将推箱子问题抽象为图搜索问题：
- 状态（State）：工人位置 + 所有箱子的位置集合
- 动作（Action）：工人向上/下/左/右移动一格
- 如果移动方向上有箱子且箱子前方为空，则推动箱子
- 如果移动方向上为空，则工人单纯移动
- 状态转移：通过合法动作从一个状态转移到另一个状态
- 初始状态：给定的关卡布局
- 目标状态：所有箱子都在目标点上
这是一个典型的最短路径问题，因为每步移动代价相同，我们需要找到从初始状态到目标状态的最少步数。
1.3 状态空间规模
推箱子的状态空间非常庞大。对于一个典型的 10×10 关卡，假设有 5 个箱子，状态空间的理论上限约为：
工人位置数 × 箱子位置组合数 ≈ 100 × C(100, 5) ≈ 7.5亿
实际可达状态数远小于理论值，但仍然是一个巨大的搜索空间。这也是为什么需要死锁检测等剪枝技术的原因——许多状态虽然合法，但已经不可能到达目标状态，可以提前排除。
二、状态表示与编码
高效的状态表示是算法性能的关键。推箱子的状态由工人位置和箱子位置共同决定，我们需要一种紧凑且便于哈希比较的编码方式。
2.1 关卡表示
使用二维字符数组表示关卡地图：
'#' = 墙壁 (Wall)
' ' = 空地 (Floor)
'.' = 目标点 (Goal)
'$' = 箱子 (Box)
'*' = 箱子在目标点上 (Box on Goal)
'@' = 工人 (Player)
'+' = 工人在目标点上 (Player on Goal)
2.2 状态编码设计
推箱子状态由两部分组成：工人位置 + 箱子位置集合。由于箱子是不可区分的（交换两个箱子的位置不产生新状态），我们需要对箱子位置进行排序后再编码。
/**
* 状态类：封装工人位置和箱子位置集合
* 实现 equals 和 hashCode 用于 HashSet 去重
*/
class SokobanState {
int playerX, playerY; // 工人位置
int[] boxPositions; // 箱子位置（排序后的一维编码）
public SokobanState(int playerX, int playerY, int[] boxPositions) {
this.playerX = playerX;
this.playerY = playerY;
this.boxPositions = boxPositions.clone();
Arrays.sort(this.boxPositions); // 排序确保相同箱子集合的编码一致
}
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (!(o instanceof SokobanState)) return false;
SokobanState other = (SokobanState) o;
return playerX == other.playerX
&& playerY == other.playerY
&& Arrays.equals(boxPositions, other.boxPositions);
}
@Override
public int hashCode() {
int result = Objects.hash(playerX, playerY);
result = 31 * result + Arrays.hashCode(boxPositions);
return result;
}
}
2.3 位置编码优化
为了提高效率，我们将二维坐标 (x, y) 编码为一维整数：
/**
* 将二维坐标编码为一维整数
* 假设地图宽度不超过 256，y 占高 16 位，x 占低 16 位
*/
public static int encodePos(int x, int y) {
return (y << 16) | x;
}
/**
* 从一维编码解码 x 坐标
*/
public static int decodeX(int code) {
return code & 0xFFFF;
}
/**
* 从一维编码解码 y 坐标
*/
public static int decodeY(int code) {
return code >>> 16;
}
2.4 静态地图预处理
将墙壁、目标点等静态信息预处理为独立的数据结构，避免在每次状态比较时重复存储：
/**
* 关卡静态信息（所有状态共享）
*/
class Level {
int width, height;
boolean[][] walls; // 墙壁位置
boolean[][] goals; // 目标点位置
int goalCount; // 目标点数量
public Level(String[] map) {
height = map.length;
width = map[0].length();
walls = new boolean[height][width];
goals = new boolean[height][width];
for (int y = 0; y < height; y++) {
for (int x = 0; x < width; x++) {
char c = map[y].charAt(x);
walls[y][x] = (c == '#');
goals[y][x] = (c == '.' || c == '*' || c == '+');
if (goals[y][x]) goalCount++;
}
}
}
public boolean isWall(int x, int y) {
return x < 0 || x >= width || y < 0 || y >= height || walls[y][x];
}
public boolean isGoal(int x, int y) {
return x >= 0 && x < width && y >= 0 && y < height && goals[y][x];
}
}
三、BFS求解原理与Java实现
广度优先搜索（BFS）是求解推箱子最短路径问题的基础算法。由于推箱子状态空间巨大，单纯的 BFS 效率很低，需要配合死锁检测等剪枝手段。
3.1 BFS 算法原理
BFS 从初始状态出发，逐层扩展搜索：
1. 将初始状态加入队列
2. 每次从队列头部取出一个状态
3. 生成该状态所有可能的下一状态（四个方向移动）
4. 对新状态进行死锁检测，排除不可解状态
5. 将未访问过的合法状态加入队列尾部
6. 重复直到找到目标状态
3.2 完整Java实现
import java.util.*;
/**
* 推箱子BFS求解器
*/
public class SokobanBFS {
// 四个方向：上、下、左、右
private static final int[][] DIRS = {{0, -1}, {0, 1}, {-1, 0}, {1, 0}};
private Level level;
private Set<SokobanState> visited;
private Map<SokobanState, SokobanState> parent;
private Map<SokobanState, Integer> steps;
public SokobanBFS(Level level) {
this.level = level;
this.visited = new HashSet<>();
this.parent = new HashMap<>();
this.steps = new HashMap<>();
}
/**
* BFS求解
* @param initialState 初始状态
* @return 最少步数，无解返回-1
*/
public int solve(SokobanState initialState) {
Queue<SokobanState> queue = new LinkedList<>();
queue.offer(initialState);
visited.add(initialState);
steps.put(initialState, 0);
parent.put(initialState, null);
int statesExplored = 0;
while (!queue.isEmpty()) {
SokobanState current = queue.poll();
statesExplored++;
// 检查是否到达目标状态
if (isGoal(current)) {
System.out.println("找到解！步数：" + steps.get(current));
System.out.println("探索状态数：" + statesExplored);
printSolution(current);
return steps.get(current);
}
// 生成所有可能的下一状态
List<SokobanState> nextStates = generateNextStates(current);
for (SokobanState next : nextStates) {
if (!visited.contains(next)) {
// 死锁检测：如果是死锁状态则跳过
if (isDeadlock(next)) {
continue;
}
visited.add(next);
steps.put(next, steps.get(current) + 1);
parent.put(next, current);
queue.offer(next);
}
}
}
System.out.println("无解！探索状态数：" + statesExplored);
return -1;
}
/**
* 检查是否为目标状态：所有箱子都在目标点上
*/
private boolean isGoal(SokobanState state) {
for (int boxPos : state.boxPositions) {
int bx = decodeX(boxPos);
int by = decodeY(boxPos);
if (!level.isGoal(bx, by)) {
return false;
}
}
return true;
}
/**
* 生成当前状态的所有合法下一状态
*/
private List<SokobanState> generateNextStates(SokobanState state) {
List<SokobanState> nextStates = new ArrayList<>();
int px = state.playerX;
int py = state.playerY;
// 将箱子位置数组转为Set便于查找
Set<Integer> boxSet = new HashSet<>();
for (int pos : state.boxPositions) {
boxSet.add(pos);
}
for (int[] dir : DIRS) {
int dx = dir[0];
int dy = dir[1];
int newPx = px + dx;
int newPy = py + dy;
// 检查新位置是否是墙
if (level.isWall(newPx, newPy)) {
continue;
}
int newPlayerPos = encodePos(newPx, newPy);
// 检查新位置是否有箱子
if (boxSet.contains(newPlayerPos)) {
// 尝试推箱子：检查箱子前方是否为空
int newBx = newPx + dx;
int newBy = newPy + dy;
if (level.isWall(newBx, newBy)) {
continue; // 箱子前方是墙，不能推
}
int newBoxPos = encodePos(newBx, newBy);
if (boxSet.contains(newBoxPos)) {
continue; // 箱子前方是另一个箱子，不能推
}
// 推动箱子：创建新状态
int[] newBoxPositions = state.boxPositions.clone();
for (int i = 0; i < newBoxPositions.length; i++) {
if (newBoxPositions[i] == newPlayerPos) {
newBoxPositions[i] = newBoxPos;
break;
}
}
SokobanState nextState = new SokobanState(newPx, newPy, newBoxPositions);
nextStates.add(nextState);
} else {
// 工人单纯移动
SokobanState nextState = new SokobanState(newPx, newPy, state.boxPositions);
nextStates.add(nextState);
}
}
return nextStates;
}
/**
* 死锁检测（简化版，详见下一节）
*/
private boolean isDeadlock(SokobanState state) {
// 简单死锁检测：检查是否有箱子在角落且不是目标点
for (int boxPos : state.boxPositions) {
int bx = decodeX(boxPos);
int by = decodeY(boxPos);
if (level.isGoal(bx, by)) {
continue; // 在目标点上，不是死锁
}
// 检查是否在角落（两面都是墙）
boolean upWall = level.isWall(bx, by - 1);
boolean downWall = level.isWall(bx, by + 1);
boolean leftWall = level.isWall(bx - 1, by);
boolean rightWall = level.isWall(bx + 1, by);
// 左上角死锁
if (upWall && leftWall) return true;
// 右上角死锁
if (upWall && rightWall) return true;
// 左下角死锁
if (downWall && leftWall) return true;
// 右下角死锁
if (downWall && rightWall) return true;
}
return false;
}
// ... encodePos/decodeX/decodeY 方法同上
/**
* 打印解决方案路径
*/
private void printSolution(SokobanState goalState) {
List<SokobanState> path = new ArrayList<>();
SokobanState current = goalState;
while (current != null) {
path.add(current);
current = parent.get(current);
}
Collections.reverse(path);
System.out.println("共 " + (path.size() - 1) + " 步：");
for (int i = 0; i < path.size(); i++) {
System.out.println("--- 第 " + i + " 步 ---");
printState(path.get(i));
}
}
private void printState(SokobanState state) {
char[][] map = new char[level.height][level.width];
// 初始化墙壁和地板
for (int y = 0; y < level.height; y++) {
for (int x = 0; x < level.width; x++) {
if (level.walls[y][x]) {
map[y][x] = '#';
} else if (level.goals[y][x]) {
map[y][x] = '.';
} else {
map[y][x] = ' ';
}
}
}
// 放置箱子
for (int boxPos : state.boxPositions) {
int bx = decodeX(boxPos);
int by = decodeY(boxPos);
map[by][bx] = (level.goals[by][bx]) ? '*' : '$';
}
// 放置工人
int px = state.playerX;
int py = state.playerY;
map[py][px] = (level.goals[py][px]) ? '+' : '@';
// 打印
for (int y = 0; y < level.height; y++) {
System.out.println(new String(map[y]));
}
}
}
四、死锁检测算法
死锁检测是推箱子求解器中最重要的优化手段。所谓死锁，是指虽然当前状态合法，但已经不可能通过任何操作到达目标状态的情况。及时检测并剪枝死锁状态，可以大幅减少搜索空间。
4.1 简单死锁（角落死锁）
最简单的死锁：箱子被推到了墙角，且该墙角不是目标点。由于箱子只能推不能拉，一旦进入角落就再也无法移动。
##### ##### ##### #####
#$.. #..$ #..# #..#
#..# #..# #$.. #..$
##### ##### ##### #####
左上死锁 右上死锁 左下死锁 右下死锁
检测方法：检查每个不在目标点上的箱子，判断其水平和垂直方向是否各有至少一面墙。
/**
* 简单死锁检测：角落死锁
* @return true 表示是死锁状态
*/
private boolean checkCornerDeadlock(int bx, int by) {
if (level.isGoal(bx, by)) return false;
boolean upWall = level.isWall(bx, by - 1);
boolean downWall = level.isWall(bx, by + 1);
boolean leftWall = level.isWall(bx - 1, by);
boolean rightWall = level.isWall(bx + 1, by);
// 四个角落中的任意一个
return (upWall && leftWall) || (upWall && rightWall)
|| (downWall && leftWall) || (downWall && rightWall);
}
4.2 冻结死锁（Freeze Deadlock）
冻结死锁比角落死锁更复杂：一个箱子虽然不在角落，但由于被其他箱子和墙壁共同阻挡，已经无法再移动。
########
# $. #
# $ #
########
上图中，上面的箱子被左边的墙和下面的箱子挡住，下面的箱子被左边的墙和上面的箱子挡住——两个箱子都无法移动，形成冻结死锁。
检测方法：从一个不在目标点的箱子出发，递归检查其相邻的箱子和墙壁，判断是否形成了无法移动的封闭结构。
/**
* 冻结死锁检测
* 检查某个箱子是否被"冻结"（无法向任何方向移动）
*/
private boolean checkFreezeDeadlock(SokobanState state, int boxIndex,
Set<Integer> frozenBoxes) {
int boxPos = state.boxPositions[boxIndex];
int bx = decodeX(boxPos);
int by = decodeY(boxPos);
if (level.isGoal(bx, by)) {
return false; // 在目标点上的箱子不参与冻结死锁判断
}
if (frozenBoxes.contains(boxPos)) {
return true; // 已经判定为冻结
}
// 检查水平方向是否可推
boolean canPushHorizontal = false;
// 检查向左推
if (!level.isWall(bx - 1, by) && !hasBoxAt(state, bx - 1, by)) {
// 左边是空的，检查右边是否有空间让工人进入推箱子
if (!level.isWall(bx + 1, by) && !hasBoxAt(state, bx + 1, by)) {
canPushHorizontal = true;
}
}
// 检查向右推
if (!level.isWall(bx + 1, by) && !hasBoxAt(state, bx + 1, by)) {
if (!level.isWall(bx - 1, by) && !hasBoxAt(state, bx - 1, by)) {
canPushHorizontal = true;
}
}
// 检查垂直方向是否可推
boolean canPushVertical = false;
// 检查向上推
if (!level.isWall(bx, by - 1) && !hasBoxAt(state, bx, by - 1)) {
if (!level.isWall(bx, by + 1) && !hasBoxAt(state, bx, by + 1)) {
canPushVertical = true;
}
}
// 检查向下推
if (!level.isWall(bx, by + 1) && !hasBoxAt(state, bx, by + 1)) {
if (!level.isWall(bx, by - 1) && !hasBoxAt(state, bx, by - 1)) {
canPushVertical = true;
}
}
// 如果两个方向都不能推，则是冻结死锁
if (!canPushHorizontal && !canPushVertical) {
frozenBoxes.add(boxPos);
return true;
}
return false;
}
/**
* 检查指定位置是否有箱子
*/
private boolean hasBoxAt(SokobanState state, int x, int y) {
int pos = encodePos(x, y);
for (int boxPos : state.boxPositions) {
if (boxPos == pos) return true;
}
return false;
}
4.3 模式死锁（Pattern Deadlock）
模式死锁是更复杂的死锁形式，指箱子被推到了某些特定的位置模式中，虽然单个箱子都可以移动，但整体上已经无法将所有箱子都推到目标点。
常见的模式死锁包括：
1. 墙壁死锁：箱子沿着墙壁排成一列，且墙壁一侧没有目标点
######### #########
#$ $ $.# #. $ $# ← 错误示范
######### #########
2. 瓶颈死锁：两个箱子堵住了唯一通道，导致无法绕到另一侧
#####
# $ #
# $ #
# #
#####
模式死锁的检测通常需要预计算死锁位置表（Deadlock Square Table）：通过从目标点反向搜索，找出所有”不可能将箱子推到任何目标点”的位置。
/**
* 预计算死锁位置表（反向搜索法）
* 从所有目标点出发，反向模拟箱子的移动，标记所有可达位置
* 不可达的位置就是死锁位置
*/
public boolean[][] computeDeadlockTable(Level level) {
int w = level.width;
int h = level.height;
boolean[][] reachable = new boolean[h][w];
Queue<int[]> queue = new LinkedList<>();
// 从所有目标点开始反向搜索
for (int y = 0; y < h; y++) {
for (int x = 0; x < w; x++) {
if (level.isGoal(x, y)) {
reachable[y][x] = true;
queue.offer(new int[]{x, y});
}
}
}
// 反向BFS：箱子从目标点"拉"回来
while (!queue.isEmpty()) {
int[] pos = queue.poll();
int bx = pos[0];
int by = pos[1];
for (int[] dir : DIRS) {
int dx = dir[0];
int dy = dir[1];
// 反向：箱子从(bx+dx, by+dy)被推到(bx, by)
// 工人需要在(bx-dx, by-dy)的位置推
int prevBx = bx + dx;
int prevBy = by + dy;
int playerX = bx - dx;
int playerY = by - dy;
// 检查箱子之前的位置和工人位置是否都不是墙
if (!level.isWall(prevBx, prevBy) && !level.isWall(playerX, playerY)) {
if (!reachable[prevBy][prevBx]) {
reachable[prevBy][prevBx] = true;
queue.offer(new int[]{prevBx, prevBy});
}
}
}
}
// 死锁位置 = 不是墙 且 不可达
boolean[][] deadlock = new boolean[h][w];
for (int y = 0; y < h; y++) {
for (int x = 0; x < w; x++) {
if (!level.isWall(x, y) && !reachable[y][x]) {
deadlock[y][x] = true;
}
}
}
return deadlock;
}
4.4 综合死锁检测
将以上几种死锁检测组合起来，形成完整的死锁判断：
/**
* 综合死锁检测
*/
private boolean isDeadlock(SokobanState state) {
// 1. 简单死锁检测 + 死锁位置表检测
for (int boxPos : state.boxPositions) {
int bx = decodeX(boxPos);
int by = decodeY(boxPos);
if (level.isGoal(bx, by)) continue;
// 死锁位置表检测（预计算）
if (deadlockTable[by][bx]) {
return true;
}
}
// 2. 冻结死锁检测
Set<Integer> frozenBoxes = new HashSet<>();
for (int i = 0; i < state.boxPositions.length; i++) {
if (checkFreezeDeadlock(state, i, frozenBoxes)) {
return true;
}
}
return false;
}
五、复杂度分析与优化策略
5.1 时间复杂度分析
| 算法 | 时间复杂度 | 说明 |
|---|---|---|
| 朴素 BFS | O(b^d) | b 为分支因子（约 2-4），d 为最优解深度 |
| BFS + 死锁检测 | 远小于 O(b^d) | 死锁剪枝可排除 50%-90% 的无效状态 |
| BFS + 死锁 + 可达性优化 | 更优 | 进一步减少状态空间 |
推箱子的分支因子（每个状态的合法后继状态数）通常在 2-4 之间，但由于死锁检测的存在，实际有效分支因子会更低。
5.2 空间复杂度分析
| 数据结构 | 空间复杂度 | 说明 |
|---|---|---|
| 已访问状态集合 | O(N) | N 为探索的状态数 |
| 队列 | O(b^d) | 最坏情况下与状态数同阶 |
| 死锁位置表 | O(W×H) | 与地图大小成正比，可忽略 |
5.3 优化策略
优化1：工人可达性优化
在推箱子中，工人的位置只有在推动箱子时才有意义。如果两个状态中箱子位置完全相同，且工人可以在不推动任何箱子的情况下从一个位置走到另一个位置，那么这两个状态是等价的。
/**
* 优化状态表示：只记录箱子位置 + 工人所在的可达区域
* 工人在同一连通区域内的不同位置视为同一状态
*/
这种优化可以将状态空间减少数倍，因为工人的许多位置都是等价的。
优化2：优先队列（A* 搜索）
与华容道类似，推箱子也可以使用 A* 算法加速搜索。常用的启发函数：
- 曼哈顿距离和：每个箱子到最近目标点的曼哈顿距离之和
- 最小权匹配：使用匈牙利算法计算箱子到目标点的最优匹配距离
/**
* 启发函数：每个箱子到最近目标点的曼哈顿距离之和
* 可采纳：每个箱子至少需要移动这么多步才能到达目标点
*/
private int heuristic(SokobanState state) {
int total = 0;
for (int boxPos : state.boxPositions) {
int bx = decodeX(boxPos);
int by = decodeY(boxPos);
if (level.isGoal(bx, by)) continue;
int minDist = Integer.MAX_VALUE;
// 找到最近的目标点
for (int gy = 0; gy < level.height; gy++) {
for (int gx = 0; gx < level.width; gx++) {
if (level.isGoal(gx, gy)) {
int dist = Math.abs(bx - gx) + Math.abs(by - gy);
minDist = Math.min(minDist, dist);
}
}
}
total += minDist;
}
return total;
}
优化3：IDA（迭代加深 A）
推箱子的状态空间很大，BFS 和 A 都可能因为内存不足而失败。IDA 使用深度优先搜索的方式，每次限制 f 值上限，空间复杂度仅为 O(d)。
优化4：双向搜索
从初始状态正向搜索，同时从目标状态反向搜索（箱子从目标点被”拉”回来），当两边相遇时得到解。
六、适用场景与扩展思路
6.1 适用场景
推箱子求解算法的思路可以推广到以下场景：
- 仓储物流：仓库中货物的搬运路径规划、货架排布优化
- 机器人路径规划：多机器人协同搬运物体的场景
- 游戏 AI：益智游戏的关卡设计与难度评估、自动解题功能
- 规划问题：许多 AI 规划问题（Planning）可以转化为状态空间搜索
- 组合优化：某些约束满足问题可以用搜索 + 剪枝的方法求解
6.2 扩展思路
1. 多箱子协作
当关卡中有多个箱子时，如何高效地规划推箱顺序？这涉及到子目标排序和任务分解：
思路：将问题分解为"将第i个箱子推到第j个目标点"的子问题
使用分治或动态规划的思想，逐步求解
2. 关卡生成器
利用求解器自动生成推箱子关卡：
- 随机生成关卡布局
- 使用求解器验证是否有解
- 根据求解难度（步数、搜索状态数）评估关卡难度
- 筛选出符合要求的关卡
3. 人机对战
将推箱子 AI 应用于游戏中：
- 提示功能：AI 给出下一步最优走法
- 对战模式：玩家与 AI 比赛谁先完成关卡
- 教学功能：AI 分析玩家的走法，给出改进建议
4. 三维推箱子
将推箱子扩展到三维空间，增加更多的策略性和复杂度。此时需要重新设计状态表示和死锁检测算法。
6.3 总结
推箱子虽然是一款经典小游戏，但其中蕴含的搜索算法、剪枝策略、状态空间优化等思想，是人工智能和算法设计领域的宝贵财富。
从简单的 BFS 到复杂的死锁检测，从盲目搜索到启发式搜索，推箱子求解器的优化过程完美展现了算法设计的核心思路：深入理解问题本质，找到有效的剪枝手段，用尽可能少的计算获得答案。
在实际工程中，我们经常会遇到类似的状态空间搜索问题。掌握这些经典算法，并能根据问题特点设计合适的剪枝策略和启发函数，是每个算法工程师的必备技能。
思考练习：如果推箱子游戏中增加了”可以拉箱子”的功能，算法需要做哪些修改？死锁检测还适用吗？
