题解 | 24点游戏算法

import sys

arr = list(map(int, input().split()))

N = 4
visit = []
st = []
path = []
def dfs(l, res):
    # if len(path)==4:
        # if path[0][0] == 0 and path[1][0]==1 and path[2][0]==2 or path[3][0]==3:
        #     print(path)
    if l==4 and (abs(res - 24) < 1e-4):
        # print(path, res)
        return True
    # 特殊处理情况:剩下两个数乘除运算后于当前相加减，或者剩下两个数加减后于当前相乘除情况
    if l==2:
        num_remain = [arr[i] for i in range(N) if not visit[i]]
        wait_res1 = [num_remain[0] * num_remain[1], num_remain[1] / num_remain[0], num_remain[0] / num_remain[1]]
        wait_res2 = [num_remain[0] + num_remain[1], num_remain[0] - num_remain[1], num_remain[1] - num_remain[0]]
        for w in wait_res1:
            if abs(res + w - 24)<1E-5 or abs(res - w - 24)<1E-5 or abs(-res + w - 24)<1E-5:
                return True
        for w in wait_res2:
            if abs(res * w - 24)<1E-5 or (w !=0 and abs(res / w - 24)<1E-5) or (res!=0 and abs(w/res - 24)<1E-5):
                return True


    # 此处循环未包含剩下两个数乘除运算后于当前相加减情况，或者剩下两个数加减后于当前相乘除情况
    for i in range(N):
        if not visit[i]:
            visit[i] = True
            
            path.append((i, res + arr[i]))
            if dfs(l+1, res + arr[i]):
                return True
            path.pop()
            path.append((i, res - arr[i]))
            if dfs(l+1, res - arr[i]):
                return True
            path.pop()
            path.append((i, arr[i] - res))
            if dfs(l+1, arr[i] - res):
                return True
            path.pop()
            path.append((i, res * arr[i]))
            if dfs(l+1, res * arr[i]):
                return True
            path.pop()
            if arr[i]!=0:
                path.append((i, res / arr[i]))
                if dfs(l+1, res / arr[i]):
                    return True
                path.pop()
            if res !=0:
                path.append((i, arr[i] / res))
                if dfs(l+1, arr[i] / res):
                    return True
                path.pop()
            visit[i] = False
    return False
for i in range(N):
    # 各个元素作为起始点
    visit = [False for _ in range(N)]
    path=[(i, arr[i])]
    visit[i] = True
    if dfs(1, arr[i]):
        print("true")
        exit(0)

print("false")

如果不在代码中交换已求和部分和剩余未求和部分的顺序，对于4个元素的情况，DFS会漏掉前两个和后两个元素各自计算的结果再次运算。因此我在代码中手动加入了这个特殊情形。看到有些代码样例将求和的结果和未运算的结果放在一起用于dfs下一步的数组，这种方法可以应对任意长度的数组，而不受限于4个元素的情况。