Cryptarithmsを解決するための効率的な方法

StackOverflow https://stackoverflow.com/questions/750984

質問

こんにちは、私は有名な言葉の種類と数と呼ばれるベースのパズルのサブセットであり、このパズルに出くわした Cryptarithms に。あなたが

として式を持っていると言います

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

これで興味深い部分は、各アルファベットは0-9からのユニークな数字を表している、ということがあります。私は一般化ソルバーを書きたかったが、私はそれのためにブルート強制的にソリューションを書き終わりました。どのように私はそれを解決することができるなどの任意の受験者？

私はそれが述語論理や集合論を使用して解決することができると思います。そして私は、C＃やPythonベースのソリューションを見つけることに特に興味があります。いずれ。？

役に立ちましたか？

解決

今年のPyConレイモンド・ヘッティンガーではPythonでAIのプログラミングの話、そしてCryptarithmsをカバーしています。

全体の話の動画がここを見て、その溶液をクックブック可能な<上で見つけることができますhref = "http://code.activestate.com/recipes/576615/" = "noreferrer" REL>このリンクでます。

他のヒント

これは、ブルートフォース溶液が悪い方法ではないような小さな問題です。どこ、（、* = 0、M = 1、すなわち我々は解決策S = 9を許可しません）は、我々がしようとする組み合わせの数を参照してくださいそれぞれの文字が固有の数字を表現しなければならないことをされたと仮定すると、N！ N はcryptarithmに一意の文字の数です。評価する組み合わせの理論上の最大数は、は10です！ = 3 628 800 を、コンピュータのための本当に小さな数です。

私たちはいくつかの文字が同じ番号を表現できるようにする場合は、しようとする組み合わせの数は、<私> 10 ^ N で囲まれます、再びここで、名詞は、一意の番号です手紙。その理論的な最悪の場合のために、我々はいくつかのヒューリスティックを必要とするかもしれないので、私たちは<私> 10 ^ 26 の組み合わせの理論上の最大数を持っている唯一の資本英語の手紙を仮定。通常の場合は、おそらくで囲まれますので、ほとんどの実用的なcryptarithmsは、以下の26個のユニークな文字ものの多くを持って名詞が10未満を、コンピュータのために再びかなり合理的である。

さて、関数のリストとしてそれを書いてみてください 

 SEND
 MORE
----+
MONEY

私は私の下の学校の数学を覚えていれば、これはする必要があります：

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

ここで再帰的にも問題をショートカットするために特定の問題の構造に留意する可能性の全てを循環効率的なブルートフォース方法である。

の各方法の最初のいくつかの引数は、各ブランチの試験値、引数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;
        }
    }
}

このには、いくつかの助けになることがあります。

編集：！あなたが掲示ウィキリンク上の答えも便利です。

ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top