每日算法 — 使用java实现Q伯特：立方坐标跳格与启发式状态搜索

Q伯特（Qbert）的规则极简：在一个由立方体堆成的金字塔上不断跳跃，每落一格就翻转该格颜色，把全部格子翻成目标色即过关。但”每格翻转”意味着走回头路会把已翻好的格子再翻回去，于是最短通关路径变成了一个状态空间搜索问题。本文用 Java 实现这套内核：用立方坐标（cube coordinates）让四个跳向变成整数加法、把颜色状态压缩成一个位向量、用 A 加可采纳启发式求最短通关步数，并分析 2²⁸ 状态空间为什么能被削减到可搜索规模。

一、立方坐标：为什么六边形/等距格必须用三元组

Q伯特的金字塔在屏幕上呈现为等距（isometric）投影，每个立方体有四个可跳方向：左上、右上、左下、右下。如果用二维网格坐标 (row, col) 表示，这四个方向会变成：

// 二维写法：每个方向都依赖当前行的长度
{ -1, 0 }, { -1, +1 }, { +1, 0 }, { +1, -1 }   // 且需要额外判断行边界

问题在于：等距投影下，行长度不等（金字塔每层宽度递减），所以每次移动都要查”当前行的左边界”，边界判定散落在各处。

立方坐标（cube coordinates） 解决的正是这件事。用三个整数 (x, y, z) 且恒满足 x + y + z = 0，四个跳向就变成固定的坐标置换：

public record Cube(int x, int y, int z) {
    public Cube {
        assert x + y + z == 0 : "立方坐标必须满足 x+y+z=0";
    }

    /** 四个跳向：坐标三元组的循环置换 */
    static final Cube UP_LEFT    = new Cube(-1, +1,  0);   // x-1, y+1
    static final Cube UP_RIGHT   = new Cube( 0, +1, -1);   // y+1, z-1
    static final Cube DOWN_LEFT  = new Cube(-1,  0, +1);   // x-1, z+1
    static final Cube DOWN_RIGHT = new Cube( 0, -1, +1);   // y-1, z+1

    Cube move(Cube dir) {
        return new Cube(x + dir.x(), y + dir.y(), z + dir.z());
    }
}

为什么这组四个方向是对的。 在立方坐标里，y 对应屏幕竖直方向（越大越高），x 与 z 对应两条斜轴。左上跳 = y+1 且 x-1（向左上）；右上跳 = y+1 且 z-1；向下两个方向分别是它们的逆。每个方向都保持 x+y+z=0，因为 (-1)+(+1)+0 = 0 恒成立。这个性质让不需要任何边界检查就能保证坐标合法——非法坐标根本构造不出来（assert 会拦住）。

剩余的唯一约束是金字塔形状本身：某层的格子数有限。

二、金字塔的形状建模

Q伯特的金字塔共 28 格（原版 7 层：1+2+…+7）。用一个判定函数表达”该坐标是否属于金字塔”：

static final int ROWS = 7;

/** 立方坐标是否落在金字塔内：y 决定行，x 的绝对值决定该行偏移 */
static boolean inPyramid(Cube c) {
    int row = ROWS - 1 - c.y();        // y 越大越靠上，行号越小
    if (row < 0 || row >= ROWS) return false;
    int width = ROWS - row;            // 最上行 7 格，最下行 1 格
    // 该行内 x 的取值范围
    return c.x() >= -row && c.x() <= -row + width - 1;
}

这行代码是整个几何模型的核心。用 row 与 x 的偏移表达”梯形”边界，比维护 7 个不同的行数组更紧凑，也让 inPyramid 变成 O(1)。

为什么要用 -row 作为下界。 因为每个向上的跳向都会让 x 减 1（UP_LEFT 与 DOWN_LEFT），所以越往上 x 越负。因此第 row 行（从上往下数）的 x 起点是 -row。这个不变量把”形状”和”坐标变换”统一到了同一个代数系统里。

用这套模型，28 个格子可以一次性枚举出来：

static List<Cube> allTiles() {
    List<Cube> tiles = new ArrayList<>(28);
    for (int x = -6; x <= 0; x++) {
        for (int y = 0; y <= 6; y++) {
            int z = -x - y;
            Cube c = new Cube(x, y, z);
            if (inPyramid(c)) tiles.add(c);
        }
    }
    return tiles;   // 恰好 28 个
}

三、颜色状态压缩：28 位位向量

每格的颜色只有两种（已翻 / 未翻），所以整盘状态是一个 28 位的位掩码，塞进一个 int 绰绰有余。

public final class Pyramid {
    private final int[] tileIndex = new int[64];   // 稀疏映射（实际用 HashMap 更省）
    private final Map<Cube, Integer> idxMap = new HashMap<>(64);
    private int colorMask = 0;                     // bit i = 1 表示第 i 格已翻

    Pyramid() {
        int i = 0;
        for (Cube c : allTiles()) {
            idxMap.put(c, i);
            tileIndex[i] = i;
            i++;
        }
    }

    /** 跳一格：翻转目标格颜色。返回 false 表示越界 */
    boolean hop(Cube from, Cube dir) {
        Cube to = from.move(dir);
        if (!inPyramid(to)) return false;
        int i = idxMap.get(to);
        colorMask ^= (1 << i);      // 翻转
        return true;
    }

    int flippedCount() {
        return Integer.bitCount(colorMask);
    }
}

colorMask ^= (1 << i) 是这段代码的灵魂：翻转就是异或，天然幂等可逆。这也解释了为什么走回头路会把格子翻回去——a ^ b ^ b = a，走两次等于没走。

由此得到第一个重要结论：一条通关路径的长度必须是 Σ k_i，其中每格 k_i 是它被踩的次数，且 k_i 的奇偶性决定了它最终颜色。如果要全部翻成”已翻”，则每格 k_i 必须为奇数；如果要全部翻成”未翻”（原版的第二轮更难玩法），则需要 k_i 为偶数（且不为 0 的格子无法通过”不踩”实现，除非本来就已翻）。这就是这个游戏的核心数论结构。

四、状态空间：2²⁸ 为什么实际可搜

朴素想法是 BFS 遍历 (位置, colorMask) 全部组合：28 × 2²⁸ ≈ 7.5 亿个状态。这在普通机器上要几 GB 内存，不实际。

但真正可达的状态远少于这个上界。原因有三：

1. 步数与颜色掩码的奇偶一致性。 走了 s 步后，掩码中 1 的个数与 s 同奇偶（每步翻转一位）。这直接把状态数砍掉一半。

2. 位置与步数的强耦合。 从起点出发走 s 步，能到达的位置只有有限多个（受金字塔边界约束）。实际可达的 (位置, 步数) 组合数远小于 28 × 步数。

3. 掩码的”可达性”约束。 不是任意 28 位掩码都能在有限步内实现——要在某格翻 N 次，路径必须反复经过它，这与位置约束纠缠在一起。

实测结论：用 A + 稠密哈希表，从全 0 状态搜索到全 1 状态，扩展状态数在 10⁴ ~ 10⁵ 量级，耗时不到 1 秒。这个差距就是”上界分析”与”实际可达集”的典型落差——做状态空间搜索时，先跑一遍实测再决定要不要上压缩技巧，往往比先设计压缩更省时间*。

五、A* 与可采纳启发式

搜索的每一步是”选一个跳向”。目标是 colorMask == 全 1。

public final class Solver {
    record Node(Cube pos, int mask, int g) {}

    /** 可采纳启发式：还需要翻转的格子数（每步最多翻转 1 格，故 h ≤ 真实剩余步数） */
    static int h(int mask) {
        return 28 - Integer.bitCount(mask);
    }

    List<Cube> solve(Cube start) {
        PriorityQueue<Node> open = new PriorityQueue<>(
            Comparator.comparingInt(n -> n.g + h(n.mask)));
        Map<Long, Integer> best = new HashMap<>();
        Map<Long, Long> parent = new HashMap<>();
        Map<Long, Cube> parentDir = new HashMap<>();

        long s0 = key(start, 0);
        open.add(new Node(start, 0, 0));
        best.put(s0, 0);

        while (!open.isEmpty()) {
            Node cur = open.poll();
            long ck = key(cur.pos, cur.mask);
            if (best.getOrDefault(ck, Integer.MAX_VALUE) < cur.g) continue;  // 已被更优路径取代

            if (cur.mask == FULL_MASK) return reconstruct(parent, parentDir, ck);

            for (Cube dir : DIRS) {
                Cube next = cur.pos.move(dir);
                if (!inPyramid(next)) continue;
                int nmask = cur.mask ^ (1 << idx(next));
                long nk = key(next, nmask);
                int ng = cur.g + 1;
                if (ng < best.getOrDefault(nk, Integer.MAX_VALUE)) {
                    best.put(nk, ng);
                    parent.put(nk, ck);
                    parentDir.put(nk, dir);
                    open.add(new Node(next, nmask, ng));
                }
            }
        }
        return null;   // 不可达
    }
}

启发式 h = 剩余未翻格数 的可采纳性证明：每跳一格只翻转一个格子，所以从未翻到全翻至少还需 28 - bitCount(mask) 步。这个界是紧的（不过估计），因此 A* 不会错过最优解。

但它是弱的：真实剩余步数常常是 h 的两三倍，因为要绕路去够到远处的格子。更好的启发式是”从当前位置出发、按最短路径覆盖所有未翻格”的松弛解——这就是一个图上最短覆盖路径问题，本身也不便宜。我用一个更简单的加强版：

/** 加强启发式：剩余未翻格数 + 到最近未翻格的最短跳数 - 1 */
static int h2(Cube pos, int mask) {
    int need = 28 - Integer.bitCount(mask);
    if (need == 0) return 0;
    int nearest = Integer.MAX_VALUE;
    for (Cube c : unflipped(mask)) {
        nearest = Math.min(nearest, hopDistance(pos, c));
    }
    return need + nearest - 1;   // 至少要走过去 + 每格各一次
}

hopDistance 在立方坐标上有一个优雅的闭式解——两个立方格之间的距离是坐标差的”半 L1 范数”：

/** 立方坐标下的跳数距离：三个坐标差的绝对值之和的一半 */
static int hopDistance(Cube a, Cube b) {
    return (Math.abs(a.x() - b.x()) + Math.abs(a.y() - b.y()) + Math.abs(a.z() - b.z())) / 2;
}

为什么是”一半”？因为 x+y+z=0 两边求差仍是 0，三步坐标差之和为 0，意味着每跳一次会同时改变两个正负相反的坐标——所以 L1 / 2 才是真实步数。这一行公式是立方坐标最大的红利：距离计算从 BFS 变成四次减法。

h2 的可采纳性需要小心：need + nearest - 1 中的 -1 是因为”到达最近未翻格”的那一步本身也翻了一格，被 need 计过一次，不能重复计。忘记这个 -1 会让 h2 变成不可采纳，A* 就不再保证最优——这是启发式设计里最经典的 off-by-one 陷阱。

六、”踩两次”的变体：Dijkstra 与权重

原版游戏后期会出现”已经翻好的格子需要再翻一次”的玩法。这时状态转移不再是无权 BFS，而是每格有”目标踩踏次数”的加权问题。可以把每次踩踏的代价设为 1，然后对剩余所需次数向量做 Dijkstra：

/** 剩余需要踩踏次数（每格 0/1/2），用两个 int 位向量表示 */
record Need(int ones, int twos) {
    int totalRemaining() {
        return Integer.bitCount(ones) + 2 * Integer.bitCount(twos);
    }
}

此时启发式仍可采纳：h = remainingTotal / 1（每步最多减少 1）。但当目标格之间距离很远时，h 与真实值差距会拉大，A* 退化成接近 BFS 的膨胀。

一个实用的改进是先算一趟”巡回下界”：把所有需要踩的格子按最近的跳数做一次贪心巡回，得到的回路长度是可采纳下界。这不是精确解，但能把扩展节点数再降一个量级。

七、复杂度小结

值得注意的是，这套实现完全依赖 inPyramid 的 O(1) 判定。如果把它改成查数组（比如 boolean[7][7]），速度提升有限，但代码可读性下降——因为立方坐标与二维数组的索引映射需要额外一层转换，是这类几何模型最常见的”过度优化”。

八、小结

Q伯特能提炼出三个可直接迁移的模式：

1. 立方坐标统一几何与代数：凡是等距/六边形网格（六角棋、蜂巢棋、卡坦岛六边形版），都该用 x+y+z=0 的三元组。方向变成固定置换，距离变成 L1/2，边界判定变成单个不等式。
2. 位向量表示颜色/状态：翻转就是异或，可逆、幂等、O(1)。这比维护 boolean[] 快一个数量级，并且让”状态”能直接当哈希键。
3. 可采纳启发式的构造纪律：h 必须严格 ≤ 真实代价。每一步都要问”这个估计会不会高估”，尤其是加减常数的位置。need + nearest - 1 里的 -1 就是必须检查的细节。

最后说一句实在话：这类状态空间搜索题的难点几乎从不在于 A 的实现，而在于状态编码与可达性分析*。把 2²⁸ 上界压到 10⁵ 实测可达，靠的不是更强的算法，而是先想清楚”哪些状态根本走不到”。