Efficient way of Solving Cryptarithms

Question

Hi i came across this puzzle which is a subset of famous kind of word and numbers based puzzles called Cryptarithms. Say you have an expression as

S E N D + M O R E = M O N E Y

Now the interesting part there is that, each alphabet is representing a unique digit from 0-9. I wanted to write a generalized solver, but i ended up writing a brute forced solution for it. Any takers as how can i solve it?

I think it can be solved using predicate logic or set theory. And i'm particularly interested in finding C# or Python based solutions. Any one.?

Cornucopia

Answer 1

At PyCon 2009 Raymond Hettinger talked about AI programing in Python, and covered Cryptarithms.

The video of entire talk can be seen here, and cookbook with Python 2.6 solution can be found at this link.

Ramsden

That whole talk was good. The (3, 5, 8) gallon jug solver reminded me of Die Hard 3. – Skindive

Answer 2

This is such a small problem that a brute-force solution is not a bad method. Assuming that each letter must represent a unique digit (i.e. we won't allow the solution S = 9, M = 1, * = 0) we see that number of combinations to try is n!, where n is the number of unique letters in the cryptarithm. The theoretical max number of combinations to evaluate is 10! = 3 628 800, which is really small number for a computer.

If we allow several letters to represent the same number, the number of combinations to try will be bounded by 10^n, again where n is the number of unique letters. Assuming only capital English letters we have a theoretical max number of combinations of 10^26, so for that theoretical worst case we might need some heuristics. Most practical cryptarithms have a lot less than 26 unique letters though, so the normal case will probably be bounded by an n less than 10, which is again pretty reasonable for a computer.

Carbonize

brute force might be good for a particular case, how about when it must work for any input which is specified properly within limits? – Cornucopia

That was what I answered. For any general input, we can find the worst possible case for a brute-force search. If we want a strict solution it's 10!, if we allow duplicates it's 10^26. – Carbonize

Answer 3

Here is an efficient brute force method that cycles through all of the possibilities recursively but also takes note of the structure of the particular problem to shortcut the problem.

The first few arguments to each method represent trial values for each branch, the arguments v1, v2 etc are the values yet to be allocated and can be passed in any order. the method is efficient because it has a maximum of 8x7x5 possible trial solutions rather than the 10!/2 possible solutions by brute force

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace ConsoleApplication1
{
    class Program
    {
        static void MESDYNR(int m, int s, int e, int d, int y, int n, int r, int v1, int v2, int v3)
        {
            // Solve for O in hundreds position
            // "SEND" + "M?RE" = "M?NEY"
            int carry = (10 * n + d + 10 * r + e) / 100;
            int o = (10 + n - (e + carry))%10;

            if ((v1 == o) || (v2 == o) || (v3 == o)) 
            {
                // check O is valid in thousands position
                if (o == ((10 + (100 * e + 10 * n + d + 100 * o + 10 * r + e) / 1000 + m + s) % 10))
                {
                    // "SEND" + "MORE" = "MONEY"
                    int send = 1000 * s + 100 * e + 10 * n + d;
                    int more = 1000 * m + 100 * o + 10 * r + e;
                    int money = 10000 * m + 1000 * o + 100 * n + 10 * e + y;

                    // Chck this solution
                    if ((send + more) == money)
                    {
                        Console.WriteLine(send + " + " + more + " = " + money);
                    }
                }
            }
        }

        static void MSEDYN(int m, int s, int e, int d, int y, int n, int v1, int v2, int v3, int v4)
        {
            // Solve for R
            // "SEND" + "M*?E" = "M*NEY"
            int carry = (d + e) / 10;
            int r = (10 + e - (n + carry)) % 10;

            if (v1 == r) MESDYNR(m, s, e, d, y, n, r, v2, v3, v4);
            else if (v2 == r) MESDYNR(m, s, e, d, y, n, r, v1, v3, v4);
            else if (v3 == r) MESDYNR(m, s, e, d, y, n, r, v1, v2, v4);
            else if (v4 == r) MESDYNR(m, s, e, d, y, n, r, v1, v2, v3);
        }

        static void MSEDY(int m, int s, int e, int d, int y, int v1, int v2, int v3, int v4, int v5)
        {
            // Pick any value for N
            MSEDYN(m, s, e, d, y, v1, v2, v3, v4, v5);
            MSEDYN(m, s, e, d, y, v2, v1, v3, v4, v5);
            MSEDYN(m, s, e, d, y, v3, v1, v2, v4, v5);
            MSEDYN(m, s, e, d, y, v4, v1, v2, v3, v5);
            MSEDYN(m, s, e, d, y, v5, v1, v2, v3, v4);
        }

        static void MSED(int m, int s, int e, int d, int v1, int v2, int v3, int v4, int v5, int v6)
        {
            // Solve for Y
            // "SE*D" + "M**E" = "M**E?"
            int y = (e + d) % 10;

            if (v1 == y) MSEDY(m, s, e, d, y, v2, v3, v4, v5, v6);
            else if (v2 == y) MSEDY(m, s, e, d, y, v1, v3, v4, v5, v6);
            else if (v3 == y) MSEDY(m, s, e, d, y, v1, v2, v4, v5, v6);
            else if (v4 == y) MSEDY(m, s, e, d, y, v1, v2, v3, v5, v6);
            else if (v5 == y) MSEDY(m, s, e, d, y, v1, v2, v3, v4, v6);
            else if (v6 == y) MSEDY(m, s, e, d, y, v1, v2, v3, v4, v5);
        }

        static void MSE(int m, int s, int e, int v1, int v2, int v3, int v4, int v5, int v6, int v7)
        {
            // "SE**" + "M**E" = "M**E*"
            // Pick any value for D
            MSED(m, s, e, v1, v2, v3, v4, v5, v6, v7);
            MSED(m, s, e, v2, v1, v3, v4, v5, v6, v7);
            MSED(m, s, e, v3, v1, v2, v4, v5, v6, v7);
            MSED(m, s, e, v4, v1, v2, v3, v5, v6, v7);
            MSED(m, s, e, v5, v1, v2, v3, v4, v6, v7);
            MSED(m, s, e, v6, v1, v2, v3, v4, v5, v7);
            MSED(m, s, e, v7, v1, v2, v3, v4, v5, v6);
        }


        static void MS(int m, int s, int v1, int v2, int v3, int v4, int v5, int v6, int v7, int v8)
        {
            // "S***" + "M***" = "M****"
            // Pick any value for E
            MSE(m, s, v1, v2, v3, v4, v5, v6, v7, v8);
            MSE(m, s, v2, v1, v3, v4, v5, v6, v7, v8);
            MSE(m, s, v3, v1, v2, v4, v5, v6, v7, v8);
            MSE(m, s, v4, v1, v2, v3, v5, v6, v7, v8);
            MSE(m, s, v5, v1, v2, v3, v4, v6, v7, v8);
            MSE(m, s, v6, v1, v2, v3, v4, v5, v7, v8);
            MSE(m, s, v7, v1, v2, v3, v4, v5, v6, v8);
            MSE(m, s, v8, v1, v2, v3, v4, v5, v6, v7);
         }

        static void Main(string[] args)
        {
            // M must be 1
            // S must be 8 or 9
            DateTime Start = DateTime.Now;
            MS(1, 8, 2, 3, 4, 5, 6, 7, 9, 0);
            MS(1, 9, 2, 3, 4, 5, 6, 7, 8, 0);
            Console.WriteLine((DateTime.Now-Start).Milliseconds);
            return;
        }
    }
}

Transparency

Answer 4

Well, try writing it as a list of functions:

 SEND
 MORE
----+
MONEY

If I remember my lower school math, this should be:

Y = (D+E) mod 10
E = ((N+R) + (D+E)/10) mod 10
...

Ridinger

your basics are right! that's how it is, but i wonder how to make it in a generic solver way.. – Cornucopia

Answer 5

this may be of some help

Edit: the answer on the wiki link you posted is also useful!

Tameika