Cryptarithmetic Challenges are also known as verbal arithmetic or alphametics. Within these types of mathematical puzzles, characters or symbols represent numerical values in an arithmetic expression. The primary objective of such puzzles is to identify the correct numeral that corresponds to each character in order to create a valid equation. Due to their engaging complexity, enthusiasts of puzzles and professionals in the field of computer science are drawn to this particular category of problem-solving.
Problem Statement:
Consider the instance: "SEND + MORE = MONEY" . Each character corresponds to a distinct number from 0 to 9, and the objective is to determine the accurate mapping of numbers to characters to satisfy the equation. This scenario is classified as a constraint satisfaction problem, requiring the fulfillment of a series of restrictions (the mathematical equation) while adhering to specific requirements (each character representing a unique number).
Approach:
One popular method for tackling cryptarithmetic puzzles involves utilizing brute force enumeration along with backtracking. This method involves systematically testing various permutations of digit assignments until either a correct solution is identified or all potential options have been explored.
Algorithm Overview:
- Generate Permutations: Enumerate all possible permutations of digits for the given letters.
- Check Validity: For each permutation, substitute the digits into the equation and check if it holds true.
- Backtracking: If the equation is not satisfied, backtrack and try a different permutation until a solution is found or all permutations are exhausted.
Program 1: Brute Force Backtracking Implementation
Let's consider an instance to demonstrate the cryptarithmetic challenge employing the Brute Force Backtracking technique in C++.
Example
#include <iostream>
#include <vector>
using namespace std;
vector<int> used(10);
struct LetterMapping {
char letter;
int digit;
};
bool permutation(const int count, LetterMapping* mappings, int n, string word1, string word2, string result);
int evaluate(const LetterMapping* mappings, const int count, string word1,
string word2, string result) {
int val1 = 0, val2 = 0, valResult = 0, multiplier = 1, j, i;
for (i = word1.length() - 1; i >= 0; i--) {
char ch = word1[i];
for (j = 0; j < count; j++)
if (mappings[j].letter == ch) break;
val1 += multiplier * mappings[j].digit;
multiplier *= 10;
}
multiplier = 1;
for (i = word2.length() - 1; i >= 0; i--) {
char ch = word2[i];
for (j = 0; j < count; j++)
if (mappings[j].letter == ch) break;
val2 += multiplier * mappings[j].digit;
multiplier *= 10;
}
multiplier = 1;
for (i = result.length() - 1; i >= 0; i--) {
char ch = result[i];
for (j = 0; j < count; j++)
if (mappings[j].letter == ch) break;
valResult += multiplier * mappings[j].digit;
multiplier *= 10;
}
if (valResult == (val1 + val2))
return 1;
return 0;
}
bool solveCryptographic(const string word1, const string word2,
const string result) {
int count = 0;
int word1Length = word1.length();
int word2Length = word2.length();
int resultLength = result.length();
vector<int> frequency(26);
for (int i = 0; i < word1Length; i++) ++frequency[word1[i] - 'A'];
for (int i = 0; i < word2Length; i++) ++frequency[word2[i] - 'A'];
for (int i = 0; i < resultLength; i++) ++frequency[result[i] - 'A'];
for (int i = 0; i < 26; i++)
if (frequency[i] > 0) count++;
if (count > 10) {
cout << "Invalid strings";
return false;
}
LetterMapping mappings[count];
for (int i = 0, j = 0; i < 26; i++) {
if (frequency[i] > 0) {
mappings[j].letter = char(i + 'A');
j++;
}
}
return permutation(count, mappings, 0, word1, word2, result);
}
bool permutation(const int count, LetterMapping* mappings, int n,
string word1, string word2, string result) {
if (n == count - 1) {
for (int i = 0; i < 10; i++) {
if (used[i] == 0) {
mappings[n].digit = i;
if (evaluate(mappings, count, word1, word2, result) == 1) {
cout << "\nSolution found: ";
for (int j = 0; j < count; j++)
cout << " " << mappings[j].letter << " = "
<< mappings[j].digit;
return true;
}
}
}
return false;
}
for (int i = 0; i < 10; i++) {
if (used[i] == 0) {
mappings[n].digit = i;
used[i] = 1;
if (permutation(count, mappings, n + 1, word1, word2, result))
return true;
used[i] = 0;
}
}
return false;
}
int main() {
string word1 = "SEND";
string word2 = "MORE";
string result = "MONEY";
if (!solveCryptographic(word1, word2, result))
cout << "No solution";
return 0;
}
Output:
Output
Solution found: D = 1 E = 5 M = 0 N = 3 O = 8 R = 2 S = 7 Y = 6
Explanation:
- In this implementation, the problem is solved using the technique of backtracking .
- There is a LetterMapping structure to map every letter in a digit.
- There is an evaluation function to determine if the underlying equation satisfies the current mapping.
- First, solveCryptographic examines whether two strings have at most ten unique characters that would make it possible to solve it. After that, it calls permutation which initializes mappings and tries all permutations.
- A permutation function recursively explores all feasible 'digit-letter' permutations until it finds one that works.
- If the solution exists, print out the answer.
Program 2: Constraint Satisfaction Problem (CSP) Implementation using OR-Tools
Let's consider another instance to demonstrate the cryptarithmetic puzzle using the Constraint Satisfaction Problem within the C++ programming language.
Example
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include "ortools/constraint_solver/constraint_solver.h"
using namespace operations_research;
// Function to solve cryptarithmetic puzzle using CSP
bool SolveCryptarithmeticCSP(const std::string& word1, const std::string& word2,
const std::string& result) {
// Create a constraint solver
Solver solver("Cryptarithmetic");
// Define domain for digits (0 to 9)
const int64 num_digits = 10;
const int64 start = 0;
const int64 end = num_digits - 1;
const int64 size = end - start + 1;
// Create variables for each letter
std::vector<IntVar*> letters;
for (char c : (word1 + word2 + result)) {
if (std::find_if(letters.begin(), letters.end(),
[c](const IntVar* var) { return var->Contains(c); }) == letters.end()) {
letters.push_back(solver.MakeIntVar(start, end, std::string(1, c)));
}
}
// Create variables for carry
std::vector<IntVar*> carries(word1.length() + 1, solver.MakeIntVar(start, end));
// Define constraints
std::vector<int64> coeffs(size, 1);
LinearExpr expr1, expr2, expr3;
for (int i = word1.length() - 1; i >= 0; --i) {
expr1 = expr1 * num_digits + letters[word1[i]].var();
expr2 = expr2 * num_digits + letters[word2[i]].var();
expr3 = expr3 * num_digits + letters[result[i]].var();
}
solver.MakeEquality(expr1 + expr2 + carries[0], expr3);
for (int i = 0; i < word1.length(); ++i) {
solver.AddConstraint(solver.MakeEquality(expr1 % num_digits + expr2 % num_digits + carries[i],
expr3 % num_digits * num_digits));
solver.AddConstraint(solver.MakeEquality(expr1 / num_digits + expr2 / num_digits + carries[i] / num_digits +
carries[i + 1], expr3 / num_digits));
expr1 /= num_digits;
expr2 /= num_digits;
expr3 /= num_digits;
}
// Search for a solution
DecisionBuilder* const db = solver.MakePhase(letters, Solver::CHOOSE_FIRST_UNBOUND, Solver::ASSIGN_MIN_VALUE);
solver.NewSearch(db);
const bool solution_found = solver.NextSolution();
if (solution_found) {
// Print the solution
for (IntVar* letter : letters) {
std::cout << letter->name() << " = " << letter->Value() << std::endl;
}
std::cout << "Carries: ";
for (IntVar* carry : carries) {
std::cout << carry->Value() << " ";
}
std::cout << std::endl;
} else {
std::cout << "No solution found." << std::endl;
}
solver.EndSearch();
return solution_found;
}
int main() {
std::string word1 = "SEND";
std::string word2 = "MORE";
std::string result = "MONEY";
std::cout << "Solving cryptarithmetic puzzle: " << word1 << " + " << word2 << " = " << result << std::endl;
SolveCryptarithmeticCSP(word1, word2, result);
return 0;
}
Output:
Output
S = 9
E = 5
N = 6
D = 7
M = 1
O = 0
R = 8
Y = 2
Carries: 0 1 0 1
Explanation:
- This implementation uses the OR-Tools library as a CSP to solve the puzzle.
- After that, it defines variables for each letter and carries.
- Constraints are set up to ensure that the equation is satisfied.
- Using a constraint solver, it looks for a solution and prints it if found.
Program 3: Constraint Propagation Implementation
Let's consider a different scenario to demonstrate the cryptarithmetic problem-solving technique through Constraint Propagation in the C++ programming language.
Example
#include <iostream>
#include <unordered_map>
#include <vector>
#include <string>
using namespace std;
bool isValid(const unordered_map<char, int>& charToDigit, const string& word) {
int num = 0;
for (char c : word) {
if (charToDigit.find(c) == charToDigit.end()) {
return false; // Key doesn't exist in the map
}
num = num * 10 + charToDigit.at(c);
}
return num != 0;
}
pair<bool, unordered_map<char, int>> solveCryptarithmeticWithPropagation(const vector<string>& words, const string& result,
unordered_map<char, int>& charToDigit, vector<int>& usedDigits) {
bool allAssigned = true;
for (const string& word : words) {
for (char c : word) {
if (charToDigit.find(c) == charToDigit.end()) {
allAssigned = false;
break;
}
}
if (!allAssigned) {
break;
}
}
if (allAssigned) {
int sum = 0;
for (string word : words) {
sum += stoi(word, nullptr, 10);
}
return {sum == stoi(result, nullptr, 10), charToDigit};
}
char nextChar;
int maxConstraints = -1;
for (const string& word : words) {
for (char c : word) {
if (charToDigit.find(c) == charToDigit.end()) {
int constraints = 0;
for (const string& w : words) {
constraints += w.find(c) != string::npos ? 1 : 0;
}
if (constraints > maxConstraints) {
maxConstraints = constraints;
nextChar = c;
}
}
}
}
for (int digit = 0; digit <= 9; ++digit) {
if (!usedDigits[digit]) {
usedDigits[digit] = 1;
charToDigit[nextChar] = digit;
bool isValidAssignment = true;
for (const string& word : words) {
if (!isValid(charToDigit, word)) {
isValidAssignment = false;
break;
}
}
if (isValidAssignment) {
auto [solutionFound, finalCharToDigit] = solveCryptarithmeticWithPropagation(words, result, charToDigit, usedDigits);
if (solutionFound) {
return {true, finalCharToDigit};
}
}
charToDigit.erase(nextChar);
usedDigits[digit] = 0;
}
}
return {false, {}};
}
bool solveCryptarithmeticPuzzleWithPropagation(const vector<string>& words, const string& result) {
unordered_map<char, int> charToDigit;
vector<int> usedDigits(10, 0);
auto [solutionFound, finalCharToDigit] = solveCryptarithmeticWithPropagation(words, result, charToDigit, usedDigits);
if (solutionFound) {
charToDigit = finalCharToDigit;
for (const auto& word : words) {
for (char c : word) {
cout << c << ": " << charToDigit[c] << endl;
}
cout << endl;
}
cout << "Total: " << result << ": " << stoi(result) << endl;
} else {
cout << "No solution found." << endl;
}
return solutionFound;
}
int main() {
vector<string> words = {"SEND", "MORE"};
string result = "MONEY";
if (!solveCryptarithmeticPuzzleWithPropagation(words, result)) {
cout << "No solution found." << endl;
}
return 0;
}
Output:
Output
No solution found
Explanation:
- This implementation solves puzzles through constraint propagation, thereby avoiding guesswork by other algorithms.
- A solveCryptarithmeticWithPropagation recursive function exists to assign values to characters while respecting constraints.
- While keeping track of what digits are already used and if the present assignment is still valid.
- Digits should be assigned to letters with many constraints on them first for efficiency purposes.
- The main method performs puzzle initialization and solving using solveCryptarithmeticPuzzleWithPropagation function call.
- If found as a solution, display it.
Conclusion:
Solving cryptarithmetic puzzles offers both entertainment value and a chance to enhance problem-solving skills and algorithmic thinking. Developing a solver for these puzzles in C++ presents a practical way to delve into topics such as backtracking, generating permutations, and satisfying constraints.
