c - 为以下密码/字母谜题寻找强力算法

Question

我正在尝试用 C 编写一个程序来解决以下 cryptarithm :

one + one = two

seven is prime

nine is a perfect square

也就是说，我需要找到单词one、two、seven 和nine 的数值其中每个字母(o、n、e、t、w、s、v、i)都被赋予一个数值，并且完整的数字也满足上述所有条件。

我正在考虑为每个单词创建一个 int 数组，然后 1) 检查每个单词是否满足条件(例如是“七”的素数)，然后 2) 检查是否每个整数在数组与其他单词的值一致，其他单词也满足各自的条件。

我真的看不到这个工作，因为我必须在每次迭代中不断地将 int 数组转换为单个 int，然后我不确定如何同时将数组中的每个元素与其他单词匹配.

也许知道每个单词必须为真的 MIN 和 MAX 数值范围会有用吗？

有什么想法吗？

Answer 1

对于蛮力(ish)方法，我将从素数 seven 开始，并使用 Sieve of Eratosthenes得到直到 99999 的所有素数。您可以丢弃所有第 2 位和第 4 位数字不相同的答案。之后您可以继续计算正方形 nine，因为其中三个数字由素数 seven 决定。那应该很好地缩小可能性，然后您可以使用@pmg 的答案来完成它:-)。

更新:下面的 C# 程序似乎可以做到这一点

bool[] poss_for_seven = new bool[100000];       // this will hold the possibilities for `seven`
for (int seven = 0; seven < poss_for_seven.Length; seven++)
    poss_for_seven[seven] = (seven > 9999);     // `seven` must have 5 digits
// Sieve of Eratosthenes to make `seven` prime
for (int seven = 2; seven < poss_for_seven.Length; seven++) {
    for (int j = 2 * seven; j < poss_for_seven.Length; j += seven) {
        poss_for_seven[j] = false;
    }
}
// look through the array poss_for_seven[], considering each possibility in turn
for (int seven = 10000; seven < poss_for_seven.Length; seven++) {
    if (poss_for_seven[seven]) {
        int second_digit = ((seven / 10) % 10);
        int fourth_digit = ((seven / 1000) % 10);
        if (second_digit == fourth_digit) {
            int e = second_digit;
            int n = (seven % 10);   // NB: `n` can't be zero because otherwise `seven` wouldn't be prime
            for (int i = 0; i < 10; i++) {
                int nine = n * 1000 + i * 100 + n * 10 + e;
                int poss_sqrt = (int)Math.Floor(Math.Sqrt(nine) + 0.1); // 0.1 in case of of rounding error
                if (poss_sqrt * poss_sqrt == nine) {
                    int o = ((2 * e) % 10); // since 2 * `one` = `two`, we now know `o`
                    int one = o * 100 + n * 10 + e;
                    int two = 2 * one;
                    int t = ((two / 100) % 10);
                    int w = ((two / 10) % 10);
                    // turns out that `one`=236, `two`=472, `nine` = 3136.
                    // look for solutions where `s` != `v` with `s` and `v' different from `o`, `n`, `e`,`t`, `w` and `i`
                    int s = ((seven / 10000) % 10);
                    int v = ((seven / 100) % 10);
                    if (s != v && s != o && s != n && s != e && s != t && s != w && s != i && v != o && v != n && v != e && v != t && v != w && v != i) {
                        System.Diagnostics.Trace.WriteLine(seven + "," + nine + "," + one + "," + two);
                    }
                }
            }
        }
    }
}

nine 似乎总是等于 3136，所以 one = 236 和 two = 472。然而，有 21 种可能七。如果添加任何两个数字都不能取相同值的约束(这是上面的 C# 代码所做的)，那么它会减少到只有一种可能性(尽管我的代码中的一个错误意味着这个答案最初有 3 种可能性):

seven,nine,one,two
56963,3136,236,472