Python3：python3中的cryptarithmetic謎題通用解決方案

Question

我被這個問題聲明卡住了，我的代碼確實有效，但我使用了排列，這使得它非常緩慢，而且，我不知道如何使它對所有或任何輸入。我認爲我必須使用回溯，但我不使用如何在這裏使用它。

歡迎任何有價值的建議或建議或代碼。是的，這是一個任務，我不是要求完整的代碼。謝謝！

這裏是問題陳述：

替代不同數字（0，1，2，...，9），用於下面不同的字母，從而使相應的加成是正確的，並且將所得的MONEY值作爲大盡可能。什麼是價值？

SHOW ME + + THE = MONEY

有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()) 

Answer 1

我把你的solve2方法爲出發點，並實現了方程'word [+ word]*n = word'一個簡單的解析器。函數get_value在用所有字母替換其相關數字後計算得到的整數值。其餘的就像你所做的那樣排列組合，並將左邊的單詞和右邊的單詞進行比較。

下面的代碼：

import itertools 


def get_value(word, substitution): 
    s = 0 
    factor = 1 
    for letter in reversed(word): 
     s += factor * substitution[letter] 
     factor *= 10 
    return s 


def solve2(equation): 
    # split equation in left and right 
    left, right = equation.lower().replace(' ', '').split('=') 
    # split words in left part 
    left = left.split('+') 
    # create list of used letters 
    letters = set(right) 
    for word in left: 
     for letter in word: 
      letters.add(letter) 
    letters = list(letters) 

    digits = range(10) 
    for perm in itertools.permutations(digits, len(letters)): 
     sol = dict(zip(letters, perm)) 

     if sum(get_value(word, sol) for word in left) == get_value(right, sol): 
      print(' + '.join(str(get_value(word, sol)) for word in left) + " = {} (mapping: {})".format(get_value(right, sol), sol)) 

if __name__ == '__main__': 
    solve2('SEND + MORE = MONEY') 

如果你只在恰當的字眼最大值感興趣的話，您可以更改排列，它與恰當的字眼最高的號碼（如98765的開始MONEY），然後一個一個下去，直到找到第一場比賽。

回溯

OK，這個想法在這裏將是一個以建立一個替代和檢查方程每個步驟之間得到滿足。

For example: 
1. set S = 9 
2. check if equation can be fulfilled: 
    2.1. if yes: set a value for the next letter and go to 2 
    2.2. if no: select next value for S 

在這種情況下，檢查方程是否可以滿足並不那麼容易。

我會嘗試以下方法：

分鐘：最小值在範圍（10），其尚未被用於替代迄今

最大：在範圍（10）的最大值具有不是已用於替代目前爲止

用最小/最大值代替到目前爲止還沒有被替換的左側的每個字母，並且在用最大/最小值代替之後將該和與右側的編號進行比較。

Example: 
equation = 'SEND + MORE = MONEY' 
1. substitute M = 2 
2. check: 
    max = 9, min = 0 
    compare max on left side with min on right side: 9999 + 2999 = 20000 
    compare min on left side with max on right side: 0000 + 2000 = 29999 
    if max_left < min_right or min_left > max_right: 
     the current chosen substitutions (M = 2 in this example) can not lead to a valid solution. 

你明白了嗎？