ExpNo 8 : Solve Cryptarithmetic Problem,a CSP(Constraint Satisfaction Problem) using Python

Name: Sanchita Sandeep

Register Number/Staff Id: 212224240142

Aim:

To solve Cryptarithmetic Problem,a CSP(Constraint Satisfaction Problem) using Python

Procedure:

Input and Output
Input: This algorithm will take three words.
B A S E
B A L L
----------
G A M E S

Output: It will show which letter holds which number from 0 – 9. For this case it is like this.

          B A S E                         2 4 6 1
          B A L L                         2 4 5 5
         ---------                       ---------
        G A M E S                       0 4 9 1 6

Algorithm For this problem, we will define a node, which contains a letter and its corresponding values.

isValid(nodeList, count, word1, word2, word3)

Input − A list of nodes, the number of elements in the node list and three words.

Output − True if the sum of the value for word1 and word2 is same as word3 value.

Begin
m := 1
for each letter i from right to left of word1, do
ch := word1[i]
for all elements j in the nodeList, do
if nodeList[j].letter = ch, then
break
done
val1 := val1 + (m * nodeList[j].value)
m := m * 10
done

m := 1
for each letter i from right to left of word2, do
ch := word2[i]
for all elements j in the nodeList, do
if nodeList[j].letter = ch, then
break
done

  val2 := val2 + (m * nodeList[j].value)
  m := m * 10

done

m := 1
for each letter i from right to left of word3, do
ch := word3[i]
for all elements j in the nodeList, do
if nodeList[j].letter = ch, then
break
done

  val3 := val3 + (m * nodeList[j].value)
  m := m * 10

done

if val3 = (val1 + val2), then
return true
return false
End

Program:

from itertools import permutations

def solve_cryptarithmetic(word1, word2, result):
    letters = set(word1 + word2 + result)
    if len(letters) > 10:
        return None
    
    first_letters = set([word1[0], word2[0], result[0]])
    
    for perm in permutations(range(10), len(letters)):
        mapping = dict(zip(letters, perm))
        
        if any(mapping[first] == 0 for first in first_letters):
            continue
            
        num1 = sum(mapping[ch] * (10 ** i) for i, ch in enumerate(word1[::-1]))
        num2 = sum(mapping[ch] * (10 ** i) for i, ch in enumerate(word2[::-1]))
        num3 = sum(mapping[ch] * (10 ** i) for i, ch in enumerate(result[::-1]))
        
        if num1 + num2 == num3:
            return mapping, num1, num2, num3
    
    return None

def print_solution(word1, word2, result, mapping, num1, num2, num3):
    print(f"{word1:>10} = {num1}")
    print(f"{word2:>10} = {num2}")
    print(f"{'':>10}---")
    print(f"{result:>10} = {num3}")
    print("\nLetter to Number Mapping:")
    for letter, number in sorted(mapping.items()):
        print(f"{letter} = {number}")

if __name__ == "__main__":
    word1 = "SEND"
    word2 = "MORE"
    result = "MONEY"
    
    solution = solve_cryptarithmetic(word1, word2, result)
    
    if solution:
        mapping, num1, num2, num3 = solution
        print_solution(word1, word2, result, mapping, num1, num2, num3)
    else:
        print("No solution found")

---

Sample Input and Output:

SEND = 9567
MORE = 1085

---

MONEY = 10652

---

Output:

Result:

Thus a Cryptarithmetic Problem was solved using Python successfully.