The 24 Game Algorithm using Depth First Search

You have 4 cards each containing a number from 1 to 9. You need to judge whether they could operated through *, /, +, -, (, ) to get the value of 24.

Example 1:
Input: [4, 1, 8, 7]
Output: True
Explanation: (8-4) * (7-1) = 24

Example 2:
Input: [1, 2, 1, 2]
Output: False

Note:
The division operator / represents real division, not integer division. For example, 4 / (1 – 2/3) = 12.
Every operation done is between two numbers. In particular, we cannot use – as a unary operator. For example, with [1, 1, 1, 1] as input, the expression -1 – 1 – 1 – 1 is not allowed.

You cannot concatenate numbers together. For example, if the input is [1, 2, 1, 2], we cannot write this as 12 + 12.

In 24 Point Poker Game Calculator, the complete list of the 24-game solutions has been implemented using PHP, via the bruteforce algorithm by iterating all possible solutions (which might contain duplicates such as communitive laws a+b=b+a).

Simple Depth First Search Algorithm to Check if 4 cards can make up to 24

As there are only four numbers, and four operators which are addition, subtraction, multiplication and divisor, the total solution space is constant.

The Depth First Search Algorithm will operate on a vector. The algorithm will bruteforce all pairs of the numbers in the vector, and apply four operators on these two numbers, push the result to the vector, and recursively calling itself until there is only 1 number in the vector – which we can easily check if it is 24 – remember, the types in the vector should be double i.e. converting the input integers to the doubles first.

As multiplication and additions are communitive so that we can slightly speed the process up by ignoring the pairs by comparing the indices.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

class Solution {
public:
    bool judgePoint24(vector<int>& nums) {
        vector<double> arr;
        for (const auto &n: nums) {
            arr.push_back(n);
        }
        return search(arr);
    }
    
private:
    bool search(vector<double>& nums) {
        if (nums.empty()) return false;
        if (nums.size() == 1) return abs(nums[0] - 24) < 1e-6;        
        for (int i = 0; i < nums.size(); ++ i) {
            for (int j = 0; j < nums.size(); ++ j) {
                if (i == j) continue;
                vector<double> nums2;
                for (int k = 0; k < nums.size(); ++ k) {
                    if (k != i && k != j) {
                        nums2.push_back(nums[k]);
                    }
                }
                for (int k = 0; k < 4; ++ k) {
                    if ((k < 2) && (j > i)) continue; // ignoring communitive additions and multiplication
                    switch (k) {
                        case 0: nums2.push_back(nums[i] + nums[j]); break;
                        case 1: nums2.push_back(nums[i] * nums[j]); break;
                        case 2: nums2.push_back(nums[i] - nums[j]); break;
                        case 3: 
                            if (nums[j] != 0) {
                                nums2.push_back(nums[i] / nums[j]); 
                            } else {
                                continue;    
                            }
                            break;                            
                    }
                    if (search(nums2)) return true;
                    nums2.pop_back();                    
                }
            }
        }
        return false;
    }
};

class Solution {
public:
    bool judgePoint24(vector<int>& nums) {
        vector<double> arr;
        for (const auto &n: nums) {
            arr.push_back(n);
        }
        return search(arr);
    }
    
private:
    bool search(vector<double>& nums) {
        if (nums.empty()) return false;
        if (nums.size() == 1) return abs(nums[0] - 24) < 1e-6;        
        for (int i = 0; i < nums.size(); ++ i) {
            for (int j = 0; j < nums.size(); ++ j) {
                if (i == j) continue;
                vector<double> nums2;
                for (int k = 0; k < nums.size(); ++ k) {
                    if (k != i && k != j) {
                        nums2.push_back(nums[k]);
                    }
                }
                for (int k = 0; k < 4; ++ k) {
                    if ((k < 2) && (j > i)) continue; // ignoring communitive additions and multiplication
                    switch (k) {
                        case 0: nums2.push_back(nums[i] + nums[j]); break;
                        case 1: nums2.push_back(nums[i] * nums[j]); break;
                        case 2: nums2.push_back(nums[i] - nums[j]); break;
                        case 3: 
                            if (nums[j] != 0) {
                                nums2.push_back(nums[i] / nums[j]); 
                            } else {
                                continue;    
                            }
                            break;                            
                    }
                    if (search(nums2)) return true;
                    nums2.pop_back();                    
                }
            }
        }
        return false;
    }
};

Special case has to be handled when checking the divisor being zero. The complexity of the algorithm is O(1) an the space complexity is also O(1) as they both do not grow as the size of the problem grows.

Remember to play at: 24 Point Poker Game Calculator

–EOF (The Ultimate Computing & Technology Blog) —