maneira eficiente de resolver Cryptarithms

Question

Hi me deparei com este quebra-cabeça que é um subconjunto do famoso tipo de palavra e números quebra-cabeças baseados chamados Cryptarithms . Digamos que você tenha uma expressão como

S P T D + M O R E = H O N L Y

Agora a parte interessante não é que, cada alfabeto está representando um dígito único de 0-9. Eu queria escrever um solver generalizada, mas acabei escrevendo uma solução ataque de força bruta para ele. Todos os compradores como como posso resolver isso?

Eu acho que pode ser resolvido usando lógica de predicados ou teoria dos conjuntos. E eu estou particularmente interessado em encontrar C # ou soluções baseadas em Python. Qualquer um.?

Answer 1

Nesta ano PyCon Raymond Hettinger falou sobre AI programação em Python, e cobriu Cryptarithms.

O vídeo de toda conversa pode ser visto aqui , e livro de receitas com solução pode ser encontrada em < a href = "http://code.activestate.com/recipes/576615/" rel = "noreferrer"> este link .

Answer 2

Este é um pequeno problema de tal forma que uma solução de força bruta não é um método ruim. Assumindo que cada carta deve representar um dígito único (ou seja, não vamos permitir que a solução S = 9, M = 1, * = 0), vemos que o número de combinações para tentar é n! , onde n é o número de letras únicas no cryptarithm. O número máximo teórico de combinações para avaliar é 10! = 3 628 800 , que é realmente pequeno número de um computador.

Se permitirmos que várias cartas para representar o mesmo número, o número de combinações para tentar será delimitada por 10 ^ n , de novo, onde n é o número de exclusivo cartas. Assumindo letras inglesas única de capitais, temos um número máximo teórico de combinações de 10 ^ 26 , então para que pior caso teórico que pode precisar de algumas heurísticas. A maioria dos cryptarithms práticas têm muito menos do que 26 letras únicas, porém, assim o caso normal provavelmente será limitado por um n inferior a 10, que é novamente bastante razoável para um computador.

Answer 3

Bem, tente escrevê-lo como uma lista de funções:

 SEND
 MORE
----+
MONEY

Se eu me lembro da minha matemática da escola menor, este deve ser:

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

Answer 4

Aqui é um método eficiente de força bruta que percorre todas as possibilidades de forma recursiva, mas também toma nota da estrutura do problema particular atalho para o problema.

Os primeiros argumentos para cada método de representar valores de teste para cada ramo, os argumentos V1, V2 etc são os valores ainda a serem alocados e pode ser transmitida em qualquer ordem. o método é eficiente porque tem um máximo de 8x7x5 soluções de teste possíveis ao invés do 10! / 2 possíveis soluções de força bruta

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 5

este pode ser de alguma ajuda

Editar: a resposta no link wiki você postou também é útil