Home » Machine Learning/Artificial Intelligence

Crypt-Arithmetic Problem - A type of Constraint Satisfactory Problem in Artificial Intelligence

This article is about the Crypt-Arithmetic Problem which is a type of Constraint Satisfactory problem in Artificial Intelligence. In this article, we are going to study about what the problem is, what set of constraints it follows and how the agent finds the solution to the problem while keeping all the constraints satisfied?
Submitted by Monika Sharma, on June 02, 2019

Crypt-Arithmetic Problem

The Crypt-Arithmetic problem in Artificial Intelligence is a type of encryption problem in which the written message in an alphabetical form which is easily readable and understandable is converted into a numeric form which is neither easily readable nor understandable. In simpler words, the crypt-arithmetic problem deals with the converting of the message from the readable plain text to the non-readable ciphertext. The constraints which this problem follows during the conversion is as follows:

1. A number 0-9 is assigned to a particular alphabet.
2. Each different alphabet has a unique number.
3. All the same, alphabets have the same numbers.
4. The numbers should satisfy all the operations that any normal number does.

Let us take an example of the message: SEND MORE MONEY.

Here, to convert it into numeric form, we first split each word separately and represent it as follows:

    S E N D
    M O R E
    -------------
    M O N E Y

These alphabets then are replaced by numbers such that all the constraints are satisfied. So initially we have all blank spaces.

These alphabets then are replaced by numbers such that all the constraints are satisfied. So initially we have all blank spaces.

We first look for the MSB in the last word which is 'M' in the word 'MONEY' here. It is the letter which is generated by carrying. So, carry generated can be only one. SO, we have M=1.

Now, we have S+M=O in the second column from the left side. Here M=1. Therefore, we have, S+1=O. So, we need a number for S such that it generates a carry when added with 1. And such a number is 9. Therefore, we have S=9 and O=0.

Now, in the next column from the same side we have E+O=N. Here we have O=0. Which means E+0=N which is not possible. This means a carry was generated by the lower place digits. So we have:

1+E=N ----------(i)

Next alphabets that we have are N+R=E -------(ii)

So, for satisfying both equations (i) and (ii), we get E=5 and N=6.

Now, R should be 9, but 9 is already assigned to S, So, R=8 and we have 1 as a carry which is generated from the lower place digits.

Now, we have D+5=Y and this should generate a carry. Therefore, D should be greater than 4. As 5, 6, 8 and 9 are already assigned, we have D=7 and therefore Y=2.

Therefore, the solution to the given Crypt-Arithmetic problem is:

S=9; E=5; N=6; D=7; M=1; O=0; R=8; Y=2

Which can be shown in layout form as:

      9 5 6 7
      1 0 8 5
    -------------
    1 0 6 5 2
    --------------

---