24点游戏求解工具

问题描述

给定四个数字，使用加法、减法、乘法、除法和括号，尝试通过不同的运算组合得到24。

24点求解器

输入四个数字，自动计算所有可能的解法

核心算法原理

24点求解的核心思路是：

1. 排列组合：生成四个数字的所有排列
2. 运算符组合：生成三个运算符位置的所有可能
3. 表达式结构：考虑不同的括号组合方式
4. 结果验证：计算表达式结果是否等于24

算法实现

以下是使用JavaScript实现24点求解算法的分步骤讲解。

步骤1：数字排列生成器

我们需要生成四个数字的所有排列组合。

function generatePermutations(nums) {
    if (nums.length === 1) return [nums];
    const permutations = [];
    for (let i = 0; i < nums.length; i++) {
        const rest = nums.slice(0, i).concat(nums.slice(i + 1));
        const restPermutations = generatePermutations(rest);
        for (const perm of restPermutations) {
            permutations.push([nums[i], ...perm]);
        }
    }
    return permutations;
}

// 示例：[3, 8, 8, 9] 生成24种排列（考虑重复数字优化）
console.log(generatePermutations([3, 8, 8, 9]));

步骤2：运算符组合生成器

生成三个运算符位置的所有可能组合（4³ = 64种）。

function generateOperators() {
    const operators = ['+', '-', '*', '/'];
    const combinations = [];
    for (const op1 of operators) {
        for (const op2 of operators) {
            for (const op3 of operators) {
                combinations.push([op1, op2, op3]);
            }
        }
    }
    return combinations;
}

// 示例：['+', '-', '*'] 等64种组合
console.log(generateOperators().length); // 64

步骤3：表达式结构生成器

枚举所有可能的表达式结构，主要包括5种括号组合方式。

function generateExpressions(nums, ops) {
    const [a, b, c, d] = nums;
    const [op1, op2, op3] = ops;
    
    return [
        // 类型1: ((a op1 b) op2 c) op3 d
        `((${a} ${op1} ${b}) ${op2} ${c}) ${op3} ${d}`,
        // 类型2: (a op1 (b op2 c)) op3 d  
        `(${a} ${op1} (${b} ${op2} ${c})) ${op3} ${d}`,
        // 类型3: (a op1 b) op2 (c op3 d)
        `(${a} ${op1} ${b}) ${op2} (${c} ${op3} ${d})`,
        // 类型4: a op1 ((b op2 c) op3 d)
        `${a} ${op1} ((${b} ${op2} ${c}) ${op3} ${d})`,
        // 类型5: a op1 (b op2 (c op3 d))
        `${a} ${op1} (${b} ${op2} (${c} ${op3} ${d}))`
    ];
}

// 示例：生成不同括号结构的表达式
console.log(generateExpressions([3, 8, 8, 9], ['+', '-', '*']));

步骤4：表达式计算与验证

安全地计算表达式结果并验证是否等于24。

function evaluateExpression(expr) {
    try {
        // 使用Function构造器代替eval，更安全
        const result = new Function('return ' + expr)();
        return Math.abs(result - 24) < 1e-9;
    } catch (error) {
        // 处理除零等异常情况
        return false;
    }
}

// 示例：验证表达式是否等于24
console.log(evaluateExpression('(9 - 8) * 8 * 3')); // true
console.log(evaluateExpression('3 + 8 + 8 + 9'));   // false

步骤5：完整求解算法

整合所有步骤，实现完整的24点求解器。

function solve24Points(inputNumbers) {
    const permutations = generatePermutations(inputNumbers);
    const operators = generateOperators();
    const solutions = [];
    
    for (const perm of permutations) {
        for (const ops of operators) {
            const expressions = generateExpressions(perm, ops);
            
            for (const expr of expressions) {
                if (evaluateExpression(expr)) {
                    solutions.push(expr);
                    // 如果只需要一个解，可以在这里return
                    // return expr;
                }
            }
        }
    }
    
    // 去重并返回所有解
    return [...new Set(solutions)];
}

// 示例：求解 [3, 8, 8, 9]
const solutions = solve24Points([3, 8, 8, 9]);
console.log('找到解法：', solutions.length > 0 ? solutions[0] : '无解');