Java 實現 24 點遊戲求解器：全排列與運算符組合算法

遊戲規則

隨機抽取 4 張撲克牌（數值 1~13），使用加減乘除及括號運算，結果等於 24 即獲勝。編程目標：給定 4 個數字，自動找出所有可行算式。

算法思路

1. 數字全排列：4 個數字有 4! = 24 種排列（去重後可能更少）。
2. 運算符組合：3 個運算符位置，每位 4 種選擇 (+, -, *, /)，共 4³ = 64 種。
3. 括號結構：4 個數字 3 步運算，二元樹結構固定為 5 種（Catalan 數 C₃=5），但本實現採用順序計算模擬：((a op b) op c) op d，配合數字排列已涵蓋所有等價形式。
4. 浮點數比較：設定精度 1e-5，判斷 |result - 24| < eps 或 |1/result - 24| < eps（處理除法倒數情況）。

核心代碼結構

public class Cal24 {
    private static final double EPS = 0.00001;
    private static final int TARGET = 24;

    public String[] execute(String[] inputs) {
        int[] digits = new int[4];
        for (int i = 0; i < 4; i++) digits[i] = Integer.valueOf(inputs[i]);
        return new String[]{calc(digits)};
    }

    private String calc(final int[] data) {
        final Set<String> results = new HashSet<>();
        // 1. 數字排列組合
        new Combination() {
            @Override protected void handle(int[] perm) {
                final int[] nums = perm;
                // 2. 運算符組合
                new Combination() {
                    @Override protected void handle(int[] ops) {
                        double val = nums[0];
                        for (int i = 0; i < 3; i++)
                            val = doCalculate(val, nums[i+1], ops[i]);
                        if (Math.abs(Math.abs(val) - TARGET) < EPS ||
                            Math.abs(Math.abs(1/val) - TARGET) < EPS) {
                            // 構建算式字符串
                            StringBuilder sb = new StringBuilder();
                            for (int j = 0; j < 4; j++) {
                                sb.append(nums[j]);
                                if (j < 3) sb.append(getOpChar(ops[j]));
                            }
                            results.add(sb.toString());
                        }
                    }
                }.combine(new int[]{0,1,2,3}, 3, true); // 運算符可重複
            }
        }.combine(data); // 數字不重複
        // 3. 輸出
        StringBuilder sb = new StringBuilder();
        for (String s : results) { sb.append(s).append("\n"); }
        return sb.toString();
    }

    private double doCalculate(double x, double y, int op) {
        switch(op) {
            case 0: return x + y;
            case 1: return x - y;
            case 2: return x * y;
            case 3: return y != 0 ? x / y : Double.MAX_VALUE;
            default: return 0;
        }
    }
    private String getOpChar(int op) {
        return new String[]{"+", "-", "*", "/"}[op];
    }
}

通用組合生成器 Combination

public abstract class Combination {
    private boolean repeat;
    private int total = 0;

    public void combine(int[] data) { combine(data, data.length, false); }
    public void combine(int[] data, int count) { combine(data, count, false); }
    public void combine(int[] data, int count, boolean repeat) {
        this.repeat = repeat;
        int n = data.length;
        int size = (int) Math.pow(n, count);
        for (int i = 0; i < size; i++) {
            int[] indices = toIndices(i, count, n);
            if (indices == null) continue;
            int[] result = new int[count];
            for (int j = 0; j < count; j++) result[j] = data[indices[j]];
            handle(result);
            total++;
        }
    }

    private int[] toIndices(int num, int count, int base) {
        int[] idx = new int[count];
        for (int i = 0; i < count; i++) {
            idx[i] = num % base;
            num /= base;
        }
        if (!repeat) {
            for (int i = 0; i < count; i++)
                for (int j = i+1; j < count; j++)
                    if (idx[i] == idx[j]) return null;
        }
        return idx;
    }
    public int getTotal() { return total; }
    protected abstract void handle(int[] result);
}

運行示例

輸入: 1 5 5 5
輸出:
5*5-1/5
5/(1-5/5)  (註: 此處邏輯需處理括號，當前順序計算模型可能漏解，見下文改進)
5*5*1-5
...

已知局限與改進方向

• 括號結構不完整：順序計算 ((a b) c) d 無法覆蓋 (a b) (c d) 等結構。改進：顯式枚舉 5 種二元樹結構並遞歸計算。
• 除零處理：當前返回 Double.MAX_VALUE 可能導致誤判，應跳過該分支。
• 結果去重：使用 HashSet 去重，但 1+2+3+4 與 4+3+2+1 視為不同，可進一步規範化表達式樹。
• 擴展：支援自定義目標數、N 個數字、更多運算符 (乘方、開根號)。

完整可運行主程序

public static void main(String[] args) {
    System.out.println(new Cal24().calc(new int[]{1, 5, 5, 5}));
}