游戏介绍
推箱子（Sokoban）是经典的逻辑益智游戏，玩家控制角色在仓库中推动箱子到指定目标位置。规则限制箱子只能推不能拉，且每次只能推动一个箱子。本文用Java实现推箱子的自动求解器。
核心算法
DFS回溯搜索
由于推箱子需要精确规划每一步，采用深度优先搜索（DFS）配合回溯策略。状态包括玩家位置和所有箱子位置。
死锁检测
推箱子最容易陷入死锁（箱子无法再移动），需要在搜索过程中实时检测：
1. 墙角死锁：箱子被推到墙角且该墙角不是目标点
2. 边缘死锁：箱子沿墙壁排列形成无法解开的阻挡
3. 简单死锁表：预处理所有非目标点的”死锁角落”
状态压缩
将玩家位置和箱子位置集合编码为字符串，使用HashSet去重。
Java实现
import java.util.*;
public class SokobanSolver {
// 地图符号
static final char WALL = '#';
static final char FLOOR = ' ';
static final char TARGET = '.';
static final char BOX = '$';
static final char PLAYER = '@';
static final char BOX_ON_TARGET = '*';
static final char PLAYER_ON_TARGET = '+';
// 示例关卡（XSB格式）
static String[] LEVEL = {
" ##### ",
"### # ",
"# $ # ",
"# . # ",
"###@### ",
" ### "
};
int rows, cols;
char[][] grid; // 原始地图（墙壁和目标点不变）
boolean[][] isTarget; // 标记目标点位置
boolean[][] deadLock; // 预处理的死锁位置
Set<String> visited;
List<String> solution;
// 方向
static final int[][] DIRS = {{0, -1}, {0, 1}, {-1, 0}, {1, 0}};
static final String[] DIR_NAMES = {"上", "下", "左", "右"};
public SokobanSolver() {
rows = LEVEL.length;
cols = LEVEL[0].length();
grid = new char[rows][cols];
isTarget = new boolean[rows][cols];
deadLock = new boolean[rows][cols];
for (int y = 0; y < rows; y++) {
String line = LEVEL[y];
for (int x = 0; x < cols; x++) {
char c = line.charAt(x);
grid[y][x] = (c == BOX || c == PLAYER || c == BOX_ON_TARGET || c == PLAYER_ON_TARGET)
? FLOOR : c;
if (c == TARGET || c == BOX_ON_TARGET || c == PLAYER_ON_TARGET) {
isTarget[y][x] = true;
}
}
}
precomputeDeadLocks();
}
// 预处理死锁位置：非目标点的凹角
void precomputeDeadLocks() {
for (int y = 0; y < rows; y++) {
for (int x = 0; x < cols; x++) {
if (grid[y][x] == WALL || isTarget[y][x]) continue;
// 检查四种类型的凹角（左上、右上、左下、右下）
if ((isWall(x - 1, y) && isWall(x, y - 1)) || // 左上
(isWall(x + 1, y) && isWall(x, y - 1)) || // 右上
(isWall(x - 1, y) && isWall(x, y + 1)) || // 左下
(isWall(x + 1, y) && isWall(x, y + 1))) { // 右下
deadLock[y][x] = true;
}
}
}
}
boolean isWall(int x, int y) {
return x < 0 || x >= cols || y < 0 || y >= rows || grid[y][x] == WALL;
}
// 解析初始状态
State parseInitialState() {
int px = 0, py = 0;
Set<String> boxes = new HashSet<>();
for (int y = 0; y < rows; y++) {
String line = LEVEL[y];
for (int x = 0; x < cols; x++) {
char c = line.charAt(x);
if (c == PLAYER || c == PLAYER_ON_TARGET) {
px = x; py = y;
}
if (c == BOX || c == BOX_ON_TARGET) {
boxes.add(x + "," + y);
}
}
}
return new State(px, py, boxes, new ArrayList<>());
}
// DFS求解
public List<String> solve() {
State init = parseInitialState();
visited = new HashSet<>();
solution = new ArrayList<>();
if (dfs(init)) {
return solution;
}
return null;
}
boolean dfs(State s) {
String key = s.key();
if (visited.contains(key)) return false;
visited.add(key);
// 检查是否全部到达目标
if (s.allOnTarget(isTarget)) {
solution = new ArrayList<>(s.moves);
return true;
}
// 尝试四个方向
for (int i = 0; i < DIRS.length; i++) {
int nx = s.px + DIRS[i][0];
int ny = s.py + DIRS[i][1];
if (isWall(nx, ny)) continue;
String nextPos = nx + "," + ny;
if (s.boxes.contains(nextPos)) {
// 前方是箱子，尝试推动
int bx = nx + DIRS[i][0];
int by = ny + DIRS[i][1];
if (isWall(bx, by) || s.boxes.contains(bx + "," + by)) continue;
if (deadLock[by][bx] && !isTarget[by][bx]) continue; // 死锁检测
Set<String> newBoxes = new HashSet<>(s.boxes);
newBoxes.remove(nextPos);
newBoxes.add(bx + "," + by);
List<String> newMoves = new ArrayList<>(s.moves);
newMoves.add(DIR_NAMES[i]);
State next = new State(nx, ny, newBoxes, newMoves);
if (dfs(next)) return true;
} else {
// 前方是空地，直接移动
List<String> newMoves = new ArrayList<>(s.moves);
newMoves.add(DIR_NAMES[i]);
State next = new State(nx, ny, s.boxes, newMoves);
if (dfs(next)) return true;
}
}
return false;
}
// 状态类
static class State {
int px, py;
Set<String> boxes;
List<String> moves;
State(int px, int py, Set<String> boxes, List<String> moves) {
this.px = px; this.py = py;
this.boxes = boxes;
this.moves = moves;
}
String key() {
return px + "," + py + "|" + String.join(";", new TreeSet<>(boxes));
}
boolean allOnTarget(boolean[][] targets) {
for (String b : boxes) {
String[] p = b.split(",");
int x = Integer.parseInt(p[0]), y = Integer.parseInt(p[1]);
if (!targets[y][x]) return false;
}
return true;
}
}
// 打印当前状态
void printState(State s) {
char[][] display = new char[rows][cols];
for (int y = 0; y < rows; y++) {
for (int x = 0; x < cols; x++) {
display[y][x] = grid[y][x];
}
}
// 标记目标点
for (int y = 0; y < rows; y++) {
for (int x = 0; x < cols; x++) {
if (isTarget[y][x] && display[y][x] == FLOOR) display[y][x] = TARGET;
}
}
// 放置箱子
for (String b : s.boxes) {
String[] p = b.split(",");
int x = Integer.parseInt(p[0]), y = Integer.parseInt(p[1]);
display[y][x] = isTarget[y][x] ? BOX_ON_TARGET : BOX;
}
// 放置玩家
display[s.py][s.px] = isTarget[s.py][s.px] ? PLAYER_ON_TARGET : PLAYER;
for (char[] row : display) {
System.out.println(new String(row));
}
System.out.println();
}
public static void main(String[] args) {
SokobanSolver solver = new SokobanSolver();
System.out.println("死锁位置:");
for (int y = 0; y < solver.rows; y++) {
for (int x = 0; x < solver.cols; x++) {
System.out.print(solver.deadLock[y][x] ? 'D' : ' ');
}
System.out.println();
}
long start = System.currentTimeMillis();
List<String> solution = solver.solve();
long end = System.currentTimeMillis();
if (solution != null) {
System.out.println("找到解！步数: " + solution.size());
System.out.println("解法: " + String.join(" -> ", solution));
System.out.println("耗时: " + (end - start) + "ms");
System.out.println("访问状态数: " + solver.visited.size());
} else {
System.out.println("无解");
}
}
}
复杂度分析
- DFS时间复杂度：最坏情况 $O(b^d)$，$b$为分支因子（最多4个方向），$d$为解深度
- 死锁检测优化：通过预处理死锁角落，可剪枝大量无效分支，实际复杂度显著降低
- 空间复杂度：$O(V)$，$V$为访问过的状态数，受HashSet存储限制
进阶优化
- BFS替代DFS：保证找到最短解
- 启发式评估：使用曼哈顿距离之和作为评估函数，优先搜索更优分支
- 模式死锁：检测更复杂的死锁模式（如两个箱子在墙边互相阻挡）
总结
本文通过DFS回溯实现了推箱子求解器，核心创新在于预处理的死锁检测机制。读者可以在此基础上加入更复杂的模式死锁检测和启发式搜索，挑战更困难的关卡。
