暗号を解く効率的な方法

Question

こんにちは、有名な単語と数字ベースのパズルのサブセットであるCryptarithmsのサブセットであるこのパズルを見つけました。もし

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

各アルファベットは、0-9から一意の数字を表している、ということがある興味深い部分として表現を有していると言います。私は一般化されたソルバーを書こうと思っていましたが、私はそれに強引な強制的な解決策を書いてしまいました。どのように私はそれを解決することができますように奪取者？

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

Answer 1

今年のPyConではRaymond HettingerがPythonのAIプログラミングについて語り、Cryptarithmsについて取り上げました。

全体のビデオはhere、解説付きの料理の本はthis linkにあります。まあ

Answer 2

thisは、いくつかの助け

編集のものとすることができる：あなたが投稿のwikiリンク上の答えにも便利です！

Answer 3

これは、ブルートフォースの解決法が悪い方法ではないという小さな問題です。各文字が一意の数字を表さなければならない（すなわち、解S = 9、M = 1、* = 0を許可しない）と仮定すると、試行する組み合わせの数は n！ここで、 nは、暗号のユニーク文字の数です。評価する組み合わせの理論的最大数は 10です。 = 3 628 800、これは実際にコンピュータの数が少ないです。

我々はいくつかの文字が同じ番号を表現できるようにする場合は、しようとする組み合わせの数が 10^nはで囲まれます、再びどこ Nは、ユニークな文字の数です。大文字の英字のみを仮定すると、理論上最大の組み合わせ数は 10^26です。その理論的最悪の場合、ヒューリスティックが必要な場合があります。ほとんどの実用的な暗号は、26個のユニークな文字よりもはるかに少ないので、通常の場合はおそらく nで制限されているでしょう。

Answer 4

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

SEND 
MORE 
----+ 
MONEY 

私は私の下の学校の数学を覚えていれば、これは次のようになります。ここでは

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

Answer 5

はそのサイクルの効率的な強引な方法であり、すべての可能性を再帰的に取り出すだけでなく、特定の問題の構造をメモして問題を解決します。

各メソッドの最初の数引数は各ブランチの試行値を表し、引数v1、v2などはまだ割り当てられていない値であり、任意の オーダーで渡すことができます。この方法は効率的です。なぜなら、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; 
     } 
    } 
}