python - Python 3 での暗号算術パズルの汎用ソリューション

Question

私はこの問題の声明で立ち往生しています。私のコードは機能しますが、使用itertools.permutationsしたため、非常に遅くなります。さらに、すべてまたは任意の入力に対して汎用にする方法がわかりません。バックトラッキングを使用する必要があると思いますが、ここでの使用方法は使用していません。

貴重な提案、アドバイス、またはコードは大歓迎です。はい、これは割り当てであり、コード全体を求めているわけではありません。ありがとう！

問題文は次のとおりです。

以下の異なる文字を異なる数字 (0、1、2、..、9) に置き換えて、対応する加算が正しく、MONEY の結果の値ができるだけ大きくなるようにします。値は何ですか？

SHOW + ME + THE = お金

方程式を満たす 3 つの解があります: 10376、10267、10265。したがって、正しい解は (最大の) 10376 です。同じ最大値に評価される複数のマッピングがある場合は、それらすべてを出力します。

課題:

この種の問題の正しい解決策を常に見つけることができるプログラムを Python で作成します。

import time
import itertools


def timeit(fn):
    def wrapper():
        start = time.clock()
        ret = fn()
        elapsed = time.clock() - start
        print("%s took %2.fs" % (fn.__name__, elapsed))
        return ret
    return wrapper


@timeit
def solve1():
    for s in range(1, 10):
        for e in range(0, 10):
            for n in range(0, 10):
                for d in range(0, 10):
                    for m in range(1, 10):
                        for o in range(0, 10):
                            for r in range(0, 10):
                                for y in range(0, 10):
                                    if distinct(s, e, n, d, m, o, r, y):
                                        send = 1000 * s + 100 * e + 10 * n + d
                                        more = 1000 * m + 100 * o + 10 * r + e
                                        money = 10000 * m + 1000 * o + 100 * n + 10 * e + y
                                        if send + more == money:
                                            return send, more, money


def distinct(*args):
    return len(set(args)) == len(args)


@timeit
def solve2():
    #letters = input("Enter your string: ")
    #letters1 = list(letters)
    letters = ('s', 'h', 'o', 'w', 'm', 'e', 't')
    digits = range(10)
    for perm in itertools.permutations(digits, len(letters)):
        sol = dict(zip(letters, perm))
        if sol['s'] == 0 or sol['m'] == 0:
            continue
        send = 1000 * sol['s'] + 100 * sol['e'] + 10 * sol['n'] + sol['d']
        more = 1000 * sol['m'] + 100 * sol['o'] + 10 * sol['r'] + sol['e']
        money = 10000 * sol['m'] + 1000 * sol['o'] + 100 * sol['n'] + 10 * sol['e'] + sol['y']
        if send + more == money:
            return send, more, money


print(solve1())
print(solve2())