Solving a Crypt-Arithmetic Puzzle with Relational Database

Question

Say you are given the crypt-arithmetic puzzle:

SEND + MORE = MONEY

The goal is to substitute numbers (0-9) for letters, so that the addition works out.

I understand how to approach the problem mathematically, but I am not sure how to solve this with a Relational Database.

How would a schema be designed to approach this problem?

How would an SQL query look that would attempt to solve this problem?

EDIT: There are some constraints:

1. The same number should be used for a given letter, throughout. For example, if you guess "5" for the letter E, then E should get the value "5" at all the places it occurs.
2. Different letters should get different numbers, e.g., you cannot assign "4" to both E and to M.
3. None of the numbers(words) may have any leading zeroes

Answer 1

The author poses two distinct problems.

This answers the problem that is posed, OVER + FLOW = STACK where each character does not necessarily have a unique digit and more than 10 characters may be involved

• There is a stipulation that each character receive a unique digit, but that is impossible for OVER + FLOW + STACK as there are too many letters.

Something like this may work where Digits table contains one column, where earch record contains an integer between 1 and 9 (or 0 through 9 if you wish).

Cross joins are pretty nasty, performance-wise, but this may be a starting point.

select
    top 5 
    O.num as O,
    V.num as V,
    E.num as E,
    R.num as R,
    F.num as F,
    L.num as L,
    W.num as W,
    S.num as S,
    T.num as T,
    A.num as A,
    C.num as C,
    K.num as K,
    (O.num * 1000 + V.num * 100 + E.num * 10 + R.num) as [OVER],
    (F.num * 1000 + L.num * 100 + O.num * 10 + W.num) as FLOW,
    (O.num * 1000 + V.num * 100 + E.num * 10 + R.num) + (F.num * 1000 + L.num * 100 + O.num * 10 + W.num) as OVER_plus_FLOW,
    (S.num * 10000 + T.num * 1000 + A.num * 100 + C.num * 10 + K.num) as STACK
from
    Digits as O
    cross join digits as V
    cross join digits as E
    cross join digits as R
    cross join digits as F
    cross join digits as L
    cross join digits as W
    cross join digits as S
    cross join digits as T
    cross join digits as A
    cross join digits as C
    cross join digits as K
where
    (O.num * 1000 + V.num * 100 + E.num * 10 + R.num)
    + (F.num * 1000 + L.num * 100 + O.num * 10 + W.num)
    = (S.num * 10000 + T.num * 1000 + A.num * 100 + C.num * 10 + K.num)

Based upon my understanding of the problem, there are multiple solutions. Here's the first 5 that this code found:

I removed 0 because you can replace each letter with zero and get a cheap answer (based upon your initial question revision).

This is the only table Digits

Answer 2

This answers the other problem posed by the user.

SEND + MORE = MONEY where each character has a unique digit and no word starts with zero.

select
    top 1
    S.num as S,
    E.num as E,
    N.num as N,
    D.num as D,
    M.num as M,
    O.num as O,
    R.num as R,
    Y.num as Y,
    (S.num * 1000 + E.num * 100 + N.num * 10 + D.num) as [SEND],
    (M.num * 1000 + O.num * 100 + R.num * 10 + E.num) as MORE,
    (S.num * 1000 + E.num * 100 + N.num * 10 + D.num) + (M.num * 1000 + O.num * 100 + R.num * 10 + E.num) as SEND_plus_MORE,
    (M.num * 10000 + O.num * 1000 + N.num * 100 + E.num * 10 + Y.num) as [MONEY]

from
    Digits as S
    join digits as E on E.num <> S.num
    join digits as N on N.num <> S.num and N.num <> E.num
    join digits as D on D.num <> S.num and D.num <> E.num and D.num <> N.num
    join digits as M on M.num <> S.num and M.num <> E.num and M.num <> N.num and M.num <> D.num
    join digits as O on O.num <> S.num and O.num <> E.num and O.num <> N.num and O.num <> D.num and O.num <> M.num
    join digits as R on R.num <> S.num and R.num <> E.num and R.num <> N.num and R.num <> D.num and R.num <> M.num and R.num <> O.num
    join digits as Y on Y.num <> S.num and Y.num <> E.num and Y.num <> N.num and Y.num <> D.num and Y.num <> M.num and Y.num <> O.num and Y.num <> R.num

where
    (S.num * 1000 + E.num * 100 + N.num * 10 + D.num)
    + (M.num * 1000 + O.num * 100 + R.num * 10 + E.num)
    = (M.num * 10000 + O.num * 1000 + N.num * 100 + E.num * 10 + Y.num)     
    and S.num <> 0 and M.num <> 0

I thought about something in the WHERE clause to enforce unique digits, but I believe this ends up processing too many permutations before the WHERE clause is checked.

Since we're only dealing with up to 10 digits, I think it is best to build the long ON clauses instead for speed concerns.

Here is the FROM + WHERE clause without the crazy ON clauses. This runs A LOT slower on my server.

from
    Digits as S
    cross join digits as E
    cross join digits as N
    cross join digits as D
    cross join digits as M
    cross join digits as O
    cross join digits as R
    cross join digits as Y

where
    (S.num * 1000 + E.num * 100 + N.num * 10 + D.num)
    + (M.num * 1000 + O.num * 100 + R.num * 10 + E.num)
    = (M.num * 10000 + O.num * 1000 + N.num * 100 + E.num * 10 + Y.num)     
    and S.num <> 0 and M.num <> 0

        and (select max(B.Count) from   
                (select COUNT(*) as Count from 
                    (select S.num, 's' as letter   -- the letters are included to make sure the unions do not merge equivalent rows
                    UNION select E.num, 'e'
                    UNION select N.num, 'n'
                    UNION select D.num, 'd'
                    UNION select M.num, 'm'
                    UNION select O.num, 'o'
                    UNION select R.num, 'r'
                    UNION select Y.num, 'y') as A
                    group by A.num
                ) as B
             ) = 1