Efficient way of Solving Cryptarithms

问题:

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.?

回答1:

On this year's PyCon Raymond Hettinger talked about AI programing in Python, and has covered Cryptarithms.

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

回答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.

回答3:

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
...

回答4:

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;
        }
    }
}

回答5:

this may be of some help

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