Running into an infinite loop while solving CryptArithmetic Problem in Python

Question

I am solving a problem from LeetCode, https://leetcode.com/problems/verbal-arithmetic-puzzle/ using Backtracking.

This is the same as CryptArithmetic problem, so I will explain in short what the problem exactly is.

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")

I have considered the same example as input where the words array/list = ["SEND", "MORE"] and the result is MONEY

I run into an inifinite loop not sure where this happens, I suspect that its probably the block where the backtracking begins This is the output, it just goes on running

can you help me to know whats the mistake in my logic here.

Answer 1

You never return True when you find a solution : in 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

Add a test :

            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

You can also optimise getSum by using only integers :

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

Some results : (one loop = one entry in 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