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

Eudora

Is there a max limit to the length of the words? – Analogy

There will only be one puzzle to solve at a time so tables can be created/modified specifically for that attempt. The puzzles will all be of the format length(4) + length(4) = length(5) – Eudora

Your first edit is impossible, there are more than 10 different letters. Each cannot have its own digit – Behling

The letters are not multiplied together. They are concatenated to form 1 long integer. O=1,V=2,E=3,R=4 ==> 1234 – Eudora

That stipulation may be impossible for the equation I provided because I altered the actual problem just for StackOverflow. The actual problem is SEND + MORE = MONEY – Eudora

@BrianWebster - would the new equation look the same or would you approach it differently without that stipulation being impossible? – Eudora

Ok, I posted a second answer since the two problems are quite unique – Behling

Sorry about that! I didn't realize my new equation had so many implications! – Eudora

Too late for this post -- but I do have the set-based reasoning and PosgreSQL implementation on my site damirsystems.com/?p=713 – Comb

Answer 1

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

Behling

Answer 2

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

Behling