运行在解决 Python 中的 CryptArithmetic Problem 时陷入无限循环

Question

我正在解决 LeetCode 的问题，https://leetcode.com/problems/verbal-arithmetic-puzzle/ 使用回溯。

这与 CryptArithmetic 问题相同，所以我将简要说明问题的具体内容。

class Solution:
    def isSolvable(self,words, result):
        characterMap={}
        uniqueString=""

        for word in words:
            for letter in word:
                if letter not in characterMap:
                    uniqueString+=letter
                    characterMap[letter]=-1
        
        for r in result:
            if r not in characterMap:
                uniqueString+=r
                characterMap[r]=-1
        
                
        self.words=words
        self.result=result
        self.uniqueString=uniqueString
        self.characterMap=characterMap
        self.usedDigit={i:False for i in range(10)}

        
        return self.isSolvableHelper(0)
    
    def getSum(self, word):
        sums=""
        for w in word:
            sums+=str(self.characterMap[w])
        
        return int(sums)
    
    def isSolvableHelper(self, idx):
        if(idx==len(self.uniqueString)):
            sumUp=0
            for w in self.words:
                sumUp+=self.getSum(w)
            
            resultSum=self.getSum(self.result)
            
            return True if(resultSum==sumUp) else False
        
        char=self.uniqueString[idx]
        for i in range(10):
            if(not self.usedDigit[i]):
                self.characterMap[char]=i
                self.usedDigit[i]=True
                self.isSolvableHelper(idx+1)
                self.usedDigit[i]=False
                self.characterMap[char]=-1

sol=Solution()
sol.isSolvable(['SEND','MORE'], "MONEY")

我考虑了与输入相同的示例，其中单词 array/list = ["SEND", "MORE"] 结果为 MONEY

我运行进入了一个无限循环，我不确定这是在哪里发生的，我怀疑它可能是回溯开始的地方这是输出，它只是运行ning

你能帮我看看我的逻辑哪里出了问题吗？

Answer 1

当你找到解决方案时，你永远不会 return 正确：在 isSolvableHelper 中：

            for i in range(10):
                if(not self.usedDigit[i]):
                    self.characterMap[char]=i
                    self.usedDigit[i]=True
                    # in the next line you do not test the returned value, so you do not know when you have finished
                    self.isSolvableHelper(idx+1)
                    self.usedDigit[i]=False
                    self.characterMap[char]=-1

添加测试：

            for i in range(10):
                if(not self.usedDigit[i]):
                    self.characterMap[char]=i
                    self.usedDigit[i]=True
                    If  self.isSolvableHelper(idx+1):
                        return True
                    self.usedDigit[i]=False
                    self.characterMap[char]=-1
            # Do not forget to return False 
            return False

您还可以通过仅使用整数来优化 getSum :

    def getSum(self, word):
        #print("getSum({})".format(word))
        sums=0
        for w in word:
            sums = 10 * sums + self.characterMap[w]
    
        return sums

一些结果：（一个循环 = isSolvableHelper 中的一个条目）

SEND MORE = MONEY
Char map : {'E': 8, 'D': 7, 'M': 0, 'O': 3, 'N': 1, 'S': 2, 'R': 6, 'Y': 5}
nb loop : 730250

SIX SEVEN SEVEN = TWENTY
Char Mao : {'E': 8, 'I': 5, 'N': 2, 'S': 6, 'T': 1, 'W': 3, 'V': 7, 'Y': 4, 'X': 0}
nb loop : 4094645

THIS IS TOO = FUNNY
Char map : {'F': 0, 'I': 8, 'H': 6, 'O': 5, 'N': 1, 'S': 2, 'U': 4, 'T': 3, 'Y': 9}
nb loop : 2272068

LEET CODE = POINT
no char map
nb loop : 6235301

运行在解决 Python 中的 CryptArithmetic Problem 时陷入无限循环

Running into an infinite loop while solving CryptArithmetic Problem in Python

python

recursion

backtracking

运行 在解决 Python 中的 CryptArithmetic Problem 时陷入无限循环

Running into an infinite loop while solving CryptArithmetic Problem in Python

python

recursion

backtracking

运行在解决 Python 中的 CryptArithmetic Problem 时陷入无限循环