

In [ ]:

    
%%HTML
<style>
.container { width:100% !important; }
</style>

A Crypto-Arithmetic Puzzle

In this notebook we formulate the crypto-arithmetic puzzle shown in the picture below as a constraint satisfaction problem.

The idea is that the letters "$\texttt{S}$", "$\texttt{E}$", "$\texttt{N}$", "$\texttt{D}$", "$\texttt{M}$", "$\texttt{O}$", "$\texttt{R}$", "$\texttt{Y}$" occurring in this puzzle are interpreted as variables ranging over the set of decimal digits, i.e. these variables can take values in the set $\{0,1,2,3,4,5,6,7,8,9\}$. Then, the string "$\texttt{SEND}$" is interpreted as a decimal number, i.e. it is interpreted as the number $$\texttt{S} \cdot 10^3 + \texttt{E} \cdot 10^2 + \texttt{N} \cdot 10^1 + \texttt{D} \cdot 10^0.$$ The strings "$\texttt{MORE}$ and "$\texttt{MONEY}$" are interpreted similarly. To make the problem interesting, the assumption is that different variables have different values.
Furthermore, the digits at the beginning of a number should be different from $0$. Then, we have to find values such that the formula $$ (\texttt{S} \cdot 10^3 + \texttt{E} \cdot 10^2 + \texttt{N} \cdot 10 + \texttt{D})

(\texttt{M} \cdot 10^3 + \texttt{O} \cdot 10^2 + \texttt{R} \cdot 10 + \texttt{E}) = \texttt{M} \cdot 10^4 + \texttt{O} \cdot 10^3 + \texttt{N} \cdot 10^2 + \texttt{E} \cdot 10 + \texttt{Y}. $$ is true. The problem with this constraint is that it involves far too many variables. As this constraint can only be checked when all the variables have values assigned to them, the backtracking search would essentially boil down to a mere brute force search. We would have 8 variables and hence we would have to test $10^{8}$ possible assignments. In order to do better, we have to perform the addition in the figure shown above column by column, just as it is taught in elementary school. To be able to do this, we have to introduce <em>carry digits</em> "$\texttt{C1}$", "$\texttt{C2}$", "$\texttt{C3}$" where $\texttt{C1}$ is the carry produced by adding $\texttt{D}$ and $\texttt{E}$, $\texttt{C2}$ is the carry produced by adding $\texttt{N}$, $\texttt{R}$ and $\texttt{C1}$, and $\texttt{C3}$ is the carry produced by adding $\texttt{E}$, $\texttt{O}$ and $\texttt{C2}$.

For a set $V$ of variables, the function $\texttt{allDifferent}(V)$ generates a set of formulas that express that all the variables of $V$ are different.



In [ ]:

    
def allDifferent(Variables):
    return { f'{x} != {y}' for x in Variables
                           for y in Variables 
                           if x < y 
           }

The function crypto_csp computes a constraint satisfaction problem that encodes the crypto-arithmetic puzzle shown above.



In [ ]:

    
def crypto_csp():
    Digits       = { 'S', 'E', 'N', 'D', 'M', 'O', 'R', 'Y' }
    Variables    = Digits | { 'C1', 'C2', 'C3' }
    Values       = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 }
    Constraints  = allDifferent(Digits)
    Constraints |= { '(D + E)      % 10 == Y', '(D + E)      // 10 == C1',
                     '(N + R + C1) % 10 == E', '(N + R + C1) // 10 == C2',
                     '(E + O + C2) % 10 == N', '(E + O + C2) // 10 == C3',
                     '(S + M + C3) % 10 == O', '(S + M + C3) // 10 == M'
                   }
    Constraints |= { 'S != 0', 'M != 0' }
    # Constraints |= { 'C1 < 2', 'C2 < 2', 'C3 < 2' }
    return Variables, Values, Constraints



In [ ]:

    
puzzle = crypto_csp()
puzzle



In [ ]:

    
def show_solution(A):
    if A == None:
        print("no solution found")
        return
    for v in { "S", "E", "N", "D", "M", "O", "R", "Y" }:
        print(f"{v} = {A[v]}")
    print("\nThe solution of\n")
    print("    S E N D")
    print("  + M O R E")
    print("  ---------")
    print("  M O N E Y")
    print("\nis as follows\n")
    print(f"    {A['S']} {A['E']} {A['N']} {A['D']}")
    print(f"  + {A['M']} {A['O']} {A['R']} {A['E']}")
    print(f"  ==========")
    print(f"  {A['M']} {A['O']} {A['N']} {A['E']} {A['Y']}")



In [ ]: