Effiziente Weise Cryptarithms von Solving

Question

Hallo ich über dieses Rätsels gekommen, die eine Teilmenge der bekannten Art von Wort und Zahlen basierte Rätsel namens Cryptarithms . Angenommen, Sie haben einen Ausdruck wie

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

Jetzt interessanten Teil ist es, dass wird jedes Alphabet eine eindeutige Zahl von 0-9 darstellt. Ich wollte einen generali Solver schreiben, aber ich am Ende für eine Brute gezwungene Lösung zu schreiben. Jeder Abnehmer wie wie kann ich sie lösen?

ich denke, es Prädikat Logik gelöst mit oder settheorie werden kann. Und ich bin besonders daran interessiert, C # oder Python-basierte Lösungen zu finden. Jeder.?

Answer 1

Auf dem dies PyCon Raymond Hettinger Jahr über AI-Programmierung in Python gesprochen, und hat Cryptarithms bedeckt.

Das Video ganzen Vortrags zu sehen ist hier und Kochbuch mit der Lösung kann auf Link .

Answer 2

Das ist so ein kleines Problem, dass eine Brute-Force-Lösung keine schlechte Methode. Unter der Annahme, dass jeder Buchstabe eine eindeutige Ziffer darstellen muss (dh werden wir nicht zulassen, dass die Lösung S = 9, M = 1, * = 0) sehen wir, dass die Anzahl von Kombinationen zu versuchen, sind n , wobei n ist die Anzahl der eindeutigen Buchstaben im Cryptarithm. Die theoretische maximale Anzahl von Kombinationen zu bewerten ist 10! = 3 628 800 , die wirklich kleine Zahl für einen Computer ist.

Wenn wir zulassen, dass mehrere Buchstaben die gleiche Anzahl, die Anzahl der Kombinationen darstellen zu versuchen, begrenzt wird 10 ^ n , wieder in der n ist die Anzahl der eindeutigen Briefe. Unter der Annahme, nur Kapital englische Buchstaben haben wir eine theoretische maximale Anzahl von Kombinationen von 10 ^ 26 , so für diesen theoretischen schlimmsten Fall haben wir einige Heuristiken benötigen. Die meisten praktischen cryptarithms haben viel weniger als 26 einzigartige Buchstaben obwohl, so dass der Normalfall wird wahrscheinlich durch eine begrenzt werden n weniger als 10, was wiederum für einen Computer ziemlich vernünftig ist.

Answer 3

Nun, versuchen Sie es als eine Liste von Funktionen zu schreiben:

 SEND
 MORE
----+
MONEY

Wenn ich meine untere Schule Mathe erinnern, sollte dies sein:

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

Answer 4

Hier ist eine effiziente Brute-Force-Methode, die Zyklen durch alle Möglichkeiten rekursiv, sondern auch Kenntnis von der Struktur des jeweiligen Problems nimmt das Problem abzukürzen.

Die ersten paar Argumente für jede Methode darstellen Versuchswerte für jeden Zweig, die Argumente v1, v2 usw. sind noch die Werte zugeteilt werden und können in jedem weitergegeben Bestellung. das Verfahren ist effizient, weil es ein Maximum von 8x7x5 möglich Versuchslösungen statt dem 10! / 2 mögliche Lösungen mit brutalen Gewalt

hat

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

diese eine Hilfe sein kann

Edit: die Antwort auf dem Wiki-Link Sie auf dem Laufenden ist auch nützlich,