CSP easy

Problem Crypto Puzzle

In crypto-arithmetic problems, digits (values between 0 and 9) are represented by letters. Different letters stand for different digits, and different occurrences of the same letter denote the same digit. The problem is then represented as an arithmetic operation between words. The task is to find out which letter stands for which digit, so that the result of the given arithmetic operation is true.

Here are some examples of crypto puzzles:

   no           cross         donald
+  no        +  roads       + gerald
= yes        = danger       = robert

To build a CSP (Constraint Satisfaction Problem) model, we need first to import the library PyCSP$^3$:

from pycsp3 import *

Then, we need some data. Here, we choose a specific crypto puzzle (donald+gerald=robert). Note that the function alphabet_positions() returns a tuple composed of the positions in the Latin alphabet of all letters of a string passed as a parameter.

words = ["donald", "gerald", "robert"]
word1, word2, word3 = words
letters = set(alphabet_positions(word1 + word2 + word3))
n = len(word1)

We can check the value of these variables. In letters, we have the indexes of all involved characters in the three words.

print("Letters: ", letters)
print("n: ", n)

Letters:  {0, 1, 3, 4, 6, 11, 13, 14, 17, 19}
n:  6

We assume that the two first words have the same length, while the third one may be longer by one letter.

assert len(word2) == n and len(word3) in {n, n + 1}

We start our CSP model with an array $x$ of variables; for simplicity, the array contains 26 squares (for the 26 possible letters) but only some of them are considered as relevant: those corresponding to an involved letter index.

# x[i] is the value assigned to the ith letter (if present) of the alphabet
x = VarArray(size=26, dom=lambda i: range(10) if i in letters else None)

By printing the content of $x$, we can clearly see which variables are created.

print(x)

[x[0], x[1], None, x[3], x[4], None, x[6], None, None, None, None, x[11], None, x[13], x[14], None, None, x[17], None, x[19], None, None, None, None, None, None]

The domain of each variable is ${0,1,\dots,9}$. For example:

print(x[4].dom)

0..9

For simplicity, we build three auxiliary lists of variables corresponding to the letters of the three words. Note however that we do not build new variables in our model, as we simply copy the references of some of them.

# auxiliary lists of variables associated with the three words
x1, x2, x3 = [[x[i] for i in alphabet_positions(word)] for word in words]

This gives:

print(f"x1: {x1} \nx2: {x2} \nx3: {x3}")

x1: [x[3], x[14], x[13], x[0], x[11], x[3]] 
x2: [x[6], x[4], x[17], x[0], x[11], x[3]] 
x3: [x[17], x[14], x[1], x[4], x[17], x[19]]

Concerning the constraints, we first post a constraint AllDifferent.

satisfy(
    # all letters must be assigned different values
    AllDifferent(x)
);

Then, we want to avoid to have the most significant letters assigned to 0.

satisfy(
    x1[0] != 0, 
    x2[0] != 0, 
    x3[0] != 0
);

If we are curious, we can print the intern representation of the constraints that have been posted. Athough a little bit technical, one can see that we have one constraint AllDifferent and three constraints Intension (note that ‘ne’ stands for ‘not equal to’).

print(posted())

allDifferent(list:[x[0], x[1], x[3], x[4], x[6], x[11], x[13], x[14], x[17], x[19]])
intension(function:ne(x[3],0))
intension(function:ne(x[6],0))
intension(function:ne(x[17],0))

Interestingly, by calling the function solve(), we can check that the problem is satisfiable (SAT). We can also display the values of each word. Here, we call the function values() that collects the values assigned to a specified list of variables.

if solve() is SAT:
    print(" ", values(x1))
    print("+", values(x2))
    print("=", values(x3))

  [2, 7, 6, 0, 5, 2]
+ [4, 3, 8, 0, 5, 2]
= [8, 7, 1, 3, 8, 9]

Of course, the sum is not valid. The missing constraint can be written by calling the function Sum():

satisfy(
    # ensuring the crypto-arithmetic sum
    Sum((x1[-i-1] + x2[-i-1]) * 10 ** i for i in range(n))
      == Sum(x3[-i-1] * 10 ** i for i in range(len(x3)))
);

Because this expression is rather complex, one may want to control it. This is made easier by developping the last posted constraint (i.e., printing its internal representation). One can see that it corresponds to a weighted sum under the condition “= 0” (note that ‘eq’ stands for ‘equal to’). By calling posted(-1) we can get the constraint(s) that have been posted at the last call to satisfy().

print(posted(-1))

sum(list:[add(x[3],x[3]), add(x[11],x[11]), add(x[0],x[0]), add(x[13],x[17]), add(x[14],x[4]), add(x[3],x[6]), x[19], x[17], x[4], x[1], x[14], x[17]], coeffs:[1, 10, 100, 1000, 10000, 100000, -1, -10, -100, -1000, -10000, -100000], condition:(eq,0))

We can now obtain a valid solution.

if solve() is SAT:
    print(" ", values(x1))
    print("+", values(x2))
    print("=", values(x3))

  [5, 2, 6, 4, 8, 5]
+ [1, 9, 7, 4, 8, 5]
= [7, 2, 3, 9, 7, 0]

By the way, does there exist several solutions? We can check it as follows.

if solve(sols=ALL) is SAT:
    print("Number of solutions: ", n_solutions())

Number of solutions:  1

If you want to solve another puzzle, replace for example [“donald”, “gerald”, “robert”] by [“no”, “no”, “yes”] at the top of this page, and restart the jupyter kernel.

Finally, we give below the model in one piece. Here the data is expected to be given by the user (in a command line).

from pycsp3 import *

word1, word2, word3 = words = [w.lower() for w in data]
letters = set(alphabet_positions(word1 + word2 + word3))
n = len(word1) 

assert len(word2) == n and len(word3) in {n, n + 1}

# x[i] is the value assigned to the ith letter (if present) of the alphabet
x = VarArray(size=26, dom=lambda i: range(10) if i in letters else None)

# auxiliary lists of variables associated with the three words
x1, x2, x3 = [[x[i] for i in alphabet_positions(word)] for word in words]

satisfy(
    # all letters must be assigned different values
    AllDifferent(x),

    # the most significant letter of each word cannot be equal to 0
    [x1[0] != 0, x2[0] != 0, x3[0] != 0],

    # ensuring the crypto-arithmetic sum
    Sum((x1[-i-1] + x2[-i-1]) * 10 ** i for i in range(n))
      == Sum(x3[-i-1] * 10 ** i for i in range(len(x3)))
)