每日算法 — 使用java实现24点游戏：DFS全排列与分数运算精确求解

引言

24点游戏是广受欢迎的数学益智游戏：给定4个1-13之间的整数，通过加减乘除和括号组合，使最终运算结果恰好等于24。这个游戏看似简单，实则蕴含丰富的算法思想——全排列枚举、递归回溯、表达式解析与分数精确运算。本文将用Java实现一个完整的24点求解器，核心亮点在于使用分数类避免浮点精度误差，确保算法在数学上的严格正确性。

问题分析

24点求解的关键难点有三：

数字排列组合：4个数字可以任意交换位置，共有 4! = 24 种排列
运算符选择：每两个数字之间可以放置 +、-、*、/ 四种运算符，3个位置共 4³ = 64 种组合
括号优先级：不同的括号位置会产生不同的运算顺序，主要有 5 种本质不同的结合方式

若不考虑括号，总搜索空间约为 24 × 64 = 1536 种；加上括号的多种组合方式，总搜索空间约 7680 种。这个规模非常适合用深度优先搜索（DFS）暴力枚举。

核心算法设计

1. 分数类精确运算

使用 double 进行除法运算会引入精度误差，可能导致误判（如 3/7 + 5*7 = 24.0000001）。本文设计 Fraction 分数类，用分子分母整数对精确表示有理数：

class Fraction {
    long num, den; // 分子、分母（den > 0）

    Fraction(long n, long d) {
        long g = gcd(Math.abs(n), Math.abs(d));
        num = n / g;
        den = d / g;
        if (den < 0) { num = -num; den = -den; }
    }

    static long gcd(long a, long b) {
        return b == 0 ? a : gcd(b, a % b);
    }

    Fraction add(Fraction o) {
        return new Fraction(num * o.den + o.num * den, den * o.den);
    }

    Fraction subtract(Fraction o) {
        return new Fraction(num * o.den - o.num * den, den * o.den);
    }

    Fraction multiply(Fraction o) {
        return new Fraction(num * o.num, den * o.den);
    }

    Fraction divide(Fraction o) {
        return new Fraction(num * o.den, den * o.num);
    }

    boolean equals24() {
        return num == 24 && den == 1;
    }

    @Override
    public String toString() {
        return den == 1 ? String.valueOf(num) : num + "/" + den;
    }
}

2. DFS枚举所有表达式

采用递归方式从数字数组中每次选取两个数，用四种运算符组合，将结果放回数组，直到数组只剩一个数时判断是否等于24：

import java.util.*;

public class Game24Solver {

    // 核心DFS：从nums中递归选取两个数进行运算
    static boolean solve(List<Fraction> nums, StringBuilder expr, List<String> solutions) {
        if (nums.size() == 1) {
            if (nums.get(0).equals24()) {
                solutions.add(expr.toString());
                return true; // 找到一个解即可返回，或继续找所有解
            }
            return false;
        }

        // 枚举每对数字
        for (int i = 0; i < nums.size(); i++) {
            for (int j = 0; j < nums.size(); j++) {
                if (i == j) continue;

                Fraction a = nums.get(i);
                Fraction b = nums.get(j);
                List<Fraction> next = new ArrayList<>();

                // 将未选中的数字加入下一轮
                for (int k = 0; k < nums.size(); k++) {
                    if (k != i && k != j) next.add(nums.get(k));
                }

                // 四种运算
                // 加法（去重：若 a+b 与 b+a 相同，只需算一次）
                if (i < j) {
                    next.add(a.add(b));
                    if (solve(next, new StringBuilder(), solutions)) return true;
                    next.remove(next.size() - 1);
                }

                // 减法
                next.add(a.subtract(b));
                if (solve(next, new StringBuilder(), solutions)) return true;
                next.remove(next.size() - 1);

                // 乘法（去重）
                if (i < j) {
                    next.add(a.multiply(b));
                    if (solve(next, new StringBuilder(), solutions)) return true;
                    next.remove(next.size() - 1);
                }

                // 除法（除数不能为0）
                if (b.num != 0) {
                    next.add(a.divide(b));
                    if (solve(next, new StringBuilder(), solutions)) return true;
                    next.remove(next.size() - 1);
                }
            }
        }
        return false;
    }

    public static void main(String[] args) {
        int[] cards = {3, 3, 8, 8}; // 经典难题
        List<Fraction> nums = new ArrayList<>();
        for (int c : cards) nums.add(new Fraction(c, 1));

        List<String> solutions = new ArrayList<>();
        solve(nums, new StringBuilder(), solutions);

        System.out.println("输入: " + Arrays.toString(cards));
        if (solutions.isEmpty()) {
            System.out.println("无解");
        } else {
            System.out.println("找到解：" + solutions.get(0));
            // 3 3 8 8 的经典解: 8/(3-8/3)=24
        }
    }
}

3. 表达式构建与输出

上述代码仅判断是否存在解，若要输出可读表达式，需在递归时传递表达式字符串：

static boolean solveWithExpr(List<Fraction> nums, List<String> exprs, List<String> solutions) {
    if (nums.size() == 1) {
        if (nums.get(0).equals24()) {
            solutions.add(exprs.get(0));
            return true;
        }
        return false;
    }

    for (int i = 0; i < nums.size(); i++) {
        for (int j = 0; j < nums.size(); j++) {
            if (i == j) continue;

            String aStr = exprs.get(i);
            String bStr = exprs.get(j);

            List<Fraction> nextNums = new ArrayList<>();
            List<String> nextExprs = new ArrayList<>();

            for (int k = 0; k < nums.size(); k++) {
                if (k != i && k != j) {
                    nextNums.add(nums.get(k));
                    nextExprs.add(exprs.get(k));
                }
            }

            // 加法
            if (i < j) {
                nextNums.add(nums.get(i).add(nums.get(j)));
                nextExprs.add("(" + aStr + "+" + bStr + ")");
                if (solveWithExpr(nextNums, nextExprs, solutions)) return true;
                nextNums.remove(nextNums.size()-1);
                nextExprs.remove(nextExprs.size()-1);
            }

            // 减法
            nextNums.add(nums.get(i).subtract(nums.get(j)));
            nextExprs.add("(" + aStr + "-" + bStr + ")");
            if (solveWithExpr(nextNums, nextExprs, solutions)) return true;
            nextNums.remove(nextNums.size()-1);
            nextExprs.remove(nextExprs.size()-1);

            // 乘法
            if (i < j) {
                nextNums.add(nums.get(i).multiply(nums.get(j)));
                nextExprs.add("(" + aStr + "*" + bStr + ")");
                if (solveWithExpr(nextNums, nextExprs, solutions)) return true;
                nextNums.remove(nextNums.size()-1);
                nextExprs.remove(nextExprs.size()-1);
            }

            // 除法
            if (nums.get(j).num != 0) {
                nextNums.add(nums.get(i).divide(nums.get(j)));
                nextExprs.add("(" + aStr + "/" + bStr + ")");
                if (solveWithExpr(nextNums, nextExprs, solutions)) return true;
            }
        }
    }
    return false;
}

复杂度分析

时间复杂度：最坏情况下需要枚举所有数字对、运算符和排列组合。对于4个数字，状态数约为 O((n!) × 4^(n-1) × C(n))，其中 n=4 时约为数千个状态，现代计算机可瞬间完成。
空间复杂度：递归深度为 n-1 = 3，空间复杂度 O(n)，主要用于递归栈和分数对象。

扩展思考

扩展到n个数求目标值：将 equals24() 改为传入目标值参数即可求解任意目标的n个数问题
去重优化：通过 i < j 约束避免加法和乘法的重复计算，将搜索空间减半
中间结果剪枝：若中间结果的分子或分母过大，可提前剪枝（分数会迅速膨胀）

小结

本文通过Java实现了24点游戏的完整求解器，核心亮点在于：
– 使用自定义分数类彻底避免浮点精度问题
– DFS递归枚举所有可能的运算顺序
– 表达式字符串同步构建，输出人类可读的解

24点游戏虽小，却涵盖了递归回溯、枚举剪枝、精确运算等多个算法核心思想，是算法入门的优质练习素材。

Tagged with: 24点游戏 DFS 回溯表达式求值

引言