问在C++中创建一个密码学求解器

EN

密码学问题是典型的constraint satisfaction problems。基本上，您需要做的是让您的程序根据输入生成约束，这样您就可以使用给定的示例得到如下所示的结果：

O + O = 2O = R + 10Carry1
W + W + Carry1 = 2W + Carry1 = U + 10Carry2
T + T + Carry2 = 2T + Carry2 = O + 10Carry3 = O + 10F

广义伪代码：

for i in range of shorter input, or either input if they're the same length:
    shorterInput[i] + longerInput2[i] + Carry[i] = result[i] + 10*Carry[i+1] // Carry[0] == 0

for the rest of the longer input, if one is longer:
    longerInput[i] + Carry[i] = result[i] + 10*Carry[i+1]

基于问题定义的附加约束：

Range(digits) == {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}
Range(auxiliary_carries) == {0, 1}

因此，对于您的示例：

Range(O, W, T) == {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}
Range(Carry1, Carry2, F) == {0, 1}

一旦您生成了限制搜索空间的约束，您就可以使用链接文章中描述的CSP解析技术遍历搜索空间并确定您的解决方案(当然，如果存在的话)。(局部)一致性的概念在这里非常重要，利用它可以极大地减少CSP的搜索空间。

作为一个简单的例子，请注意，加密算法通常不使用前导零，这意味着如果结果比两个输入的结果都长，那么最后一个数字，即最后一个进位数字，必须是1(所以在你的例子中，它意味着F == 1)。然后这个约束可以向后传播，因为它意味着2T + Carry2 == O + 10；换句话说，T的最小值必须是5，因为Carry2最多可以是1和2(4)+1==9。还有其他方法来增强搜索(最小冲突算法等)，但我不想把这个答案变成一个完整的CSP类，所以我把进一步的调查留给你。

(请注意，您不能做出像A+C=A -> C == 0这样的假设，除非是最不重要的列，因为C可能是9，列中的进位数字可能是1。这确实意味着C通常将仅限于域{0, 9}，因此您并没有完全理解错。)

你可以从右向左迭代这个问题，也就是你执行实际操作的方式。从最右边的列开始。对于您遇到的每个数字，您都会检查该数字是否已有赋值。如果有，则使用它的值并继续。如果没有，则在所有可能的数字上输入循环(如果需要双射映射，则可能省略已使用的数字)，并递归地继续每个可能的赋值。当您到达sum行时，再次检查给定数字的变量是否已赋值。如果不是，则将当前和的最后一位赋值，然后继续到下一个更高值的列，并随身携带进位。如果已经有一个赋值，并且它与结果的最后一位数一致，则以相同的方式继续。如果有一个赋值，但它不同意，那么你中止当前分支，并返回到最近的循环，在那里你有其他数字可供选择。

这种方法的好处应该是许多变量是由总和决定的，而不是预先猜测的。特别是对于只出现在sum行中的字母，这可能是一个巨大的胜利。此外，您可能能够在早期发现错误，从而在某些情况下避免选择字母，因为您到目前为止所做的选择已经不一致。缺点可能是程序的递归结构稍微复杂一些。但一旦你掌握了这一点，你也会学到很多将想法转化为代码的知识。

我在blog上使用随机爬山算法解决了这个问题。基本的想法是选择字母的随机数字分配，通过计算等式两边的差值来给分配“评分”，然后更改分配(交换两个数字)并重新计算分数，保留那些提高分数的更改，放弃那些不会提高分数的更改。这就是爬山，因为你只接受一个方向的更改。爬山的问题是它有时会陷入局部最大值，所以你经常会放弃当前的尝试并重新开始；这是算法的随机化部分。这个算法非常快:它能在几分之一秒内解决我给出的每一个密码。