如何解决这个问题而不需要强加强制和/或需要大量的计算时间？

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，但是如果不作选择，它将收敛。

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是变量的数量。因此，对于这样的小问题，它几乎是即时的。