字母算术题（Letterometrics）Python求解代码优化求助

字母算术题（Letterometrics）是一种将每个字母匹配为唯一数字，使给定等式成立的谜题。例如SEND+MORE=MONEY，当O=0、M=1、Y=2、E=5、N=6、D=7、R=8、S=9时，等式9567+1085=10652成立。

需求说明 #

程序输入为一个字母算术题，等号左侧是两个数相加，右侧是结果数。需推导其解，注意数字不能以0开头，要求30秒内完成求解。

问题现状 #

已使用itertools.permutations实现求解，但执行时间波动极大（0.1秒至109秒），尝试切片优化后无明显效果，寻求可行的优化方案。

调试输入数据 #

• THERE+ARE=RISKS
• GREEN+ORANGE=COLORS
• ELVIS+PRESLEY=POSTERS
• DCLIX+DLXVI=MCCXXV
• COUPLE+COUPLE=QUARTET

现有基础实现代码 #

from itertools import permutations
 
s = input().replace('+', ' ').replace('=', ' ')
s2 = set(s.replace(' ', ''))
s = s.split(' ')
otv = -1
 
for i in permutations(range(10), len(s2)):
    y = dict(zip((list(s2)), i))
    if int(y[s[0][0]]) == 0 or int(y[s[1][0]]) == 0 or int(y[s[2][0]]) == 0:
        continue
    if int(''.join(map(str, [y.get(key) for key in s[0]])))+int(''.join(map(str, [y.get(key) for key in s[1]]))) == int(''.join(map(str, [y.get(key) for key in s[2]]))):
        otv = ' '.join('{} {}'.format(key, val) for key, val in sorted(y.items()))
        break
 
print(otv)

尝试优化的切片版本代码 #

from itertools import permutations
 
s = input().replace('+', ' ').replace('=', ' ')
s2 = list(set(s.replace(' ', '')))
s3 = list(s)
s = s.split(' ')
otv = -1
 
for i in permutations(range(10), len(s2)):
    if i[0] == 0 or i[s2.index(s[1][0])] == 0 or i[s2.index(s[2][0])] == 0:
        continue
    y = dict(zip(s2, i))
    zy = [str(y[i]) for i in s3 if i.isalpha()]
    if int(''.join(zy[:len(s[0])])) + int(''.join(zy[len(s[0]):len(s[0])+len(s[1])])) == int(''.join(zy[len(s[0])+len(s[1])])):
        otv = ' '.join('{} {}'.format(key, val) for key, val in sorted(y.items()))
        break
 print(otv)

内容的提问来源于stack exchange，提问作者Вадим Косарев