6

我正在计划一个 C++ 程序，它需要 3 个字符串来表示一个密码谜题。例如，给定 TWO、TWO 和 FOUR，程序将找到每个字母的数字替换，使得数学表达式

   TWO 
+  TWO 
------
  FOUR

是真的，假设输入是正确的。解决这个问题的一种方法当然是暴力破解，用嵌套循环为每个字母分配每个可能的替换，反复尝试求和等等，直到最终找到答案。

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

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

考虑到这一点，还有一些规划思路：

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

- 我想我应该从每个字母的一组可能的值 0-9 开始，可能作为向量存储在“域”表中，并在进行扣除时从中消除值。例如，如果我看到一些像这样排列的字母

 A
 C
--
 A

，我可以说 C 为零，这消除了其域中的所有其他值。我可以想出不少推论，但将它们推广到各种小情况并放入代码中，乍一看似乎有点棘手。

-假设我有一系列很好的推论可以贯穿事物并从域表中引导出许多值，我想我仍然会遍历所有内容并希望状态空间足够小以合理地生成解决方案多少时间。但感觉必须有更多的东西！- 也许一些聪明的方程式要建立或类似的东西。

提示表示赞赏！

4

3 回答 3

1

我在我的博客中使用随机爬山算法解决了这个问题。基本思想是选择随机分配数字到字母，通过计算等式两侧之间的差来“评分”分配，然后更改分配（交换两位数）并重新计算分数，保留那些改进的更改分数并丢弃那些没有的变化。那是爬山，因为你只接受一个方向的变化。爬山的问题在于它有时会卡在局部最大值，所以你经常会放弃当前的尝试并重新开始；这是算法的随机化部分。该算法非常快：它可以在几分之一秒内解决我给它的每个密码。

于 2013-06-21T12:49:53.797 回答
1

你可以从右到左迭代这个问题，即你执行实际操作的方式。从最右边的列开始。对于您遇到的每个数字，您检查是否已经有该数字的分配。如果有，您使用它的值并继续。如果没有，那么你在所有可能的数字上输入一个循环（如果你想要一个双射映射，可能会省略已经使用的数字）并递归地继续每个可能的分配。当您到达总和行时，您再次检查是否已分配给定数字的变量。如果不是，则分配当前总和的最后一位，然后继续到下一个更高值的列，随身携带进位。如果已经有一个作业，并且它与你的结果的最后一位一致，你以同样的方式进行。

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

于 2013-06-21T11:18:10.467 回答
0

密码算术问题是经典的约束满足问题。基本上，您需要做的是让您的程序根据输入生成约束，以便您使用给定的示例最终得到如下内容：

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 类，所以我会把进一步的调查留给你。

（请注意，由于可能为9 并且列中的进位数字为 1 ，因此您不能做出类似A+C=A->之类的假设，但在最不重要的列中除外。这确实意味着通常仅限于 domain ，但是，所以你并没有完全同意。）C == 0CC{0, 9}

于 2013-06-21T13:17:25.900 回答