我正在计划一个C++程序，该程序接受代表密码算术谜题的三个字符串。例如，给定TWO、TWO和FOUR，程序将为每个字母找到数字替代，使得数学表达式

   TWO +  TWO ------  FOUR

为真，输入假设为右对齐。当然，一种解决方法是使用暴力破解，通过嵌套循环为每个字母分配所有可能的替代，反复尝试求和等，直到最终找到答案。

我的想法是，尽管这种方法效率极低，但底层的循环检查可能是一个可行（甚至是必要）的方法——在进行一系列推理以限制每个变量的域之后。我发现这有点难以想象，但首先假设一个通用/填充结构是否合理（每个X代表一个不一定不同的数字，每个C是进位数字，在这种情况下，将是0或1）？:

   CCC.....CCC   XXX.....XXXX+  XXX.....XXXX----------------  CXXX.....XXXX 

考虑到这一点，更多的计划想法如下：

-尽管问题中不会给出前导零，但我可能应该在适当的地方添加足够的前导零以平衡/匹配操作数。

-我想我应该从每个字母的一组可能值0-9开始，可能存储在’domains’表中的向量中，并随着推理的进行从中消除值。例如，如果我看到一些字母像这样排列

 A C-- A

，我可以判断C为零，并从它的域中消除所有其他值。我可以想到很多推理，但将它们推广到各种小情况并将其编入代码似乎乍一看有点棘手。

-假设我有一系列好的推理，可以运行并从域表中剔除大量值，我想我仍然只会循环所有内容，并希望状态空间足够小，可以在合理的时间内生成解决方案。但感觉应该还有更多！-也许设置一些巧妙的方程或类似的东西。

欢迎提供建议！

回答：

密码算术问题是经典的约束满足问题。基本上，你需要做的就是让你的程序根据输入生成约束，以便你得到类似以下内容的东西，使用你给出的例子：

O + O = 2O = R + 10Carry1W + W + Carry1 = 2W + Carry1 = U + 10Carry2T + 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] == 0for 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}中，所以你对这一点的理解并不完全错误。）