如何加速求解字母代数字等式WHITE+WATER=PICNIC的Python代码？

问题背景 #

需解决数学竞赛中的字母数字谜题：WHITE + WATER = PICNIC，规则为不同字母代表不同数字，求PICNIC对应的数字。原代码通过全量遍历10^10种数字组合求解，速度过慢无法满足竞赛时间要求，需优化。

原代码如下：

from tqdm import tqdm

def find_solution():
    for W in tqdm(range(10)):
        for H in tqdm(range(10), desc='H'):
            for I in tqdm(range(10), desc='I'):
                for T in tqdm(range(10)):
                    for E in tqdm(range(10)):
                        for A in (range(10)):
                            for R in (range(10)):
                                for P in (range(1, 10)): # P cannot be 0
                                    for C in (range(10)):
                                        for N in (range(10)):
                                            white = W * 10000 + H * 1000 + I * 100 + T * 10 + E
                                            water = W * 10000 + A * 1000 + T * 100 + E * 10 + R
                                            picnic = P * 100000 + I * 10000 + C * 1000 + N * 100 + I * 10 + C

                                            if white + water == picnic:
                                                return {'W': W, 'H': H, 'I': I, 'T': T, 'E': E, 'A': A, 'R': R, 'P': P, 'C': C, 'N': N}

    return None

solution = find_solution()

if solution:
    print("Solution found:")
    print(solution)
else:
    print("No solution found.")

优化思路 #

1. 利用加法特性固定关键变量 #

两个5位数相加的最大值为99999 + 99999 = 199998，因此结果的首位P必然是1，直接固定P=1，无需遍历该变量。

2. 逐位拆解加法竖式，推导约束等式 #

将加法拆解为从右到左的竖式计算（c0~c4为每一位的进位，仅取0或1）：

W H I T E
+   W A T E R
= 1 I C N I C

对应每一位的约束等式：

• 个位：E + R = C + 10*c0
• 十位：T + E + c0 = I + 10*c1
• 百位：I + T + c1 = N + 10*c2
• 千位：H + A + c2 = C + 10*c3
• 万位：W + W + c3 = I + 10*1（因为十万位进位c4=1）

3. 减少遍历维度，通过等式推导变量 #

基于上述等式，只需遍历部分变量和进位值，其余变量通过等式直接计算，同时提前过滤数字越界、重复的组合，避免无效计算。

优化后的代码 #

def find_solution():
    # 固定P=1，两个5位数相加最大为199998
    P = 1
    # 遍历所有可能的进位（仅0或1）
    for c0 in [0, 1]:
        for c1 in [0, 1]:
            for c2 in [0, 1]:
                for c3 in [0, 1]:
                    # 从万位等式推导W的范围：2W + c3 = I +10 → W≥(10 -c3)//2
                    for W in range((10 - c3) // 2, 10):
                        I = 2 * W + c3 - 10
                        if I < 0 or I > 9:
                            continue
                        # 遍历E和T，验证十位等式
                        for E in range(10):
                            for T in range(10):
                                if T != I + 10*c1 - E - c0:
                                    continue
                                # 遍历R，推导C并验证个位等式
                                for R in range(10):
                                    C = E + R - 10*c0
                                    if C < 0 or C > 9:
                                        continue
                                    # 遍历H，推导A并验证千位等式
                                    for H in range(10):
                                        A = C + 10*c3 - H - c2
                                        if A < 0 or A > 9:
                                            continue
                                        # 推导N并验证百位等式
                                        N = I + T + c1 - 10*c2
                                        if N < 0 or N > 9:
                                            continue
                                        # 检查所有数字是否唯一
                                        digits = [W, H, I, T, E, A, R, P, C, N]
                                        if len(set(digits)) != 10:
                                            continue
                                        # 最终验证等式（双重保险）
                                        white = W*10000 + H*1000 + I*100 + T*10 + E
                                        water = W*10000 + A*1000 + T*100 + E*10 + R
                                        picnic = P*100000 + I*10000 + C*1000 + N*100 + I*10 + C
                                        if white + water == picnic:
                                            return {
                                                'W': W, 'H': H, 'I': I, 'T': T, 'E': E,
                                                'A': A, 'R': R, 'P': P, 'C': C, 'N': N,
                                                'PICNIC': picnic
                                            }
    return None

solution = find_solution()
if solution:
    print("找到解：")
    print(f"字母对应数字：{ {k:v for k,v in solution.items() if k!='PICNIC'} }")
    print(f"PICNIC对应的数字：{solution['PICNIC']}")
else:
    print("未找到解")

优化效果说明 #

原代码需遍历10^10次，优化后通过固定关键变量、利用约束等式推导，遍历次数骤降至约8万次，运行速度提升几个数量级，完全满足竞赛时间要求。

内容的提问来源于stack exchange，提问作者Lucien Jaccon