sendmoremoney.py

# /greatswercporto
def check_back(exp, assgn, carry):
    try:
        d = carry
        for i in exp[:-1]:
            if i:
                d += assgn[i[-1]]
        e = assgn[exp[-1][-1]]
        return (d % 10 == e % 10, d//10)
    except:
        return False

def backtrack(exp, domains, assgn, carry=0):
    for i in leads:
        if i in assgn and assgn[i] == 0:
            return
    if not any(exp) and carry == 0:
        mem.add(tuple(sorted(assgn.items())))
        return
    t = check_back(exp, assgn, carry)
    if not (type(t) == tuple and not t[0]):
        if t != False:
            exp = list(map(lambda x: x[:-1], exp))
            carry = t[1]
            if not any(exp[:-1]) and exp[-1] and carry:
                if exp[-1][-1] in assgn and assgn[exp[-1][-1]] == carry:
                    mem.add(tuple(sorted(assgn.items())))
                    return
                if exp[-1][-1] not in assgn and carry in domains:
                    mem.add(tuple(sorted(list(assgn.items()) + [(exp[-1][-1], carry)])))
                    return
        if not any(exp) and not carry:
            mem.add(tuple(sorted(assgn.items())))
            return
        rec = False
        for i in {i[-1] for i in exp if i}:
            if i not in assgn:
                rec = True
                for domain in sorted(domains):
                    assgn[i] = domain
                    domains -= {assgn[i]}
                    backtrack(exp, domains, assgn, carry)
                    domains.add(assgn[i])
                    del assgn[i]
                break
        if t != False and not rec:
            backtrack(exp, domains, assgn, carry)
    return

l, r = input().split('='); a, b = l.split('+'); letters = {*a, *b, *r}; exp = ([*a], [*b], [*r]); mem = set()
leads = {i[0] for i in exp}; backtrack(exp, set(range(10)), {})
if not mem: print('impossible'), exit(0)
asg = dict(min(mem))
for i in exp:
    for j in range(len(i)):
        try: i[j] = str(asg[i[j]])
        except: print('impossible'), exit(0)
print(''.join(exp[0])+'+'+''.join(exp[1])+'='+''.join(exp[2]))