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

Name: NITHYA T

Register Number: 2305001023

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

---

Sample Input and Output:

SEND = 9567
MORE = 1085

---

MONEY = 10652

PROGRAM

from itertools import permutations

def solve_cryptarithmetic():
    letters = ('T', 'H', 'I', 'S', 'A', 'R', 'D')
    for perm in permutations(range(10), len(letters)):
        T, H, I, S, A, R, D = perm

        # Leading letters cannot be zero
        if T == 0 or H == 0:
            continue

        THIS = 1000 * T + 100 * H + 10 * I + S
        IS = 10 * I + S
        HARD = 1000 * H + 100 * A + 10 * R + D

        if THIS + IS == HARD:
            return THIS, IS, HARD, {'T':T, 'H':H, 'I':I, 'S':S, 'A':A, 'R':R, 'D':D}

    return None

solution = solve_cryptarithmetic()

if solution:
    THIS, IS, HARD, mapping = solution
    print("Mapping:", mapping)
    print(f"THIS = {THIS}")
    print(f"IS   = {IS}")
    print(f"HARD = {HARD}")
else:
    print("No solution found.")

OUTPUT

---

Result:

Thus a Cryptarithmetic Problem was solved using Python successfully.