Эффективный способ решения криптарифмов

Question

Привет, я натолкнулся на эту загадку, которая представляет собой подмножество известных видов слов и чисел, называемых Cryptarithms . Скажем, у вас есть выражение

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

Теперь интересная часть заключается в том, что каждый алфавит представляет собой уникальную цифру от 0 до 9. Я хотел написать обобщенный решатель, но в итоге я написал грубое принудительное решение для него. Любые берущие как, как я могу решить это?

Я думаю, что это можно решить с помощью логики предикатов или теории множеств. И я особенно заинтересован в поиске решений на C # или Python. Любой .?

Answer 1

В этом году на PyCon Рэймонд Хеттингер рассказал о программировании ИИ на Python и рассказал о криптарифмах.

Видео всего разговора можно посмотреть здесь , а кулинарную книгу с решением можно найти по по этой ссылке .

Answer 2

Это такая маленькая проблема, что грубое решение не плохой метод. Предполагая, что каждая буква должна представлять уникальную цифру (т. Е. Мы не допустим решения S = 9, M = 1, * = 0), мы видим, что количество комбинаций, которые нужно попробовать, составляет n! , где n - количество уникальных букв в криптарифе. Теоретическое максимальное количество комбинаций для оценки составляет 10! = 3 628 800 , что действительно мало для компьютера.

Если мы допустим, чтобы несколько букв представляли одно и то же число, количество попыток сочетания будет ограничено 10 ^ n , опять же, где n - количество уникальных букв. Предполагая, что только заглавные английские буквы у нас есть теоретическое максимальное количество комбинаций 10 ^ 26 , поэтому для этого теоретического наихудшего случая нам может потребоваться некоторая эвристика. В большинстве практических криптарифмов гораздо меньше, чем 26 уникальных букв, поэтому нормальный регистр, вероятно, будет ограничен n меньше 10, что опять-таки вполне разумно для компьютера.

Answer 3

Вот эффективный метод грубой силы, который рекурсивно просматривает все возможности, но также принимает во внимание структуру конкретной проблемы, чтобы быстро решить проблему.

Первые несколько аргументов каждого метода представляют пробные значения для каждой ветви, аргументы v1, v2 и т. Д. - это значения, которые еще предстоит выделить, и могут быть переданы в любом порядок. метод эффективен, потому что он имеет максимум 8x7x5 возможных пробных решений, а не 10! / 2 возможных решений методом грубой силы

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

Answer 4

Хорошо, попробуйте написать его в виде списка функций:

 SEND
 MORE
----+
MONEY

Если я помню свою младшую школьную математику, это должно быть:

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

Answer 5

это может оказать некоторую помощь

Редактировать: ответ по вики-ссылке, которую вы разместили, также полезен!