每日算法 — 使用java实现推箱子：逆向拉取搜索与宏观路径压缩

为什么正向搜索会爆炸

推箱子（Sokoban）规则只有一句话：小人可以推箱子，不能拉箱子，把所有箱子推到目标格即通关。看起来简单，可它是 PSPACE-hard 问题——因为状态空间随箱子数量指数增长，而且大量”看起来很近”的推动其实是死路。

正向搜索以”推”为单位建模时，分支因子约为 箱子数 × 4。一个 6 箱局面单层就有 24 个后继，10 层搜索就是 24^10 ≈ 6.3×10^13 个状态，即使每层剪掉一半也无济于事。

真正致命的是双向不对称性：正向推动很容易造成”箱子贴墙无法再推”的死锁，而这类死锁在搜索树中占比极高；反过来，把所有箱子放回目标格的”逆向拉取”过程中，拉取动作天然不会把箱子推进墙角——因为拉取要求箱子身后有两格空地。

所以本文采用逆向拉取搜索（reverse pull search）：从”箱子全在目标格”的通关局面出发，反向把箱子拉回初始位置，最后把解序列整体翻转，就得到正向的推动解。

三个核心建模点

1. 拉取动作的精确定义

设箱子在 B，方向 d（单位向量）。正向推动是”玩家在 B-d，把箱子推到 B“。把它反过来：箱子从 B 拉回 B-d，玩家退到 B-2d。

于是拉取合法性只需三个条件：

• B-d 必须是地板（玩家要站在这里）；
• B-2d 必须是地板且没有箱子（玩家要退到这里）；
• 玩家在当前局面下能走到 B-d。

第三条是最容易被写错的地方：玩家的可达性依赖当前箱子布局，不同玩家位置可能导致同一组箱子布局产生不同后继。标准解法是玩家位置归一化——把所有可达格中的”字典序最小坐标”作为规范位置（canonical player）。因为玩家在连通区域内可以自由走动，区域相同的两个状态是等价的。

/** 玩家可达区域 BFS：返回可达标记数组，并给出规范位置（最小坐标） */
static int[] reachable(char[][] grid, int[][] boxMask, int px, int py, int[] canonical) {
    int h = grid.length, w = grid[0].length;
    int[] vis = new int[h * w];                 // 0 未访问, 1 可达
    int[] queue = new int[h * w];
    int head = 0, tail = 0;
    queue[tail++] = py * w + px;
    vis[py * w + px] = 1;
    canonical[0] = py; canonical[1] = px;       // 初始化最小值
    while (head < tail) {
        int cur = queue[head++];
        int y = cur / w, x = cur % w;
        if (cur < canonical[0] * w + canonical[1]) {   // 字典序更小则更新规范位置
            canonical[0] = y; canonical[1] = x;
        }
        for (int k = 0; k < 4; k++) {
            int ny = y + DY[k], nx = x + DX[k];
            if (ny < 0 || nx < 0 || ny >= h || nx >= w) continue;
            if (grid[ny][nx] == WALL || boxMask[ny][nx] != 0) continue;
            int id = ny * w + nx;
            if (vis[id] == 1) continue;
            vis[id] = 1;
            queue[tail++] = id;
        }
    }
    return vis;
}

2. 状态压缩与 Zobrist 哈希

一个局面 = 箱子集合 + 玩家连通区域。用 long 位棋盘存箱子（宽高 ≤ 64 时一维 long 就够），再叠加玩家规范位置，用 Zobrist 增量异或得到 64 位指纹。

final class Zobrist {
    private final long[][] boxKey;   // [cell][boxIndex] 让同格不同箱号区分（可选）
    private final long[] playerKey;  // [cell] 玩家规范位置
    Zobrist(int cells, int maxBox, long seed) {
        SplittableRandom rnd = new SplittableRandom(seed);
        boxKey = new long[cells][maxBox];
        playerKey = new long[cells];
        for (int i = 0; i < cells; i++) {
            for (int j = 0; j < maxBox; j++) boxKey[i][j] = rnd.nextLong();
            playerKey[i] = rnd.nextLong();
        }
    }
    long boxHash(int cell, int boxIdx) { return boxKey[cell][boxIdx]; }
    long playerHash(int cell)         { return playerKey[cell]; }
}

3. 宏观路径压缩：一层搜索顶十层

如果每次只推一格，解的长度会膨胀好几倍。宏观移动（macro move） 的思路是：一次扩展直接把某个箱子推到”下一个有意义的位置”——撞墙前、拐角前、或者紧贴另一箱子前，中间的所有格位都是同一宏观动作的不同中间态，不必逐层入队。

/**
 * 从 (boxY, boxX) 沿方向 (dy, dx) 连续拉取，返回所有可行的宏观落点（不含原点）。
 * 遇到墙/箱子/已越过目标走廊即停止。
 */
static List<int[]> macroPulls(char[][] grid, int[][] boxMask, int boxY, int boxX, int dy, int dx) {
    List<int[]> out = new ArrayList<>();
    int y = boxY, x = boxX;
    while (true) {
        int ny = y - dy, nx = x - dx;              // 箱子下一格
        int py = y - 2 * dy, px2 = x - 2 * dx;     // 玩家退让格
        if (!floor(grid, ny, nx) || boxMask[ny][nx] != 0) break;
        if (!floor(grid, py, px2) || boxMask[py][px2] != 0) break;
        y = ny; x = nx;
        out.add(new int[]{y, x});
    }
    return out;
}

注意这里 ny/nx 与 py/px2 的检查顺序与单步拉取完全一致，只是把”拉一次”换成”拉到不能再拉”。这个优化对推箱子尤其有效，因为走廊型地图上单格推动几乎全是无效层。

完整项目结构

sokoban-reverse/
├── pom.xml
└── src/main/java/com/daily/algorithm/sokoban/
    ├── Board.java            // 地图解析、静态预处理、死格标记
    ├── Zobrist.java          // 64 位局面指纹
    ├── CanonicalState.java   // 归一化状态打包（箱子位 + 玩家区域）
    ├── ReversePullSolver.java// 逆向拉取 BFS/Dijkstra 主流程
    ├── MacroMoves.java       // 宏观拉取生成
    └── SolutionRenderer.java // 反解序列 → 正向推动 + 玩家步伐还原

主求解器

逆向搜索用 Dijkstra 而非纯 BFS，因为”宏观拉取”一次压缩了多个格位，步数不再等权；用推动次数（push count）作为边权更贴近”最短解”的真实含义。

public final class ReversePullSolver {
    private final Board board;
    private final Zobrist zob;
    private final Map<Long, Long> bestG = new HashMap<>();        // 指纹 → 最小推动数
    private final Map<Long, CanonicalState> parent = new HashMap<>();
    private final PriorityQueue<Entry> pq = new PriorityQueue<>(Comparator.comparingInt(e -> e.g));

    public ReversePullSolver(Board board) {
        this.board = board;
        this.zob = new Zobrist(board.cells(), board.boxCount() + 1, 0x5DEECE66DL);
    }

    /** 从通关局面（箱子全在目标）反向搜索到初始箱子布局 */
    public List<Integer> solve() {
        CanonicalState start = board.goalState();
        bestG.put(start.hash(), 0);
        pq.add(new Entry(start, 0));

        while (!pq.isEmpty()) {
            Entry e = pq.poll();
            if (e.g != bestG.getOrDefault(e.state.hash(), Integer.MAX_VALUE)) continue;
            if (board.isInitialBoxLayout(e.state)) return rebuild(e.state);

            for (long next : successors(e.state)) {
                int ng = e.g + 1;                       // 一次宏观拉取记 1 次推动
                CanonicalState ns = CanonicalState.decode(next);
                if (ng >= bestG.getOrDefault(ns.hash(), Integer.MAX_VALUE)) continue;
                bestG.put(ns.hash(), ng);
                parent.put(ns.hash(), e.state);
                pq.add(new Entry(ns, ng));
            }
        }
        return Collections.emptyList();                 // 不可解
    }

    /**
     * 生成所有后继：对每个箱子、每个方向，先做玩家可达性判定，
     * 再做宏观拉取的落点枚举；每个落点重新归一化玩家位置。
     */
    private List<Long> successors(CanonicalState s) {
        List<Long> res = new ArrayList<>(16);
        int[] canon = new int[2];
        int[] vis = ReversePullSolver.reachable(board.grid(), s.boxMask(), s.playerY(), s.playerX(), canon);

        for (int by = 0; by < board.height(); by++) {
            for (int bx = 0; bx < board.width(); bx++) {
                if (s.boxMask()[by][bx] == 0) continue;
                for (int k = 0; k < 4; k++) {
                    int sy = by - DY[k], sx = bx - DX[k];       // 玩家拉取时的站位
                    if (!board.floor(sy, sx) || s.boxMask()[sy][sx] != 0) continue;
                    if (vis[sy * board.width() + sx] != 1) continue; // 玩家到不了站位
                    for (int[] dst : MacroMoves.macroPulls(board.grid(), s.boxMask(), by, bx, DY[k], DX[k])) {
                        if (board.isDeadCell(dst[0], dst[1])) continue;  // 角落死格剪枝
                        CanonicalState ns = s.moveBoxAndPlayer(by, bx, dst[0], dst[1],
                                dst[0] - DY[k], dst[1] - DX[k], zob);
                        res.add(ns.hash());
                    }
                }
            }
        }
        return res;
    }
}

isDeadCell 是静态预处理：对每个非目标格，若它同时贴着一面横墙和一面竖墙（墙角），箱子推进去就再也拉不出来，可以直接剪掉。这条规则挡掉了绝大多数无谓分支。

反解序列还原为正向操作

逆向搜索得到的是”从终点到起点”的拉取序列，需要整体翻转，并把每个宏观拉取拆成若干次单格推动，再插入玩家行走步骤：

public final class SolutionRenderer {
    /** 把逆向宏观序列翻转为正向推动序列 */
    public static List<int[]> toForwardPushes(List<MacroStep> reversePath) {
        List<int[]> pushes = new ArrayList<>();
        for (int i = reversePath.size() - 1; i >= 0; i--) {
            MacroStep st = reversePath.get(i);
            // 逆向：箱子 B → B-d；正向：箱子 B-d → B，方向取反
            int dy = -st.dy, dx = -st.dx;
            int steps = st.steps;                       // 宏观压缩了几格
            for (int t = 0; t < steps; t++) {
                pushes.add(new int[]{st.toY - dy * t, st.toX - dx * t, dy, dx});
            }
        }
        return pushes;
    }

    /** 玩家两段推动之间的行走路径：BFS 最短路，避免绕路卡死 */
    public static List<int[]> walk(char[][] grid, int[][] boxes, int fromY, int fromX, int toY, int toX) { /* BFS 略 */ }
}

复杂度分析

设箱子数 k、可行格子数 N、宏观拉取平均长度 L。

• 单次后继生成：O(k·4·N)，其中 N 来自玩家可达性 BFS；
• 状态总数上界 O(C(N,k))，实际因归一化与死格剪枝能压到 10^5~10^6 量级（本实现跑经典关卡 Microban 系列约 200 万状态内可解）；
• 空间：每个状态存 long 指纹 + int 位棋盘（宽高 ≤ 64 时两个 long），约 24 字节/状态。

宏观压缩带来的是常数级而非多项式级提升，但对走廊密集的推箱子地图，实测能让扩展节点数下降 5~10 倍。

运行示例

public class Main {
    public static void main(String[] args) throws Exception {
        String level = String.join("\n",
                "##########",
                "#   .    #",
                "#  $@$   #",
                "#   .    #",
                "##########");
        Board board = Board.parse(level);
        ReversePullSolver solver = new ReversePullSolver(board);
        List<Integer> path = solver.solve();
        System.out.println("推动次数 = " + (path.size() - 1));
        System.out.println(SolutionRenderer.render(board, path));
    }
}

字符含义：# 墙、 地板、. 目标、$ 箱子、@ 玩家、* 箱在目标、+ 人在目标。

小结

推箱子的难点不在规则，而在搜索方向的选择。逆向拉取利用”拉取自带空地约束”这一物理特性，天然规避了正向推动最容易产生的墙角死锁；再加上玩家位置归一化（消除同区域冗余）与宏观拉取（压缩走廊中间态），一个朴素 BFS 也能在秒级内解出多箱关卡。这套”反向建模 + 状态归一化 + 动作压缩”的组合，可以直接迁移到仓库调度、滑块拼图、机器人搬运等路径规划问题。