每日算法 — 使用java实现停车场逃脱：位棋盘状态编码与A*最优步数搜索

停车场逃脱（Rush Hour）的规则极其简单：6×6 的停车场里塞满横竖摆放的车辆，只有出口那一行是空的。你要做的是反复滑动车辆，把红色主角车挪到出口。规则一分钟学会，但第 40 关能让成年人卡上半小时。

它本质上是滑块谜题（sliding block puzzle）的一个经典实例，而求解它需要三件事：高效的状态编码、不会爆内存的去重、以及 admissible 的启发式函数。这篇文章用 Java 从零实现一个能秒解全部关卡的求解器。

一、状态定义与位棋盘编码

6×6 棋盘共 36 格，每格只需表示”被哪辆车占用”。最直观的表示是 byte[36]，但那样一次搜索要拷贝 36 字节，去重时哈希代价高。

更优雅的做法是按行位压缩：每一行用 6 位表示占用情况，整个棋盘压成一个 long 的 36 位。车辆位置另外编码。但滑动谜题的车辆是有身份的（同形状的车不能互换），所以状态必须记录”每辆车在哪一列/行”。

实践中采用”紧凑车辆数组编码”：每辆车记录 (朝向, 行或列, 起始格)，一辆车占用 1 字节即可（6×6 下位置信息 < 64），10 辆车 = 10 字节，直接可以 pack 进两个 long。

public final class Car {
    public final int id;
    public final boolean horizontal;  // true=横车，false=竖车
    public final int length;          // 2 或 3
    public final boolean hero;        // 是否主角车（红色，需到达出口）
    public int row, col;              // 当前左上角坐标

    public Car(int id, boolean horizontal, int length, boolean hero,
               int row, int col) {
        this.id = id; this.horizontal = horizontal; this.length = length;
        this.hero = hero; this.row = row; this.col = col;
    }

    public Car move(int delta) {
        return horizontal
                ? new Car(id, horizontal, length, hero, row, col + delta)
                : new Car(id, horizontal, length, hero, row + delta, col);
    }

    /** 该车占用的所有格子索引（0..35） */
    public int[] cells() {
        int[] out = new int[length];
        for (int i = 0; i < length; i++) {
            out[i] = horizontal ? row * 6 + col + i : (row + i) * 6 + col;
        }
        return out;
    }
}

public final class Board {
    public static final int SIZE = 6;
    public final Car[] cars;
    public final long occupancy;   // 36 位占用掩码，用于 O(1) 碰撞检测

    public Board(Car[] cars) {
        this.cars = cars;
        long mask = 0L;
        for (Car c : cars) for (int cell : c.cells()) mask |= (1L << cell);
        this.occupancy = mask;
    }
}

有了 occupancy 掩码，判断”某车能否移动一步”就变成一次位与运算，比遍历数组快一个量级：

    /** 判断某车向 delta 方向移动 1 步是否合法 */
    public boolean canMove(Car car, int delta) {
        if (delta == 0) return false;
        int newRow = car.horizontal ? car.row : car.row + delta;
        int newCol = car.horizontal ? car.col + delta : car.col;

        // 越界判定
        if (car.horizontal) {
            if (newCol < 0 || newCol + car.length > SIZE) return false;
        } else {
            if (newRow < 0 || newRow + car.length > SIZE) return false;
        }
        // 新占用的格子
        int[] cells = new int[car.length];
        for (int i = 0; i < car.length; i++) {
            cells[i] = car.horizontal ? newRow * SIZE + newCol + i
                                      : (newRow + i) * SIZE + newCol;
        }
        // 把自身原占格从掩码中剔除后再判断，避免"撞到自己"
        long others = occupancy;
        for (int cell : car.cells()) others &= ~(1L << cell);
        for (int cell : cells) if ((others & (1L << cell)) != 0L) return false;
        return true;
    }

二、核心搜索：A* 与阻塞启发式

Rush Hour 的搜索空间在 6×6 布局下约 10⁵ 量级，用 BFS 也能出解，但 A* 配合好的启发式可以把访问节点数压到几千。

启发式 h1（最小移动距离）：主角车到出口还差多少步。若主角车在第 col 列、横车长度为 len，出口在 col=5 一侧，则至少需要 5 - (col + len - 1) 步。

启发式 h2（阻塞车辆数）：主角车到出口的路径上有几辆不同的车挡道。每挡一辆车，至少要把它挪开一次（1 步），也可能更多，但这个下界是 admissible 的。

两者相加仍是 admissible（下界可加），但通常取 max(h1, h2) 更紧。

public final class Heuristic {
    /** 主角车到出口的最少滑动步数（不考虑阻挡） */
    public static int distanceToExit(Board b) {
        for (Car c : b.cars) {
            if (!c.hero) continue;
            if (c.horizontal) {
                int rightmost = c.col + c.length - 1;
                return Board.SIZE - 1 - rightmost;   // 出口在右侧
            } else {
                int bottom = c.row + c.length - 1;
                return Board.SIZE - 1 - bottom;      // 出口在下方
            }
        }
        return 0;
    }

    /** 主角车前方路径上挡路的不同车辆数 */
    public static int blockingCars(Board b) {
        for (Car hero : b.cars) {
            if (!hero.hero) continue;
            java.util.Set<Integer> blockers = new java.util.HashSet<>();
            if (hero.horizontal) {
                for (int r = 0; r < Board.SIZE; r++) {
                    for (int c = hero.col + hero.length; c < Board.SIZE; c++) {
                        int id = carAt(b, r, c);
                        if (id >= 0) blockers.add(id);
                    }
                }
            } else {
                for (int r = hero.row + hero.length; r < Board.SIZE; r++) {
                    for (int c = 0; c < Board.SIZE; c++) {
                        int id = carAt(b, r, c);
                        if (id >= 0) blockers.add(id);
                    }
                }
            }
            return blockers.size();
        }
        return 0;
    }

    private static int carAt(Board b, int r, int c) {
        for (Car car : b.cars) {
            for (int cell : car.cells()) if (cell == r * 6 + c) return car.id;
        }
        return -1;
    }

    public static int estimate(Board b) {
        return Math.max(distanceToExit(b), blockingCars(b));
    }
}

注意 carAt 是 O(车辆数 × 长度) 的朴素查表。生产实现应预建一个 int[36] 的格子到车号映射，每次构造棋盘时同步维护，可把启发式计算从 O(V·L) 降到 O(V)。

三、状态哈希：去重的成本决定搜索的生死

A* 的性能瓶颈从来不是堆操作，而是”这个状态我见过没有”。Board 对象不能直接做 key，必须序列化成稳定的字符串或长整数。

最省事的方案是把每辆车的 (row, col) 编码进一个 long：

public final class BoardKey {
    /** 每辆车用 6 位编码行列（0..35），最多 10 辆车 => 60 位 */
    public static long encode(Board b) {
        long key = 0L;
        int shift = 0;
        for (Car c : b.cars) {
            int pos = c.row * Board.SIZE + c.col;   // 0..35
            key |= ((long) pos) << shift;
            shift += 6;
            if (shift >= 60) break;   // 超出 long 的容量时需换方案
        }
        return key;
    }
}

车辆数超过 10 时 6 位 × N 会溢出，此时改用 String 或多个 long 拼接：

    /** 通用方案：按车辆顺序拼字符串，语义清晰、可直接作为 HashMap key */
    public static String canonical(Board b) {
        StringBuilder sb = new StringBuilder(b.cars.length * 3);
        for (Car c : b.cars) {
            sb.append((char) ('A' + c.row)).append((char) ('a' + c.col));
        }
        return sb.toString();
    }

关键洞察：车辆的 id 顺序天然固定，所以不需要像八数码那样考虑排列等价，直接按序编码即可去重。

四、A* 主循环

public final class RushHourSolver {

    public static final class Node implements Comparable<Node> {
        final Board board;
        final int g;          // 已走步数
        final int h;          // 启发值
        final Node parent;
        final String moveDesc; // 到达本节点的动作，用于回溯路径

        Node(Board b, int g, Node parent, String moveDesc) {
            this.board = b; this.g = g; this.parent = parent;
            this.moveDesc = moveDesc;
            this.h = Heuristic.estimate(b);
        }
        int f() { return g + h; }
        @Override public int compareTo(Node o) { return Integer.compare(f(), o.f()); }
    }

    public static java.util.List<String> solve(Board start) {
        java.util.PriorityQueue<Node> open = new java.util.PriorityQueue<>();
        java.util.Map<Long, Integer> bestG = new java.util.HashMap<>();
        java.util.Set<Long> closed = new java.util.HashSet<>();

        open.add(new Node(start, 0, null, "初始状态"));
        bestG.put(BoardKey.encode(start), 0);

        while (!open.isEmpty()) {
            Node cur = open.poll();
            long key = BoardKey.encode(cur.board);
            if (closed.contains(key)) continue;
            closed.add(key);

            // 目标检测：主角车抵达出口
            if (isSolved(cur.board)) return buildPath(cur);

            for (Car car : cur.board.cars) {
                for (int delta : new int[]{-1, 1}) {
                    if (!cur.board.canMove(car, delta)) continue;

                    Car[] next = cloneWithMove(cur.board.cars, car, delta);
                    Board nb = new Board(next);
                    long nk = BoardKey.encode(nb);
                    int ng = cur.g + 1;

                    Integer prevG = bestG.get(nk);
                    if (prevG != null && prevG <= ng) continue;   // 已有更优路径
                    bestG.put(nk, ng);

                    String desc = String.format("车%d 向%s移动 1 格",
                            car.id, delta > 0 ? "右/下" : "左/上");
                    open.add(new Node(nb, ng, cur, desc));
                }
            }
        }
        return java.util.Collections.emptyList();   // 无解
    }

    private static boolean isSolved(Board b) {
        for (Car c : b.cars) {
            if (!c.hero) continue;
            return c.horizontal && c.col + c.length == Board.SIZE;
        }
        return false;
    }

    private static Car[] cloneWithMove(Car[] cars, Car target, int delta) {
        Car[] out = new Car[cars.length];
        for (int i = 0; i < cars.length; i++) {
            out[i] = cars[i].id == target.id ? cars[i].move(delta) : cars[i];
        }
        return out;
    }

    private static java.util.List<String> buildPath(Node n) {
        java.util.LinkedList<String> path = new java.util.LinkedList<>();
        for (Node p = n; p != null; p = p.parent) path.addFirst(p.moveDesc);
        return path;
    }
}

bestG 与 closed 的双重结构是必要的：closed 防止重复展开（同一状态展开两次等于浪费），bestG 允许”找到更短路径时重新入堆”。这是 A* 在图搜索（而非树搜索）下的正确写法——很多实现只留一个 closed 集合，一旦把某状态标记为已访问，就再也不能用更优路径更新它，结果是解存在但不最优。

五、为什么启发式必须 admissible

A* 能保证最优解的前提是 h(n) ≤ h*(n)（真实剩余代价）。我们用的两个启发式都满足：

• distanceToExit：主角车每走一步最多前进 1 格，所以”还差的格数”是绝对下界，无法更少。
• blockingCars：每辆挡路的车至少要移动 1 次才能让路，所以”挡路车辆数”也是下界。

两者取 max 而非相加，是因为它们描述的是同一批动作的不同侧面，相加会高估（某辆车挪开既减少了距离也减少了一个 blocker，重复计数）。这是”A* 启发式设计中最常见的错误”：把两个相关下界相加，导致不 admissible，最终解不最优。

如果想更激进，可以用”阻塞链长度”启发式：主角车路径上的车，如果自己也挡住了别的车，形成依赖链，则链长是更紧的下界。代价是每次估值要多做一次 DFS，属于典型的”算得更准 vs 算得更多”权衡。

六、性能实测与工程细节

几个让实现真正可用的细节：

1. 状态不可变。Board 用 final 字段 + 每次移动构造新实例，避免回溯时”撤销移动”的隐性 bug。用可变数组做原地修改 + 手动回滚，在 Rush Hour 这种小状态空间里几乎没有性能收益，却极易写错。
2. canMove 只在必要时构造新格数组。可以先算目标格区间，用掩码判断，避免每步分配 int[3]。
3. ID 稳定：主角车的 id 固定为 0，其他车按读取顺序编号。这样 BoardKey.encode 才有稳定语义，否则同一布局会因车辆顺序变化而产生多个 key，去重失效。
4. 迭代加深作为兜底：若 A 内存吃紧（移动端场景），改用 IDA，用”当前路径上的最小 f 值”作为下一轮阈值，空间降到 O(depth)。

停车场逃脱之所以让人上瘾，是因为它把”局部可动性”和”全局目标”强行拆开：每辆车单独都能动，但大部分移动对通关无益。A* 恰好是这类问题的最优工具——启发式负责把注意力集中到”能减少阻塞的移动”，位棋盘负责让每次状态转移近乎免费。写完之后你会发现，人类卡半天的第 40 关，机器只需要展开几千个节点。