python - 如何在不强制和/或花费大量计算时间的情况下解决这个问题？

Question

我正在尝试解决以下问题:

A store sells large individual wooden letters for signs to put on houses. 
The letters are priced individually.
The total cost of letters in LOAN is 17 dollars.
The total cost of letters in SAM is 18 dollars.
The total cost of letters in ANNA is 20 dollars.
The total cost of letters in ROLLO is 21 dollars.
The total cost of letters in DAMAGES is 30 dollars.
The total cost of letters in SALMON is 33 dollars.

How much would the letters in the name GARDNER cost?

我正在使用以下 python 代码暴力破解字母成本，但它需要数小时才能收敛，因为它们有 33^10 种可能的组合需要测试。我使用 n=33，因为它是名称的最大成本，但实际上，n 可以减少到 15 甚至 10，但如果不是 sur，它将收敛。

def func(letters):
    print letters
    if letters['L']+letters['O']+letters['A']+letters['N'] != 17:
        return False
    elif letters['S']+letters['A']+letters['M'] != 18:
        return False
    elif 2*letters['A']+2*letters['N'] != 20:
        return False
    elif letters['R']+2*letters['O']+2*letters['L'] != 21:
        return False
    elif letters['D']+2*letters['A']+letters['M']+letters['G']+letters['E']+letters['S'] != 30:
        return False
    elif letters['S']+letters['A']+letters['L']+letters['M']+letters['O']+letters['N'] != 33:
        return False
    return True

def run(letters, n, forbidden_letters):
    for letter in letters.keys():
        if letter not in forbidden_letters:
            for i in range(1, n):
                letters[letter] = i
                if not func(letters):
                    if letter not in forbidden_letters:
                        forbidden_letters+=letter
                    if run(letters, n, forbidden_letters):
                        return letters
                else:
                    return letters

LETTERS = {
    "L":1,
    "O":1,
    "A":1,
    "N":1,
    "S":1,
    "M":1,
    "R":1,
    "D":1,
    "G":1,
    "E":1,
}
n=33
print run(LETTERS, n, "")

暴力破解最终会奏效，但它占用大量 CPU，因此肯定不是最佳解决方案。

有没有人有更好的方案来解决这个问题？要么通过减少计算时间，要么通过良好的数学方法。

谢谢大家。

Answer 1

这就是所谓的线性方程组。如果需要，您可以手动求解，但也可以使用线性求解器。例如 sympy

import sympy

l,o,a,n,s,m,r,d,g,e = sympy.symbols('l,o,a,n,s,m,r,d,g,e')

eq1 = l+o+a+n - 17
eq2 = s+a+m -18
eq3 = a+n+n+a -20
eq4 = r+o+l+l+o -21 
eq5 = d+a+m+a+g+e+s -30
eq6 = s+a+l+m+o+n- 33

sol, = sympy.linsolve([eq1,eq2,eq3,eq4,eq5,eq6],(l,o,a,n,s,m,r,d,g,e))
l,o,a,n,s,m,r,d,g,e = sol

print(g+a+r+d+n+e+r)

线性方程的求解速度非常快。复杂度为 O(n³)，其中 n 是变量的数量。所以对于像这样的小问题，它几乎是即时的。