Modo efficace per Risolvere Cryptarithms

Question

Ciao, mi sono imbattuto in questo puzzle che è un sottoinsieme del famoso sorta di parola e di numeri a base di puzzle chiamato Cryptarithms.Dici di avere un'espressione come

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

Ora la parte interessante è che, ogni alfabeto, rappresenta un unica cifra da 0 a 9.Volevo scrivere un generalizzato risolutore, ma ho finito per scrivere un bruto costretto soluzione.Eventuali acquirenti come posso risolvere?

Penso che può essere risolto utilizzando la logica del predicato o la teoria degli insiemi.E mi interessa in particolare la ricerca di C#, Python o soluzioni a base di.Uno qualsiasi.?

Answer 1

In quest'anno PyCon Raymond Hettinger parlato AI programmazione in Python, e ha coperto Cryptarithms.

Il video di tutto il discorso può essere visto qui , e libro di cucina con soluzione può essere trovata su < a href = "http://code.activestate.com/recipes/576615/" rel = "noreferrer"> questo link .

Answer 2

Questo è un piccolo problema in modo tale che una soluzione di forza bruta non è un metodo cattivo. Supponendo che ogni lettera deve rappresentare una cifra unica (cioè non consentirà la soluzione S = 9, M = 1, * = 0) si vede che il numero di combinazioni per provare è n , dove n è il numero di lettere uniche nel cryptarithm. Il numero massimo teorico di combinazioni per la valutazione è 10! = 3 628 800 , che è davvero piccolo numero per un computer.

Se permettiamo diverse lettere per rappresentare lo stesso numero, il numero di combinazioni da provare sarà delimitata da 10 ^ n , ancora una volta in cui n è il numero di unico lettere. Supponendo che solo lettere maiuscole inglesi abbiamo un numero massimo teorico di combinazioni di 10 ^ 26 , quindi per questo caso peggiore teorico potremmo aver bisogno alcune euristiche. cryptarithms più pratici hanno molto meno di 26 lettere uniche, però, in modo che il caso normale probabilmente sarà delimitata da un n inferiore a 10, che è ancora abbastanza ragionevole per un computer.

Answer 3

Beh, provare a scrivere come una lista di funzioni:

 SEND
 MORE
----+
MONEY

Se non ricordo la mia matematica scolastica inferiore, questo dovrebbe essere:

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

Answer 4

Ecco un efficace metodo forza bruta che passa in rassegna tutte le possibilità in modo ricorsivo, ma prende anche nota della struttura del particolare problema di scelta rapida del problema.

Il primo paio di argomenti per ogni metodo di rappresentare valori di valutazione per ogni ramo, gli argomenti v1, v2, ecc sono i valori ancora essere assegnati e può essere trasmesso in qualsiasi ordine.il metodo è efficiente perché ha un massimo di 8x7x5 possibile sperimentazione di soluzioni piuttosto che il 10!/2 possibili soluzioni con la forza 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

questo può essere di qualche aiuto

Modifica: la risposta sul link wiki che hai postato è utile anche