Cryptarithmetic Puzzle In C++

Cryptarithmetic Puzzles are sometimes also called as verbal arithmetic or alphametics . In these kinds of math-based puzzles, the letters or symbols stand for numbers in an arithmetic equation. The main aim of this puzzle is to determine the right digit that will be used to form a true equation for each letter. With their captivating nature, puzzle lovers and computer scientists cannot forget this class of problems.

Problem Statement:

Consider the example: "SEND + MORE = MONEY" . Each letter represents a unique digit from 0 to 9, and the task is to find the correct assignment of digits to letters to make the equation valid. This problem falls under the category of constraint satisfaction problems, where we must satisfy a set of constraints (the arithmetic equation) subject to certain conditions (each letter representing a different digit).

Approach:

One common approach to solving cryptarithmetic puzzles is brute force enumeration combined with backtracking . We systematically try different combinations of digit assignments until a valid solution is found or all possibilities are exhausted.

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 us take an example to illustrate the cryptarithmetic puzzle using the Brute Force Backtracking 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 us take another example to illustrate the cryptarithmetic puzzle using the Constraint Satisfaction Problem in C++.

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 us take another example to illustrate the cryptarithmetic puzzle using the Constraint Propagation in C++.

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:

Cryptarithmetic puzzles not only entertain challenges but also serve as excellent exercises in problem-solving and algorithm design. Implementing a solver for these puzzles in C++ provides a hands-on opportunity to explore concepts like backtracking, permutation generation, and constraint satisfaction.

Problem Statement:

Approach:

Algorithm Overview:

Program 1: Brute Force Backtracking Implementation

Program 2: Constraint Satisfaction Problem (CSP) Implementation using OR-Tools

Program 3: Constraint Propagation Implementation

Conclusion:

Input Required