Scribd
Upload
100 views

Cryptarithmetic Puzzle

This document describes a cryptarithmetic puzzle involving the addition of SATURN and URANUS equaling JUPITER. It defines the puzzle as a constraint satisfaction problem by defining the variables (letters) and their domains (possible digit values 0-9), and the constraints on the variables. It then shows the step-by-step solution, determining the values of each letter that satisfies all the constraints, resulting in the solution: P=0, J=1, E=2, T=3, A=4, U=5, R=6, N=7, I=8, S=9.

Uploaded by

Sihem Belabbes - IUT Montreuil
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
100 views

Cryptarithmetic Puzzle

This document describes a cryptarithmetic puzzle involving the addition of SATURN and URANUS equaling JUPITER. It defines the puzzle as a constraint satisfaction problem by defining the variables (letters) and their domains (possible digit values 0-9), and the constraints on the variables. It then shows the step-by-step solution, determining the values of each letter that satisfies all the constraints, resulting in the solution: P=0, J=1, E=2, T=3, A=4, U=5, R=6, N=7, I=8, S=9.

Uploaded by

Sihem Belabbes - IUT Montreuil
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 2

A cryptarithmetic problem

Consider the following cryptarithmetic puzzle:


SATURN + URANUS = JUPITER
Each letter represents a specific digit and each digit can only be represented by a
specific letter.

1. Re-write the puzzle in terms of a Constraint Satisfaction Problem (CSP) by

- Defining the variables and their domains, and


- Defining the constraints on the variables.

2. Provide the solution to this cryptarithmetic puzzle.

Solution
We have the following constraints:

N +S = R + 10C1 (1)
R + U + C1 = E + 10C2 (2)
U + N + C2 = T + 10C3 (3)
T + A + C3 = I + 10C4 (4)
A + R + C4 = P + 10C5 (5)
S + U + C5 = U + 10C6 (6)
C6 = J (7)
S 6= 0 (8)
U 6= 0 (9)
J 6= 0 (10)

Constraints (8), (9) and (10) represent the fact that the first letter of a word cannot be
0.

Constraints (7) and (10):


C6 = J = 1 .
Constraint (6):
S + U + C5 = U + 10 =⇒ S + C5 = 10. Since S ≤ 9 we have C5 = 1 . So S = 9 .
Constraint (1):
Alldiff(N, S, R), thus N 6= 0, thus N ≥ 2.
From S = 9 and N ≥ 2, we have C1 = 1 . Thus N + 9 = R + 10, thus N = R + 1.
Since N ≥ 2 and R 6= 1, it follows that R ≥ 2 and N ≥ 3.
Since N ≤ 8, R ≤ 7.
So we have DR = {2, 3, 4, 5, 6, 7} and DN = {3, 4, 5, 6, 7, 8}.
Constraints (2) and (3):
Assume C2 = 0:
R+U +1 = E (20 )
U +N = T + 10C3 (30 )
Replace N = R + 1 in (20 ), thus U + N = E. From (30 ) we get E = T + 10C3 . Impossible
no matter whether C3 = 0 or C3 = 1.

1
We conclude that C2 6= 0, thus C2 = 1 . Replace N = R + 1 in constraints (2) and (3):

U +N = E + 10 (200 )
U + N + 1 = T + 10C3 (300 )

Assume C3 = 0. (300 ) =⇒ U + N = T − 1. Replace in (200 ): E + 10 = T − 1 =⇒


E + 11 = T . Impossible thus C3 = 1 .
(300 ) =⇒ U + N + 1 = T + 10, thus U + N = T + 9. Replace in (200 ): T + 9 = E + 10 =⇒
T = E + 1.
Since E 6= 1 and T 6= 1 and following a similar reasoning as for N and R, we conclude
that DE = {2, 3, 4, 5, 6, 7} and DT = {3, 4, 5, 6, 7, 8}.
Constraint (2):
R + U + 1 = E + 10 thus R + U = E + 9. Since E ≥ 2, R + U ≥ 11. Since R ≤ 7, it
follows that U ≥ 4. Thus DU = {4, 5, 6, 7, 8}.

Notice that the value 0 can only be taken by letters A, P or I.

Assume A = 0:
Assume C4 = 0. (5) =⇒ R = P + 10. Impossible thus C4 = 1.
(5) =⇒ R + 1 = P + 10 =⇒ R = P + 9. Impossible so A 6= 0. And we backtrack
without recording the value of C4 .

Assume P = 0:
Assume C4 = 0:
T + A + 1 = I (40 )
A+R = 10 (50 )
Since R ≤ 7, we have (50 ) =⇒ A ≥ 3.
We have I ≤ 8, thus (40 ) =⇒ T + A + 1 ≤ 8 =⇒ T + A ≤ 7.
We have T ≥ 3 and A ≥ 3. But T 6= A =⇒ T + A ≥ 3 + 4 =⇒ T + A + 1 ≥ 8. Thus
we have 8 ≤ I ≤ 8, thus I = 8.
Thus T + A = 7. Assume T = 3, then A = 4, E = 2, R = 6, N = 7 and U = 5.
Thus we have found the solution to the puzzle as follows:

P = 0, J = 1, E = 2, T = 3, A = 4, U = 5, R = 6, N = 7, I = 8, S = 9.
with C1 = C2 = C3 = C5 = C6 = 1 and C4 = 0.
We can verify that: 943567 + 564759 = 1508326.

You might also like