lxvi. 24 Game and Countdown

Problem. Given four numbers (usually $\mathrm{1..13}$), combine all of them with $+,-,\times ,÷$ and parentheses to make $24$. Countdown is the same search with six numbers and any target.

Solution: recursive search: pick any ordered pair, replace it by the result of an operation, recurse on the shorter list; use exact fractions (division is real division, and $8/(3-8/3)=24$ needs non-integer intermediates).

bool make24(vector<pair<long long, long long>> v) {     // fractions (num, den); +, -, *, / on any pair
    if (sz(v) == 1) return v[0].second != 0 && v[0].first == 24 * v[0].second;
    for (int i = 0; i < sz(v); i++) for (int j = 0; j < sz(v); j++) if (i != j) {
        auto [a, b] = v[i]; auto [c, d] = v[j];
        vector<pair<long long, long long>> rest;
        for (int k = 0; k < sz(v); k++) if (k != i && k != j) rest.push_back(v[k]);
        vector<pair<long long, long long>> cand = {{a * d + b * c, b * d}, {a * d - b * c, b * d}, {a * c, b * d}};
        if (c != 0) cand.push_back({a * d, b * c});
        for (auto [p, q] : cand) {
            if (q < 0) p = -p, q = -q;
            long long g = __gcd(llabs(p), q); if (g) p /= g, q /= g;
            rest.push_back({p, q}); if (make24(rest)) return true; rest.pop_back();
        }
    }
    return false;
}

Input	Result
1 5 5 5	$5\times (5-1/5)=24$
3 3 8 8	$8/(3-8/3)=24$
4 4 10 10	$(10\times 10-4)/4=24$
1 1 1 1, 1 1 1 2	impossible

Proof: the search is complete

Every expression tree over the numbers has a last-evaluated operation at some internal node whose children are two leaves (or already-reduced subexpressions); evaluating that node first and replacing it by its value gives a valid expression on one fewer number with the same value. So every expression corresponds to a sequence of pair reductions, and the recursion tries every pair, every order (for $-$ and $÷$), and every operation; with exact fractions no value is lost to rounding. The number of states is small ($4$ numbers: under $10^4$ reductions). Checked on the classic instances in the table.