Cryptarithmetic Puzzle in C++
In this article, we will discuss a C++program to implement cryptarithmetic puzzle. But before going to its implementation, we must know about cryptarithmetic puzzle in C++.
What is the Cryptarithmetic Puzzle in C++?
The object of a cryptarithmetic puzzle is to determine the proper mapping from digit to letter to satisfy an arithmetic equation. In these puzzles, letters or symbols represent digits. Part of the difficulty is figuring out the right mapping given the puzzle's constraints. According to certain rules, a legitimate arithmetic expression can be formed by arranging the letters in a certain way. In a typical cryptarithmetic puzzle, each letter represents a distinct digit ranging from 0 to 9. Although division and subtraction can also be used, addition and multiplication are typically required to solve the puzzle.
Example:
SEND
+ MORE
--------
MONEY
The input is:
s1 = SEND, s2 = "MORE", s3 = "MONEY".
Output:
Here's one potential fix: N=3 O=8 R=2 S=7 Y=6 D=1 E=5 M=0
Every different letter in this puzzle stands for a different digit between 0 and 9. The goal is to determine which numbers satisfy the formula SEND + MORE = MONEY.
Programmatic approaches to Cryptarithmetic puzzle solving include constraint satisfaction algorithms, backtracking, and brute-force search. Backtracking is frequently used because it is effective at examining potential answers and wisely eliminating branches that will inevitably lead to dead ends.
Steps:
There are following steps to solve the Cryptarithmetic Puzzle in C++.
- First, we define a function that determines whether a possible solution is correct.
- Next, implement a recursive backtracking function to investigate potential digit assignments.
- After that, repeatedly go through potential digit assignments and determine whether they result in a workable solution.
- Remember the numbers we have used so we don't use them again.
- Stop the search and print the solution if a workable answer is discovered.
Example:
Let us take an example to illustrate the Cryptarithmetic Puzzle in C++.
#include <iostream>
#include <vector>
#include <string>
using namespace std;
vector<int> used(10);
struct Assignment {
char character;
int value;
};
bool isValidSolution(const vector<Assignment>& assignments, const string& s1, const string& s2, const 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 < assignments.size(); j++)
if (assignments[j].character == ch) break;
val1 += m * assignments[j].value;
m *= 10;
}
m = 1;
for (i = s2.length() - 1; i >= 0; i--) {
char ch = s2[i];
for (j = 0; j < assignments.size(); j++)
if (assignments[j].character == ch) break;
val2 += m * assignments[j].value;
m *= 10;
}
m = 1;
for (i = s3.length() - 1; i >= 0; i--) {
char ch = s3[i];
for (j = 0; j < assignments.size(); j++)
if (assignments[j].character == ch) break;
val3 += m * assignments[j].value;
m *= 10;
}
if (val3 == (val1 + val2))
return true;
return false;
}
bool generateAssignments(vector<Assignment>& assignments, int index, const string& s1, const string& s2, const string& s3) {
if (index == assignments.size()) {
if (isValidSolution(assignments, s1, s2, s3)) {
cout << "\nSolution found: ";
for (const auto& assignment : assignments) {
cout << " " << assignment.character << " = " << assignment.value;
}
return true;
}
return false;
}
for (int i = 0; i < 10; i++) {
if (!used[i]) {
assignments[index].value = i;
used[i] = 1;
if (generateAssignments(assignments, index + 1, s1, s2, s3)) {
return true;
}
used[i] = 0;
}
}
return false;
}
bool solveCryptographic(string s1, string s2, string s3) {
int uniqueChars = 0;
vector<int> frequency(26);
for (char ch : s1) frequency[ch - 'A']++;
for (char ch : s2) frequency[ch - 'A']++;
for (char ch : s3) frequency[ch - 'A']++;
for (int freq : frequency) {
if (freq > 0) uniqueChars++;
}
if (uniqueChars > 10) {
cout << "Invalid strings";
return false;
}
vector<Assignment> assignments(uniqueChars);
for (int i = 0, j = 0; i < 26; i++) {
if (frequency[i] > 0) {
assignments[j].character = char(i + 'A');
j++;
}
}
return generateAssignments(assignments, 0, s1, s2, s3);
}
int main() {
string s1 = "SEND";
string s2 = "MORE";
string s3 = "MONEY";
if (!solveCryptographic(s1, s2, s3)) {
cout << "No solution";
}
return 0;
}
Output:
Solution found: D = 1 E = 5 M = 0 N = 3 O = 8 R = 2 S = 7 Y = 6
Conclusion:
In conclusion, The cryptarithmetic puzzles are an intriguing challenge especially when approached programmatically in C++ when it comes to problem-solving and algorithm design. Solving these puzzles involves coming up with a unique mapping from digit to letter that meets predetermined arithmetic requirements, which are usually related to addition, subtraction, multiplication, or division. C++ programs are capable of intelligently traversing the solution space and avoiding redundant paths by utilizing backtracking algorithms, like the ones illustrated in the examples provided. The secret to success is developing effective algorithms that thoroughly examine the solution space, making use of strategies like constraint satisfaction and pruning to enhance the search process. Cryptarithmetic puzzles are a useful tool for exploring different algorithmic strategies in the context of C++ programming, in addition to being an entertaining intellectual exercise.