每日算法 — 使用java实现祖玛：链表结构与递归连锁消除算法

祖玛（Zuma）是一款风靡全球的益智消除类游戏：彩色珠子沿着蜿蜒的轨道缓缓前进，玩家需要操控发射器射出彩球，当三个或更多同色球相连时便会触发消除，而消除后两侧球链如果因此相接并满足同色条件，还会引发连锁反应。看似简单的小游戏，背后却涉及链表结构的高效维护、递归连锁消除算法以及贪心落点决策策略三大核心算法问题。本文将用Java完整实现祖玛的核心消除引擎，从数据结构选型到算法细节逐一剖析。

一、问题建模与数据结构选型

1.1 为什么选择链表而非数组

祖玛的球链具有以下特性：
– 频繁插入：新球需要插入到链中任意位置
– 频繁删除：消除时可能一次性移除多个连续节点
– 动态变化：消除后左右两侧子链需要拼接

若使用数组，中间插入/删除的时间复杂度为 O(n)，且连锁消除时涉及大量元素移动。而双向链表可以在 O(1) 时间内完成节点插入与删除，仅查找插入点需要遍历，非常适合祖玛场景。

1.2 双向链表节点定义

/**
 * 祖玛球链节点
 * 每个节点代表轨道上的一个彩球
 */
class ZumaNode {
    // 球的颜色，用字符表示，如 'R'=红, 'G'=绿, 'B'=蓝, 'Y'=黄
    char color;
    // 前驱节点
    ZumaNode prev;
    // 后继节点
    ZumaNode next;

    ZumaNode(char color) {
        this.color = color;
        this.prev = null;
        this.next = null;
    }
}

1.3 球链容器与哨兵节点

使用哨兵头节点（Sentinel Head）和哨兵尾节点（Sentinel Tail）可以简化边界判断，避免处理空链或首尾节点的空指针问题：

/**
 * 祖玛球链
 * 维护双向链表，提供插入、删除、遍历等功能
 */
class ZumaChain {
    // 哨兵头节点，不存储实际数据
    private final ZumaNode head;
    // 哨兵尾节点，不存储实际数据
    private final ZumaNode tail;
    // 当前链中球的总数
    private int size;

    ZumaChain() {
        this.head = new ZumaNode('\0');
        this.tail = new ZumaNode('\0');
        this.head.next = this.tail;
        this.tail.prev = this.head;
        this.size = 0;
    }

    /**
     * 从字符串初始化球链
     * 例如 "RRGGBB" 表示红-红-绿-绿-蓝-蓝
     */
    void initFromString(String colors) {
        // 清空现有链
        head.next = tail;
        tail.prev = head;
        size = 0;
        for (char c : colors.toCharArray()) {
            append(c);
        }
    }

    /**
     * 在尾部追加一个球
     */
    private void append(char color) {
        ZumaNode node = new ZumaNode(color);
        ZumaNode last = tail.prev;
        last.next = node;
        node.prev = last;
        node.next = tail;
        tail.prev = node;
        size++;
    }

    /**
     * 在指定节点之后插入新球
     * @param target 插入位置的节点，新球将置于target之后
     * @param color 新球颜色
     */
    void insertAfter(ZumaNode target, char color) {
        ZumaNode node = new ZumaNode(color);
        ZumaNode next = target.next;
        target.next = node;
        node.prev = target;
        node.next = next;
        next.prev = node;
        size++;
    }

    /**
     * 删除一个节点
     * @param node 要删除的节点
     */
    void remove(ZumaNode node) {
        if (node == head || node == tail) return;
        ZumaNode prev = node.prev;
        ZumaNode next = node.next;
        prev.next = next;
        next.prev = prev;
        size--;
    }

    /**
     * 获取链中球的数量
     */
    int getSize() {
        return size;
    }

    /**
     * 获取第一个真实节点（跳过哨兵头）
     */
    ZumaNode getFirst() {
        return head.next == tail ? null : head.next;
    }

    /**
     * 将链转换为字符串表示，便于调试
     */
    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        ZumaNode cur = head.next;
        while (cur != tail) {
            sb.append(cur.color);
            cur = cur.next;
        }
        return sb.toString();
    }
}

二、核心算法一：发射球插入与落点查找

2.1 落点定位策略

玩家发射球后，需要确定球在链中的插入位置。在实际游戏中，这通常由碰撞检测决定——发射球沿直线飞行，与轨道上的球链相交时停止。为简化问题，本文采用索引定位模型：给定一个插入索引，将球插入到该位置。

/**
 * 根据索引查找对应节点
 * 索引从0开始，表示插入后新球所在的位置
 * @param index 目标索引
 * @return 索引位置的节点（若index==size则返回尾哨兵的前一个节点）
 */
ZumaNode findNodeAt(int index) {
    if (index < 0 || index > size) return null;
    ZumaNode cur = head;
    for (int i = 0; i < index && cur.next != tail; i++) {
        cur = cur.next;
    }
    return cur;
}

2.2 发射球并插入

/**
 * 发射一个彩球到指定位置
 * @param index 插入位置索引
 * @param color 球的颜色
 * @return 插入后的新节点
 */
ZumaNode shoot(int index, char color) {
    ZumaNode target = findNodeAt(index);
    if (target == null) return null;
    insertAfter(target, color);
    return target.next;
}

三、核心算法二：同色检测与递归连锁消除

3.1 单次消除原理

当新球插入后，需要检查以该球为中心、向左右扩展的连续同色球数量。若数量大于等于3，则触发消除：

/**
 * 统计以node为中心，向左右两侧延伸的连续同色球数量
 * 同时收集这些节点，便于后续删除
 * @param node 中心节点
 * @return 连续同色球的节点列表
 */
List<ZumaNode> collectSameColor(ZumaNode node) {
    List<ZumaNode> group = new ArrayList<>();
    if (node == null || node == head || node == tail) return group;
    char color = node.color;

    // 向左扩展
    ZumaNode left = node.prev;
    while (left != head && left.color == color) {
        group.add(left);
        left = left.prev;
    }

    // 加入中心节点
    group.add(node);

    // 向右扩展
    ZumaNode right = node.next;
    while (right != tail && right.color == color) {
        group.add(right);
        right = right.next;
    }

    return group;
}

3.2 递归连锁消除

消除一组球后，其左右两侧的球会”接壤”。如果这两个边界球颜色相同，且加上中间已消除的球后原本能形成消除条件，则需要再次检查。实际逻辑是：消除后，检查左侧边界节点与右侧边界节点是否颜色相同且各自延伸后总数量≥3。

更简洁的实现方式是：每次消除后，以左右边界为新的检查中心，递归执行消除，直到无法继续消除为止。

/**
 * 递归连锁消除
 * 从insertedNode开始检查，若形成消除则删除节点，然后检查左右接壤处是否继续触发消除
 * @param insertedNode 最近一次插入或引发消除的节点
 * @return 总共消除的球数
 */
int recursiveEliminate(ZumaNode insertedNode) {
    int totalEliminated = 0;

    // 收集以insertedNode为中心的连续同色球
    List<ZumaNode> group = collectSameColor(insertedNode);

    if (group.size() >= 3) {
        // 记录消除前左右边界节点（用于后续连锁检测）
        ZumaNode leftBoundary = group.get(0).prev;
        ZumaNode rightBoundary = group.get(group.size() - 1).next;

        // 删除所有同色球
        for (ZumaNode node : group) {
            remove(node);
        }
        totalEliminated += group.size();

        // 连锁消除检查：如果左右边界颜色相同，需要以该颜色继续检查
        // 实际上应该检查 leftBoundary.next（即消除后leftBoundary的后继）
        // 因为消除后leftBoundary和rightBoundary之间的节点已被删除
        // 此时leftBoundary.next 就是 rightBoundary（如果rightBoundary未被删除）
        // 所以我们需要找消除后的"接壤点"
        if (leftBoundary != head && rightBoundary != tail
                && leftBoundary.color == rightBoundary.color) {
            // 以leftBoundary或rightBoundary任一为起点检查连续同色
            // 注意：此时leftBoundary和rightBoundary在链中已经相邻
            List<ZumaNode> chainGroup = collectSameColor(leftBoundary);
            if (chainGroup.size() >= 3) {
                totalEliminated += recursiveEliminate(leftBoundary);
            }
        } else {
            // 即使颜色不同，也可能单侧形成消除（虽然通常单侧在新插入时不会单独形成≥3）
            // 但为了安全，分别检查左右边界
            if (leftBoundary != head) {
                List<ZumaNode> leftGroup = collectSameColor(leftBoundary);
                if (leftGroup.size() >= 3) {
                    totalEliminated += recursiveEliminate(leftBoundary);
                }
            }
            if (rightBoundary != tail) {
                List<ZumaNode> rightGroup = collectSameColor(rightBoundary);
                if (rightGroup.size() >= 3) {
                    totalEliminated += recursiveEliminate(rightBoundary);
                }
            }
        }
    }

    return totalEliminated;
}

3.3 更优雅的连锁消除实现

上述实现中边界处理略显复杂。一种更简洁的思路是：每次消除后，直接检查”接壤点”——即消除区间左侧节点和右侧节点在链中是否相邻且同色。如果相邻且同色，则以该颜色段为新的中心继续消除。

/**
 * 优化版连锁消除
 * 核心思想：消除一段后，检查left.prev和right.next是否因拼接而形成新的可消除段
 */
int eliminateChain(ZumaNode center) {
    int count = 0;
    List<ZumaNode> group = collectSameColor(center);

    while (group.size() >= 3) {
        // 记录边界
        ZumaNode leftNode = group.get(0).prev;
        ZumaNode rightNode = group.get(group.size() - 1).next;

        // 执行删除
        for (ZumaNode n : group) {
            remove(n);
        }
        count += group.size();

        // 消除后，leftNode和rightNode在链中已经相邻
        // 检查它们是否能形成新的消除
        if (leftNode != head && rightNode != tail && leftNode.color == rightNode.color) {
            // 以leftNode为起点重新收集（此时链中leftNode和rightNode相邻）
            group = collectSameColor(leftNode);
        } else {
            break;
        }
    }

    return count;
}

四、核心算法三：贪心落点决策

4.1 决策目标

在真实游戏中，玩家需要在有限时间内选择最佳发射角度。一个简单的贪心策略是：优先选择能引发消除的位置，若能引发连锁消除则更优；其次选择能阻止球链到达终点的位置。

4.2 评分函数

/**
 * 评估在指定位置插入某颜色球的收益
 * @param index 插入位置
 * @param color 球颜色
 * @return 收益评分（消除球数，0表示无法消除）
 */
int evaluateMove(int index, char color) {
    // 创建链的深拷贝进行模拟
    ZumaChain sim = this.deepCopy();
    ZumaNode inserted = sim.shoot(index, color);
    if (inserted == null) return 0;
    return sim.eliminateChain(inserted);
}

/**
 * 深拷贝当前链
 */
ZumaChain deepCopy() {
    ZumaChain copy = new ZumaChain();
    copy.initFromString(this.toString());
    return copy;
}

4.3 最优落点搜索

/**
 * 贪心策略：找到最佳发射位置和颜色组合
 * 遍历所有可能的插入位置和当前可用颜色，返回收益最高的操作
 * @param availableColors 当前发射器可用的颜色集合
 * @return 最佳操作 {index, color, score}
 */
int[] findBestMove(Set<Character> availableColors) {
    int bestIndex = -1;
    char bestColor = '\0';
    int bestScore = 0;

    for (int i = 0; i <= size; i++) {
        for (char color : availableColors) {
            int score = evaluateMove(i, color);
            if (score > bestScore) {
                bestScore = score;
                bestIndex = i;
                bestColor = color;
            }
        }
    }

    return new int[]{bestIndex, bestColor, bestScore};
}

五、完整运行示例

public class ZumaGame {
    public static void main(String[] args) {
        // 初始化球链：红-红-绿-蓝-蓝-绿-红
        ZumaChain chain = new ZumaChain();
        chain.initFromString("RRGBBGR");
        System.out.println("初始链: " + chain);

        // 场景1：在索引2后插入绿色球，应形成 "RRG G BBGR" -> 绿球连续3个，触发消除
        // 消除后：RR + BBGR = RRBBGR
        // 检查R和B接壤，不同色，停止
        System.out.println("\n--- 场景1：插入绿球触发单次消除 ---");
        ZumaChain c1 = chain.deepCopy();
        ZumaNode n1 = c1.shoot(2, 'G');
        System.out.println("插入后: " + c1);
        int eliminated1 = c1.eliminateChain(n1);
        System.out.println("消除数量: " + eliminated1);
        System.out.println("消除后: " + c1);

        // 场景2：构造连锁消除
        // 链：R-R-G-G-B-B-R-R
        // 在索引4后插入蓝色球：R-R-G-G-B-B-B-R-R -> 蓝球连续3个消除
        // 消除后：R-R-G-G + R-R = R-R-G-G-R-R
        // G和R接壤，不同色，不连锁
        // 再构造一个会连锁的例子：R-R-R-G-G-G-B-B-B
        // 在3个R和3个G之间插入G：R-R-R-G-G-G-G-B-B-B -> G消除 -> R-R-R和B-B-B接壤，不同色
        // 构造真正连锁：R-R-R-G-B-B-B-G-R-R-R
        // 中间BBB消除后，G和G接壤，形成G-G，加上消除的G原本是G-G-G-G？
        // 更清晰：R-R-R-G-B-B-B-G-G-R-R-R
        // 消除BBB -> R-R-R-G + G-G-R-R-R = R-R-R-G-G-G-R-R-R -> G连续3个消除
        // -> R-R-R + R-R-R = R-R-R-R-R-R -> R连续6个消除
        System.out.println("\n--- 场景2：构造连锁消除 ---");
        ZumaChain c2 = new ZumaChain();
        c2.initFromString("RRRGBBBGGRRR");
        System.out.println("初始链: " + c2);
        // 在索引7后插入G（即在BBB后的G之前）
        // 实际链：R R R G B B B G G R R R
        // 索引： 0 1 2 3 4 5 6 7 8 9 10 11
        // 在索引6（第三个B）后插入G：
        ZumaNode n2 = c2.shoot(6, 'G');
        System.out.println("插入G后: " + c2);
        int eliminated2 = c2.eliminateChain(n2);
        System.out.println("连锁消除总数: " + eliminated2);
        System.out.println("最终链: " + c2);

        // 场景3：贪心最优决策
        System.out.println("\n--- 场景3：贪心最优落点决策 ---");
        ZumaChain c3 = new ZumaChain();
        c3.initFromString("RRGGBBRR");
        System.out.println("初始链: " + c3);
        Set<Character> colors = new HashSet<>(Arrays.asList('R', 'G', 'B'));
        int[] best = c3.findBestMove(colors);
        System.out.println("最佳操作: 位置=" + best[0] + ", 颜色=" + (char)best[1] + ", 消除数=" + best[2]);
    }
}

六、复杂度分析

其中 n 为链中球的总数。贪心决策的复杂度较高，实际游戏中可采用启发式剪枝（如只评估与发射球颜色相同的最近邻位置）来降低搜索空间。

七、延伸优化方向

1. A*寻路辅助落点：在带有物理轨道的高级版本中，发射球沿固定轨道飞行，可用A*或射线投射计算精确碰撞点。
2. 记忆化评估：对常见局部模式（如 “AABBA” 型）预先计算最优解，构建模式数据库加速决策。
3. 多步前瞻（Minimax）：将祖玛建模为双人对抗（玩家 vs 系统发球），使用Minimax算法进行多步规划，而非单步贪心。
4. 空间压缩：对于超长球链，可考虑将连续同色球压缩为 (color, count) 的段节点，进一步减少遍历开销。

八、总结

本文通过Java实现了祖玛游戏的核心消除引擎，重点展示了三个算法要点：

• 双向链表作为球链的底层结构，以 O(1) 时间完成节点插入与删除，远优于数组方案。
• 递归连锁消除算法通过循环检测消除后的边界拼接，实现了连续消除的自动化处理。
• 贪心落点策略通过模拟评估选择收益最高的发射方案，为AI对战提供了基础决策能力。

祖玛虽小，却是一个集数据结构、递归算法与贪心策略于一体的绝佳算法学习案例。