解决密码算术难题
什么是密码算术难题？
密码算术难题，也称为密码，是一种数学难题，我们将数字分配给字母或符号。最终目标是找到每个字母的唯一数字分配，以使给定的数学运算成立。在这种难题中，执行加法运算的方程是最常用的。然而，它还涉及其他算术运算，例如减法、乘法等。
密码算术谜题的规则如下 −
我们只能使用 0 到 9 之间的数字来表示谜题中唯一的字母。
在整个等式中，同一个数字不能分配给不同的字母。
用数字替换字母所形成的等式在数学上应该是正确的。
输入输出场景
假设给定的等式是 −
Input: B A S E B A L L ---------- G A M E S
在上述等式中，单词"BASE"和"BALL"相加，得到"GAMES"。算法会将给定单词的每个字母与一个从 0 到 9 的唯一数字关联起来。对于上述输入，输出应为 −
使用回溯法解决密码算术难题
解决密码算术问题的简单方法是从每个操作数中取出一个字母，从左侧开始逐一分配从 0 到 9 的数字。分配数字后，检查算术表达式的有效性。但是，对于较大的操作数，此方法效率低下。
要使用回溯法解决密码算术问题，请按照以下步骤操作 −
首先，从给定的算术表达式中找出所有唯一字符。
接下来，尝试将数字分配给字母。如果发现重复，则回溯并取消分配。这样，将生成每个字母所有可能的数字组合。
现在，用数字替换字母，并检查表达式是否为真。
示例
在下面的示例中，我们将实际演示如何解决密码算术问题。
#include <stdio.h>
#include <string.h>
//当之前有一个字符被赋值时，设置 1
int use[10] = {0};
// 结构体
struct node {
char letter;
int value;
};
int isValid(struct node* nodeList, const int count, char* s1, char* s2, char* s3) {
int val1 = 0, val2 = 0, val3 = 0, m = 1, j, i;
//查找第一个字符串的数字
for (i = strlen(s1) - 1; i >= 0; i--) {
char ch = s1[i];
for (j = 0; j < count; j++)
//当 ch 存在时，打破循环
if (nodeList[j].letter == ch)
break;
val1 += m * nodeList[j].value;
m *= 10;
}
m = 1;
//找到第二个字符串的数字
for (i = strlen(s2) - 1; i >= 0; i--) {
char ch = s2[i];
for (j = 0; j < count; j++)
if (nodeList[j].letter == ch)
break;
val2 += m * nodeList[j].value;
m *= 10;
}
m = 1;
//找到第三个字符串的数字
for (i = strlen(s3) - 1; i >= 0; i--) {
char ch = s3[i];
for (j = 0; j < count; j++)
if (nodeList[j].letter == ch)
break;
val3 += m * nodeList[j].value;
m *= 10;
}
//检查总和是否与第三个字符串相同
if (val3 == (val1 + val2))
return 1;
return 0;
}
int permutation(int count, struct node* nodeList, int n, char* s1, char* s2, char* s3) {
//当为所有字符分配值时
if (n == count - 1) {
for (int i = 0; i < 10; i++) {
// 对于那些未使用的数字
if (use[i] == 0) {
//赋值i
nodeList[n].value = i;
//检查验证
if (isValid(nodeList, count, s1, s2, s3) == 1) {
printf("Solution found: ");
//打印已分配的代码
for (int j = 0; j < count; j++)
printf(" %c = %d", nodeList[j].letter, nodeList[j].value);
return 1;
}
}
}
return 0;
}
for (int i = 0; i < 10; i++) {
// 对于那些未使用的数字
if (use[i] == 0) {
//分配值 i 并标记为不可用于将来使用
nodeList[n].value = i;
use[i] = 1;
//寻找下一个字符
if (permutation(count, nodeList, n + 1, s1, s2, s3) == 1)
return 1;
//当回溯时，再次提供
use[i] = 0;
}
}
return 0;
}
int solvePuzzle(char* s1, char* s2, char* s3) {
//唯一字符数
int uniqueChar = 0;
int len1 = strlen(s1);
int len2 = strlen(s2);
int len3 = strlen(s3);
//有 26 个不同的角色
int freq[26] = {0};
for (int i = 0; i < len1; i++)
++freq[s1[i] - 'A'];
for (int i = 0; i < len2; i++)
++freq[s2[i] - 'A'];
for (int i = 0; i < len3; i++)
++freq[s3[i] - 'A'];
for (int i = 0; i < 26; i++)
//频率 > 0，则存在
if (freq[i] > 0)
uniqueChar++;
//因为十进制中有 10 位数字
if (uniqueChar > 10) {
printf("Invalid strings");
return 0;
}
struct node nodeList[uniqueChar];
//分配三个字符串中找到的所有字符
for (int i = 0, j = 0; i < 26; i++) {
if (freq[i] > 0) {
nodeList[j].letter = (char)(i + 'A');
j++;
}
}
return permutation(uniqueChar, nodeList, 0, s1, s2, s3);
}
int main() {
char s1[] = "BASE";
char s2[] = "BALL";
char s3[] = "GAMES";
if (solvePuzzle(s1, s2, s3) == 0)
printf("No solution");
return 0;
}
#include <iostream>
#include <vector>
using namespace std;
//集合 1，当之前分配了一个字符时
vector<int> use(10);
struct node {
char letter;
int value;
};
int isValid(node* nodeList, const int count, string s1, string s2, string s3) {
int val1 = 0, val2 = 0, val3 = 0, m = 1, j, i;
//查找第一个字符串的数字
for (i = s1.length() - 1; i >= 0; i--) {
char ch = s1[i];
for (j = 0; j < count; j++)
//当 ch 存在时，打破循环
if (nodeList[j].letter == ch)
break;
val1 += m * nodeList[j].value;
m *= 10;
}
m = 1;
//找到第二个字符串的数字
for (i = s2.length() - 1; i >= 0; i--) {
char ch = s2[i];
for (j = 0; j < count; j++)
if (nodeList[j].letter == ch)
break;
val2 += m * nodeList[j].value;
m *= 10;
}
m = 1;
//找到第三个字符串的数字
for (i = s3.length() - 1; i >= 0; i--) {
char ch = s3[i];
for (j = 0; j < count; j++)
if (nodeList[j].letter == ch)
break;
val3 += m * nodeList[j].value;
m *= 10;
}
//检查总和是否与第三个字符串相同
if (val3 == (val1 + val2))
return 1;
return 0;
}
bool permutation(int count, node* nodeList, int n, string s1, string s2, string s3) {
//当为所有字符分配值时
if (n == count - 1) {
for (int i = 0; i < 10; i++) {
// 对于那些未使用的数字
if (use[i] == 0) {
//赋值i
nodeList[n].value = i;
//检查验证
if (isValid(nodeList, count, s1, s2, s3) == 1) {
cout << "Solution found: ";
//打印已分配的代码
for (int j = 0; j < count; j++)
cout << " " << nodeList[j].letter << " = " << nodeList[j].value;
return true;
}
}
}
return false;
}
for (int i = 0; i < 10; i++) {
// 对于那些未使用的数字
if (use[i] == 0) {
//分配值 i 并标记为不可用于将来使用
nodeList[n].value = i;
use[i] = 1;
//寻找下一个字符
if (permutation(count, nodeList, n + 1, s1, s2, s3))
return true;
//当回溯时，再次提供
use[i] = 0;
}
}
return false;
}
bool solvePuzzle(string s1, string s2,string s3) {
//唯一字符数
int uniqueChar = 0;
int len1 = s1.length();
int len2 = s2.length();
int len3 = s3.length();
//有 26 个不同的角色
vector<int> freq(26);
for (int i = 0; i < len1; i++)
++freq[s1[i] - 'A'];
for (int i = 0; i < len2; i++)
++freq[s2[i] - 'A'];
for (int i = 0; i < len3; i++)
++freq[s3[i] - 'A'];
for (int i = 0; i < 26; i++)
//频率 > 0，则存在
if (freq[i] > 0)
uniqueChar++;
//因为十进制中有 10 位数字
if (uniqueChar > 10) {
cout << "Invalid strings";
return 0;
}
node nodeList[uniqueChar];
//分配三个字符串中找到的所有字符
for (int i = 0, j = 0; i < 26; i++) {
if (freq[i] > 0) {
nodeList[j].letter = char(i + 'A');
j++;
}
}
return permutation(uniqueChar, nodeList, 0, s1, s2, s3);
}
int main() {
string s1 = "BASE";
string s2 = "BALL";
string s3 = "GAMES";
if (solvePuzzle(s1, s2, s3) == false)
cout << "No solution";
}
public class Main {
// 当先前分配了一个字符时设置 1
int[] use = new int[10];
class Node {
char letter;
int value;
}
public int isValid(Node[] nodeList, int count, String s1, String s2, String s3) {
int val1 = 0, val2 = 0, val3 = 0;
int m = 1;
int j, i;
//查找第一个字符串的数字
for (i = s1.length() - 1; i >= 0; i--) {
char ch = s1.charAt(i);
for (j = 0; j < count; j++) {
// 当 ch 存在时，打破循环
if (nodeList[j].letter == ch) {
break;
}
}
val1 += m * nodeList[j].value;
m *= 10;
}
m = 1;
//找到第二个字符串的数字
for (i = s2.length() - 1; i >= 0; i--) {
char ch = s2.charAt(i);
for (j = 0; j < count; j++) {
if (nodeList[j].letter == ch) {
break;
}
}
val2 += m * nodeList[j].value;
m *= 10;
}
m = 1;
//找到第三个字符串的数字
for (i = s3.length() - 1; i >= 0; i--) {
char ch = s3.charAt(i);
for (j = 0; j < count; j++) {
if (nodeList[j].letter == ch) {
break;
}
}
val3 += m * nodeList[j].value;
m *= 10;
}
//检查总和是否与第三个字符串相同
if (val3 == (val1 + val2)) {
return 1;
}
return 0;
}
public int permutation(int count, Node[] nodeList, int n, String s1, String s2, String s3) {
//当赋值时
if (n == count - 1) {
// 对于那些未使用的数字
for (int i = 0; i < 10; i++) {
if (use[i] == 0) {
//赋值i
nodeList[n].value = i;
if (isValid(nodeList, count, s1, s2, s3) == 1) {
System.out.print("Solution found:");
//打印已分配的代码
for (int j = 0; j < count; j++) {
System.out.print(" " + nodeList[j].letter + " = " + nodeList[j].value);
}
return 1;
}
}
}
return 0;
}
// 对于那些未使用的数字
for (int i = 0; i < 10; i++) {
if (use[i] == 0) {
//分配值 i 并标记为不可用于将来使用
nodeList[n].value = i;
use[i] = 1;
if (permutation(count, nodeList, n + 1, s1, s2, s3) == 1) {
//寻找下一个字符
return 1;
}
//当回溯时，再次提供
use[i] = 0;
}
}
return 0;
}
public int solvePuzzle(String s1, String s2, String s3) {
//唯一字符数
int uniqueChar = 0;
int len1 = s1.length();
int len2 = s2.length();
int len3 = s3.length();
// 有 26 个不同的角色
int[] freq = new int[26];
for (int i = 0; i < len1; i++) {
freq[s1.charAt(i) - 'A']++;
}
for (int i = 0; i < len2; i++) {
freq[s2.charAt(i) - 'A']++;
}
for (int i = 0; i < len3; i++) {
freq[s3.charAt(i) - 'A']++;
}
//频率 > 0，则存在
for (int i = 0; i < 26; i++) {
if (freq[i] > 0) {
uniqueChar++;
}
}
//因为十进制中有 10 位数字
if (uniqueChar > 10) {
System.out.println("Invalid strings");
return 0;
}
Node[] nodeList = new Node[uniqueChar];
int j = 0;
for (int i = 0; i < 26; i++) {
//分配三个字符串中找到的所有字符
if (freq[i] > 0) {
nodeList[j] = new Node();
nodeList[j].letter = (char) (i + 'A');
j++;
}
}
return permutation(uniqueChar, nodeList, 0, s1, s2, s3);
}
public static void main(String[] args) {
Main main = new Main();
String s1 = "BASE";
String s2 = "BALL";
String s3 = "GAMES";
if (main.solvePuzzle(s1, s2, s3) == 0) {
System.out.println("No solution");
}
}
}
class Main:
#当先前分配了一个字符时设置 1
use = [0] * 10
class Node:
def __init__(self):
self.letter = ''
self.value = 0
def isValid(self, nodeList, count, s1, s2, s3):
val1 = 0
val2 = 0
val3 = 0
m = 1
j = 0
i = 0
#查找第一个字符串的数字
for i in range(len(s1) - 1, -1, -1):
ch = s1[i]
for j in range(count):
#当 ch 存在时，打破循环
if nodeList[j].letter == ch:
break
val1 += m * nodeList[j].value
m *= 10
m = 1
#找到第二个字符串的数字
for i in range(len(s2) - 1, -1, -1):
ch = s2[i]
for j in range(count):
if nodeList[j].letter == ch:
break
val2 += m * nodeList[j].value
m *= 10
m = 1
#找到第三个字符串的数字
for i in range(len(s3) - 1, -1, -1):
ch = s3[i]
for j in range(count):
if nodeList[j].letter == ch:
break
val3 += m * nodeList[j].value
m *= 10
#检查总和是否与第三个字符串相同
if val3 == (val1 + val2):
return 1
return 0
def permutation(self, count, nodeList, n, s1, s2, s3):
#当赋值时
if n == count - 1:
for i in range(10):
#对于那些未使用的数字
if self.use[i] == 0:
#赋值 i
nodeList[n].value = i
if self.isValid(nodeList, count, s1, s2, s3) == 1:
print("Solution found:", end='')
#打印代码，已分配
for j in range(count):
print(f" {nodeList[j].letter} = {nodeList[j].value}", end='')
return 1
return 0
for i in range(10):
#对于那些未使用的数字
if self.use[i] == 0:
#分配值 i 并标记为不可用于将来使用
nodeList[n].value = i
self.use[i] = 1
if self.permutation(count, nodeList, n + 1, s1, s2, s3) == 1:
#寻找下一个角色
return 1
#回溯时，再次提供
self.use[i] = 0
return 0
def solvePuzzle(self, s1, s2, s3):
#唯一字符数
uniqueChar = 0
len1 = len(s1)
len2 = len(s2)
len3 = len(s3)
#有 26 个不同的角色
freq = [0] * 26
for i in range(len1):
freq[ord(s1[i]) - ord('A')] += 1
for i in range(len2):
freq[ord(s2[i]) - ord('A')] += 1
for i in range(len3):
freq[ord(s3[i]) - ord('A')] += 1
for i in range(26):
#频率 > 0，则存在
if freq[i] > 0:
uniqueChar += 1
#as there are 10 digits in the decimal system
if uniqueChar > 10:
print("Invalid strings")
return 0
nodeList = [self.Node() for _ in range(uniqueChar)]
j = 0
for i in range(26):
#分配三个字符串中找到的所有字符
if freq[i] > 0:
nodeList[j].letter = chr(i + ord('A'))
j += 1
return self.permutation(uniqueChar, nodeList, 0, s1, s2, s3)
if __name__ == "__main__":
main = Main()
s1 = "BASE"
s2 = "BALL"
s3 = "GAMES"
if main.solvePuzzle(s1, s2, s3) == 0:
print("No solution")
输出
Solution found: A = 4 B = 2 E = 1 G = 0 L = 5 M = 9 S = 6
