C++で解く24ゲーム：四則演算で24を作れるか判定するアルゴリズム

問題の概要

1から9までのいずれかの数値が書かれたカードが4枚あるとします。これらの数値に対して「+（足し算）」「-（引き算）」「*（掛け算）」「/（割り算）」の四則演算を自由に組み合わせ、計算結果をちょうど24にできるかどうかを判定するのが、いわゆる「24ゲーム」と呼ばれる問題です。

たとえば、手元のカードが [4, 9, 2, 6] だった場合、(4 * 9) - (2 * 6) という式で 36 − 12 = 24 が求められるため、答えは true（24が作れる）となります。

解法のアプローチ：バックトラッキング

この問題はバックトラッキング（試行錯誤しながら探索を進め、行き詰まったら一歩戻る手法）を用いることで効率的に解けます。基本的な発想はシンプルで、「4つの数の中から2つを選び、演算して1つにまとめる」という操作を繰り返し、最終的に残った1つの数が24になるかどうかを確認します。

アルゴリズムの手順

1. 許容誤差の設定： 割り算によって小数が生じる可能性があるため、厳密な等号比較は行いません。epsilon = 10^-5 を許容誤差として定義しておきます。
2. 再帰関数 solve(v) の定義： 引数として数値の配列 v を受け取ります。
   • 配列 v の要素数が 1 になった場合、|v[0] − 24.0| ≤ epsilon を満たしていれば true を返します。
   • まだ複数の要素がある場合は、二重ループですべての順序付きペア (i, j) を列挙します。i と j が同じ場合はスキップします。
   • ペア以外の残りの要素をすべて新しい配列 res にコピーします。
   • 4種類の演算子それぞれについて、v[i] と v[j] を演算した結果を res の末尾に追加し、solve(res) を再帰的に呼び出します。
   • 再帰呼び出しの結果が true であれば、その時点で true を返します。そうでなければ、追加した要素を pop_back で取り除き（バックトラック）、次の演算子を試します。
3. すべての組み合わせを試しても成功しなければ、false を返します。
4. メイン処理： 入力 nums を double 型の配列 v に変換し、solve(v) を呼び出してその結果を返します。

それでは、実際のコードを見ながら理解を深めていきましょう。

C++での実装例

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
    char operators[4] = {'+', '-', '/', '*'};
    double epsilon = pow(10.0, -5);
    bool judgePoint24(vector<int>& nums) {
        vector<double> v;
        for(int i = 0; i < nums.size(); i++){
            v.push_back(nums[i]);
        }
        return solve(v);
    }
    bool solve(vector<double> v){
        if(v.size() == 1){
            return abs(v[0] - 24.0) <= epsilon;
        }
        for(int i = 0; i < v.size(); i++){
            for(int j = 0; j < v.size(); j++){
                if(i == j) continue;
                vector<double> res;
                for(int k = 0; k < v.size(); k++){
                    if(i != k && j != k){
                        res.push_back(v[k]);
                    }
                }
                for(int k = 0; k < 4; k++){
                    if(operators[k] == '+'){
                        res.push_back(v[i] + v[j]);
                    }else if(operators[k] == '-'){
                        res.push_back(v[i] - v[j]);
                   }else if(operators[k] == '*'){
                        res.push_back(v[i] * v[j]);
                   }else{
                        res.push_back(v[i] / v[j]);
                   }
                   if(solve(res)) return true;
                   res.pop_back();
                }
            }
        }
        return false;
    }
};
main(){
    Solution ob;
    vector<int> v = {4,9,2,6};
    cout << (ob.judgePoint24(v));
}

入力例

{4,9,2,6}

出力例

1

コードのポイント

• 数値を double 型で扱うことで、割り算によって生じる小数にも正しく対応できます。
• 浮動小数点数には計算誤差が伴うため、結果が24と完全に一致しているかではなく、差が epsilon（10^-5）以内に収まっているかで判定しています。
• 演算結果を push_back で追加して再帰呼び出しを行い、失敗したら pop_back で取り消すことで、探索状態を正しく復元しています。これがバックトラッキングの核となる部分です。
• カードは4枚と固定されているため、組み合わせの総数は限られ、十分高速に動作します。