每日算法 — 使用java实现24点游戏：回溯搜索与表达式求值剪枝优化

24点是一款家喻户晓的数学益智游戏：给定4个正整数，通过加减乘除和括号运算，使最终结果恰好等于24。每张牌必须且只能使用一次。这个看似简单的规则背后，隐藏着组合爆炸的搜索空间与精妙的剪枝艺术。本文将用Java实现一个完整的24点求解器，系统讲解回溯搜索如何枚举所有可能的运算顺序、表达式树如何优雅存储与求值，以及多种剪枝策略如何将无效分支扼杀在萌芽状态。

一、问题建模：从卡牌到搜索树

24点的核心挑战在于运算顺序的多样性。4个数字的全排列有4! = 24种，3个运算符位置每个有4种选择（+、-、*、/），共4³ = 64种，而加括号的方式又有5种本质不同的结构。理论上总组合数为24 × 64 × 5 = 7680种。但由于除法产生分数、减法不满足交换律，实际搜索空间更加复杂。

关键观察是：运算具有二元性。无论怎么加括号，本质上都是反复从当前数字集合中选取两个数，进行某种运算，将结果放回集合，直到只剩一个数。这种”归约”视角天然适合递归回溯。

例如对于数字 [3, 8, 3, 8]，一种解法是：
1. 选 8 和 3，做除法：8 / 3 = 8/3，集合变为 [3, 8, 8/3]
2. 选 8/3 和 3，做减法：8/3 – 3 = -1/3，集合变为 [8, -1/3]
3. 选 8 和 -1/3，做除法：8 / (-1/3) = -24 —— 不对

正确的解法是 8 / (3 – 8/3) = 24。这要求我们在每一步都尝试所有可能的两数组合、所有运算符、以及运算顺序（因为减法和除法不满足交换律）。

二、表达式树：存储与求值的核心数据结构

为了同时输出求解过程和最终结果，我们引入表达式树节点。每个节点要么是叶子（原始数字），要么是内部节点（运算符 + 左右子树）。

/**
 * 表达式树节点
 * 用于存储24点求解过程中的运算表达式，支持递归求值和字符串输出
 */
class ExprNode {
    double value;           // 节点求值结果
    String expr;            // 中缀表达式字符串表示
    boolean isLeaf;         // 是否为叶子节点（原始数字）
    ExprNode left, right;   // 左右子树
    char op;                // 运算符（仅内部节点有效）

    // 叶子节点构造器
    ExprNode(double value) {
        this.value = value;
        this.expr = String.valueOf((int) value);
        this.isLeaf = true;
    }

    // 内部节点构造器
    ExprNode(ExprNode left, ExprNode right, char op) {
        this.left = left;
        this.right = right;
        this.op = op;
        this.isLeaf = false;
        // 根据运算符计算结果
        this.value = applyOp(left.value, right.value, op);
        // 构建中缀表达式字符串，注意括号优先级
        this.expr = buildExpr(left, right, op);
    }

    /**
     * 执行二元运算
     * 对除法进行零值保护，返回NaN表示非法运算
     */
    static double applyOp(double a, double b, char op) {
        switch (op) {
            case '+': return a + b;
            case '-': return a - b;
            case '*': return a * b;
            case '/': return Math.abs(b) < 1e-9 ? Double.NaN : a / b;
            default:  return Double.NaN;
        }
    }

    /**
     * 构建中缀表达式字符串
     * 根据运算符优先级决定是否添加括号
     */
    static String buildExpr(ExprNode left, ExprNode right, char op) {
        String l = left.expr;
        String r = right.expr;
        // 当前节点优先级
        int curPriority = priority(op);
        // 若左子树根运算符优先级低于当前，需加括号
        if (!left.isLeaf && priority(left.op) < curPriority) {
            l = "(" + l + ")";
        }
        // 若右子树根运算符优先级低于当前，或等于当前但运算符不满足结合律（减法和除法），需加括号
        if (!right.isLeaf) {
            int rp = priority(right.op);
            if (rp < curPriority || (rp == curPriority && (op == '-' || op == '/'))) {
                r = "(" + r + ")";
            }
        }
        return l + " " + op + " " + r;
    }

    static int priority(char op) {
        if (op == '+' || op == '-') return 1;
        if (op == '*' || op == '/') return 2;
        return 0;
    }
}

表达式树的设计精妙之处在于：它不预先假设括号位置，而是通过树结构隐式表达运算顺序。不同的树形对应不同的加括号方式，而buildExpr方法根据运算符优先级自动添加必要的括号，保证输出表达式既正确又简洁。

三、回溯搜索：枚举所有归约路径

核心算法采用深度优先搜索：从当前数字集合中任选两个数，尝试四种运算（注意减法和除法有两种顺序），将结果放回集合，递归搜索直到集合大小为1。若最终结果为24（允许浮点误差），则找到解。

import java.util.*;

/**
 * 24点求解器
 * 基于回溯搜索枚举所有数字组合与运算顺序
 */
public class Game24Solver {
    // 允许浮点误差范围
    private static final double EPS = 1e-6;
    // 目标值
    private static final double TARGET = 24.0;
    // 四种运算符
    private static final char[] OPS = {'+', '-', '*', '/'};

    /**
     * 求解入口：给定4个整数，返回所有不同的解表达式
     */
    public List<String> solve(int[] nums) {
        List<String> results = new ArrayList<>();
        List<ExprNode> nodes = new ArrayList<>();
        for (int num : nums) {
            nodes.add(new ExprNode(num));
        }
        dfs(nodes, results);
        return results;
    }

    /**
     * 深度优先搜索核心
     * @param nodes 当前可用的表达式节点集合
     * @param results 存储找到的解
     */
    private void dfs(List<ExprNode> nodes, List<String> results) {
        // 剪枝1：若已找到足够解可提前返回（视需求而定）
        // if (results.size() >= 5) return;

        int n = nodes.size();
        if (n == 1) {
            // 只剩一个数，检查是否等于目标值
            if (Math.abs(nodes.get(0).value - TARGET) < EPS) {
                results.add(nodes.get(0).expr + " = 24");
            }
            return;
        }

        // 枚举所有无序的两数组合 (i, j)，其中 i < j
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                ExprNode a = nodes.get(i);
                ExprNode b = nodes.get(j);

                // 对每种运算符尝试两种顺序（+和*只需一种，-和/需要两种）
                for (char op : OPS) {
                    // 顺序1: a op b
                    tryCombine(nodes, i, j, a, b, op, results);
                    // 顺序2: b op a（若运算符不满足交换律且两数不同）
                    if ((op == '-' || op == '/') && Math.abs(a.value - b.value) > EPS) {
                        tryCombine(nodes, i, j, b, a, op, results);
                    }
                }
            }
        }
    }

    /**
     * 尝试将两个节点合并，递归搜索
     */
    private void tryCombine(List<ExprNode> nodes, int i, int j,
                            ExprNode left, ExprNode right, char op,
                            List<String> results) {
        double val = ExprNode.applyOp(left.value, right.value, op);
        // 剪枝2：非法运算（除零）
        if (Double.isNaN(val)) return;

        // 剪枝3：中间结果过大或过小，不可能通过后续运算得到24
        if (Math.abs(val) > 1e6 || (Math.abs(val) < EPS && Math.abs(val) > 0)) {
            return;
        }

        ExprNode merged = new ExprNode(left, right, op);

        // 构建新的节点集合：移除i和j，加入合并后的节点
        List<ExprNode> next = new ArrayList<>();
        for (int k = 0; k < nodes.size(); k++) {
            if (k != i && k != j) {
                next.add(nodes.get(k));
            }
        }
        next.add(merged);

        dfs(next, results);
    }
}

四、剪枝策略：扼杀无效分支的艺术

24点搜索虽然规模不大，但加入以下剪枝策略能显著提升速度，更重要的是展示了回溯算法优化的通用思路：

4.1 除零剪枝

在applyOp中检测除数接近零时返回NaN，外层直接跳过该分支。这是最基础的合法性剪枝。

4.2 中间结果范围剪枝

若某步运算结果的绝对值超过10⁶，或产生极接近零的非零值（如1e-12），则后续运算几乎不可能精确收敛到24。这种范围剪枝在搜索问题中极为常见。

4.3 重复状态剪枝（去重）

当输入中有重复数字时（如 [3, 3, 8, 8]），交换两个相同数字的位置会产生冗余搜索。为避免重复解，我们在每一层递归中对节点值进行排序后去重：

/**
 * 生成下一层节点集合时，对节点值排序并跳过重复组合
 * 此方法在dfs中替换原有的next构建逻辑
 */
private void dfsWithDeduplication(List<ExprNode> nodes, List<String> results) {
    int n = nodes.size();
    if (n == 1) {
        if (Math.abs(nodes.get(0).value - TARGET) < EPS) {
            results.add(nodes.get(0).expr + " = 24");
        }
        return;
    }

    // 用Set记录已尝试的无序对（按值），避免重复数字导致的冗余
    Set<String> triedPairs = new HashSet<>();

    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            String pairKey = String.format("%.6f_%.6f",
                nodes.get(i).value, nodes.get(j).value);
            if (triedPairs.contains(pairKey)) continue;
            triedPairs.add(pairKey);

            // ... 尝试合并 ...
        }
    }
}

注意：此处的去重是基于数值相等而非对象引用。对于浮点结果，使用固定精度格式化后比较。

4.4 对称运算剪枝

加法和乘法满足交换律，a + b 与 b + a 等价。在核心dfs中，我们在运算符为+或*时只尝试一种顺序，而-和/才尝试两种顺序，这已经避免了一部分冗余。若两数数值相等，即使对于-和/，结果也必然相同（a - a = 0、a / a = 1），因此可进一步跳过。

五、完整运行示例

将以上模块整合后，我们得到可独立运行的24点求解器：

public class Main {
    public static void main(String[] args) {
        Game24Solver solver = new Game24Solver();

        // 经典难题：3, 3, 8, 8
        int[] case1 = {3, 3, 8, 8};
        System.out.println("=== 3, 3, 8, 8 ===");
        List<String> sol1 = solver.solve(case1);
        sol1.forEach(System.out::println);

        // 多解案例：4, 4, 10, 10
        int[] case2 = {4, 4, 10, 10};
        System.out.println("\n=== 4, 4, 10, 10 ===");
        List<String> sol2 = solver.solve(case2);
        sol2.forEach(System.out::println);

        // 无解案例：1, 1, 1, 1
        int[] case3 = {1, 1, 1, 1};
        System.out.println("\n=== 1, 1, 1, 1 ===");
        List<String> sol3 = solver.solve(case3);
        if (sol3.isEmpty()) {
            System.out.println("无解");
        } else {
            sol3.forEach(System.out::println);
        }
    }
}

对于 [3, 3, 8, 8]，程序输出：

8 / (3 - 8 / 3) = 24

对于 [4, 4, 10, 10]，程序可找到多个等价解，如 (10 * 10 - 4) / 4 = 24。

六、复杂度分析

虽然24点本身的规模很小，但其算法框架——从集合中反复选取元素合并，直到满足终止条件——是回溯搜索的经典范式，广泛应用于矩阵链乘法、最优二叉搜索树、电路布线等问题的子结构枚举。

七、延伸与变体

7.1 扩展到N个数求Target

将代码中的常量4和24参数化，即可求解”N个数凑成M”的通用问题。随着N增大，搜索空间指数级增长，此时需要更激进的剪枝或引入启发式排序（优先尝试乘除，因为乘除更容易快速接近目标）。

7.2 分数精度处理

由于除法产生分数，使用double可能在极端情况下因精度丢失而漏判。更严谨的实现可采用分数类（自定义分子/分母的大整数表示），确保精确比较。这对教学目的很有帮助，但会显著增加代码量。

7.3 与强化学习的结合

若将24点视为序贯决策问题（每步选两个数和运算符），可训练一个价值网络评估当前数字集合”离24有多近”，用蒙特卡洛树搜索（MCTS）替代纯回溯。这在N较大时比暴力搜索更高效，也是AlphaZero等系统的核心思想在简单问题上的投射。

八、总结

本文通过Java实现了24点游戏的完整求解器，核心要点包括：

• 表达式树以隐式树结构表达运算顺序，自动处理括号优先级，兼具存储与求值能力。
• 回溯搜索通过”选两数、运算、放回”的归约策略，系统枚举所有可能的运算序列。
• 多级剪枝（除零、范围、重复状态、对称运算）大幅削减无效分支，体现了搜索算法优化的精髓。

24点虽小，却浓缩了组合搜索、表达式处理与剪枝优化的核心技巧，是理解回溯算法的绝佳切入点。