C++ 密码算术谜题

数字密码算术谜题有时也被称为文字算术或字母算术。在这类基于数学的谜题中，字母或符号代表算术方程中的数字。这个谜题的主要目的是确定每个字母的正确数字，以形成一个真实的方程。凭借其迷人的本质，谜题爱好者和计算机科学家无法忘记这类问题。

问题陈述

考虑示例："SEND + MORE = MONEY"。每个字母代表 0 到 9 之间的一个唯一数字，任务是找到正确的数字分配给字母，使方程有效。这个问题属于约束满足问题范畴，我们必须满足一组约束（算术方程）并符合特定条件（每个字母代表不同的数字）。

方法

解决数字密码算术谜题的一种常见方法是暴力枚举结合回溯。我们系统地尝试不同的数字分配组合，直到找到一个有效的解决方案或所有可能性都被穷尽。

算法概述

1. 生成排列： 枚举给定字母的所有可能数字排列。
2. 检查有效性： 对于每个排列，将数字代入方程并检查其是否成立。
3. 回溯： 如果方程不满足，则回溯并尝试不同的排列，直到找到解决方案或所有排列都被穷尽。

程序 1：暴力回溯实现

让我们以一个例子来说明 C++ 中使用暴力回溯解决数字密码算术谜题。

输出

Solution found:  D = 1 E = 5 M = 0 N = 3 O = 8 R = 2 S = 7 Y = 6

说明

• 在此实现中，问题使用回溯技术解决。
• 有一个LetterMapping结构，用于将每个字母映射到一个数字。
• 有一个评估函数，用于确定底层方程是否满足当前映射。
• 首先，solveCryptographic检查两个字符串最多是否有十个唯一字符，这使得它可能被解决。之后，它调用permutation，该函数初始化映射并尝试所有排列。
• permutation函数递归地探索所有可行的“数字-字母”排列，直到找到一个有效的排列。
• 如果解决方案存在，则打印答案。

程序 2：使用 OR-Tools 的约束满足问题 (CSP) 实现

让我们以另一个例子来说明 C++ 中使用约束满足问题解决数字密码算术谜题。

输出

S = 9
E = 5
N = 6
D = 7
M = 1
O = 0
R = 8
Y = 2
Carries: 0 1 0 1

说明

• 此实现使用OR-Tools库作为CSP来解决谜题。
• 之后，它为每个字母和进位定义变量。
• 设置约束以确保方程得到满足。
• 使用约束求解器，它会查找解决方案并在找到时打印出来。

程序 3：约束传播实现

让我们以另一个例子来说明 C++ 中使用约束传播解决数字密码算术谜题。

输出

No solution found

说明

• 此实现通过约束传播解决谜题，从而避免了其他算法的猜测。
• 存在一个solveCryptarithmeticWithPropagation递归函数，用于在遵守约束的同时为字符赋值。
• 同时跟踪已使用的数字以及当前赋值是否仍然有效。
• 为了提高效率，应首先将数字分配给具有许多约束的字母。
• 主方法使用solveCryptarithmeticPuzzleWithPropagation函数调用执行谜题初始化和求解。
• 如果找到解决方案，则显示它。

结论

数字密码算术谜题不仅提供了有趣的挑战，而且还是解决问题和算法设计的绝佳练习。在 C++ 中实现这些谜题的求解器提供了亲身探索回溯、排列生成和约束满足等概念的机会。