解决密码问题的有效方法

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

题

嗨，我遇到了这个谜题，它是著名的基于单词和数字的谜题的子集，称为 隐秘虫. 。假设你有一个表达式

发送 + 更多 = 金钱

有趣的是，每个字母表都代表 0-9 的唯一数字。我想编写一个通用求解器，但最终我为其编写了一个强制解决方案。有哪位高手帮我解决一下吗？

我认为可以使用谓词逻辑或集合论来解决。我对寻找基于 C# 或 Python 的解决方案特别感兴趣。任何人。？

有帮助吗？

解决方案

在今年的 PyCon 上，Raymond Hettinger 谈论了 Python 中的人工智能编程，并涵盖了密码学。

整个演讲视频可见 这里, ，以及包含解决方案的食谱可以在 这个链接.

其他提示

这是这样一个小问题，即强力解决方案是不坏的方法。假设每个字母必须代表一个唯一的数字（即，我们将不允许溶液S = 9，M = 1，* = 0），我们看到数字组合菜系是名词！，其中名词的是在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