Log inSign up
hardGeeksforGeeksNot Started

Cryptarithmetic Puzzle

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Backtracking
Solve on GeeksforGeeks
Lesson

Problem Statement

A Cryptarithmetic Puzzle is an arithmetic game where digits are replaced by letters of the alphabet.

Given three words: word1, word2, and result, determine if there exists a valid one-to-one mapping from each unique character to a unique decimal digit from 0 to 9 such that: 1. decode(word1) + decode(word2) == decode(result) 2. No word has a leading zero (unless the word is a single letter '0'). 3. Each distinct character maps to a unique digit.

Return the valid character-to-digit mapping dictionary/map, or return boolean true/false indicating whether a solution exists.

Example 1 · Classic SEND + MORE = MONEY:

Input: word1 = "SEND", word2 = "MORE", result = "MONEY"
Output: {'S': 9, 'E': 5, 'N': 6, 'D': 7, 'M': 1, 'O': 0, 'R': 8, 'Y': 2}
Explanation: 9567 + 1085 = 10652. All digits are unique, and leading letters S=9 and M=1 are non-zero.

Example 2 · Simple BASE + BALL = GAMES:

Input: word1 = "BASE", word2 = "BALL", result = "GAMES"
Output: {'B': 7, 'A': 4, 'S': 8, 'E': 3, 'L': 5, 'G': 1, 'M': 9}
Explanation: 7483 + 7455 = 14938. Equation holds true.

Constraints:

  • 1 <= word1.length, word2.length, result.length <= 10
  • Total unique characters across all 3 words <= 10.
  • Words consist solely of uppercase English letters.

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Master bijective constraint satisfaction backtracking.
  • Understand search tree pruning with leading zero constraints.
  • Learn column-by-column carry verification for large scale cryptarithmetic problems.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Arithmetic equation with letters representing digits
  • One-to-one (bijective) mapping constraint between symbols and digits 0..9
  • Total unique letters <= 10

Algorithmic Decision Tree:

  • Collect all unique characters from the input words.
  • If unique characters count > 10, return impossible (more letters than available decimal digits).
  • Recursively assign each unused digit from 0 to 9 to the current unassigned character.
  • Enforce leading letter constraint (digit != 0 for initial characters).

Connected Patterns:

Sudoku SolverN-QueensPermutations

1. Permutation Library Generator with Full Eval

Intuition

Extract all U unique characters. Generate all permutations of length U from digits [0..9]. For each permutation, construct candidate mapping, check leading zero conditions, compute number values, and check if val(w1) + val(w2) == val(res).

When to apply: Baseline approach in Python/C++ utilizing itertools.permutations or std::next_permutation.

Algorithm

  1. Extract list of unique characters chars.
  2. Generate all permutations of digits 0..9 of length chars.length.
  3. For each permutation, assign digits to characters.
  4. If leading characters map to 0, continue.
  5. If num(word1) + num(word2) == num(result), return valid mapping.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4#include <unordered_map>
5#include <unordered_set>
6#include <algorithm>
7#include <numeric>
8
9using namespace std;
10
11class Solution {
12 long long getVal(const string& w, const unordered_map<char, int>& map) {
13 long long val = 0;
14 for (char c : w) val = val * 10 + map.at(c);
15 return val;
16 }
17
18public:
19 bool solveCryptarithm(string w1, string w2, string res, unordered_map<char, int>& result) {
20 unordered_set<char> charSet;
21 for (char c : w1) charSet.insert(c);
22 for (char c : w2) charSet.insert(c);
23 for (char c : res) charSet.insert(c);
24
25 if (charSet.size() > 10) return false;
26
27 vector<char> chars(charSet.begin(), charSet.end());
28 int u = chars.size();
29 vector<int> digits = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
30
31 // Check all permutations
32 do {
33 unordered_map<char, int> map;
34 for (int i = 0; i < u; i++) map[chars[i]] = digits[i];
35
36 if (map[w1[0]] == 0 || map[w2[0]] == 0 || map[res[0]] == 0) continue;
37
38 if (getVal(w1, map) + getVal(w2, map) == getVal(res, map)) {
39 result = map;
40 return true;
41 }
42 } while (next_permutation(digits.begin(), digits.end()));
43
44 return false;
45 }
46};
47
48int main() {
49 Solution sol;
50 unordered_map<char, int> res;
51 if (sol.solveCryptarithm("SEND", "MORE", "MONEY", res)) {
52 for (auto p : res) cout << p.first << ": " << p.second << " ";
53 cout << endl;
54 }
55 return 0;
56}

Time & Space Complexity

  • Time complexity: O(P(10, U) * L) — P(10, U) is 10! / (10 - U)!. For U = 8 (like SEND MORE MONEY), P(10, 8) = 1,814,400 permutations. L is word length.
  • Space complexity: O(U) — Stores unique characters and permutation buffer.

2. Recursive Backtracking with Leading-Zero Pruning

Intuition

Track leading characters in a hash set. During digit assignment, if the current character is a leading character, immediately skip digit 0. This prunes 10% of search branches at the very top level of the recursion tree.

When to apply: Standard recursive search approach with clean state unwinding.

Algorithm

  1. Find unique characters and identify leading letters.
  2. In backtrack(charIndex):
  3. - If charIndex == chars.length: evaluate num(w1) + num(w2) == num(res).
  4. - For digit 0..9:
  5. - If digit == 0 and character is leading, continue.
  6. - If digit is unused, map character to digit and recurse.
  7. - Backtrack: unmark digit.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4#include <unordered_map>
5#include <unordered_set>
6
7using namespace std;
8
9class Solution {
10 long long getVal(const string& w, const unordered_map<char, int>& map) {
11 long long val = 0;
12 for (char c : w) val = val * 10 + map.at(c);
13 return val;
14 }
15
16 bool backtrack(int idx, const vector<char>& chars, const unordered_set<char>& leading,
17 unordered_map<char, int>& map, vector<bool>& used,
18 const string& w1, const string& w2, const string& res) {
19 if (idx == chars.size()) {
20 return getVal(w1, map) + getVal(w2, map) == getVal(res, map);
21 }
22
23 char c = chars[idx];
24 for (int d = 0; d <= 9; d++) {
25 if (!used[d]) {
26 if (d == 0 && leading.count(c)) continue; // Prune leading zero
27
28 used[d] = true;
29 map[c] = d;
30
31 if (backtrack(idx + 1, chars, leading, map, used, w1, w2, res)) return true;
32
33 map.erase(c);
34 used[d] = false;
35 }
36 }
37 return false;
38 }
39
40public:
41 unordered_map<char, int> solve(string w1, string w2, string res) {
42 unordered_set<char> charSet(w1.begin(), w1.end());
43 charSet.insert(w2.begin(), w2.end());
44 charSet.insert(res.begin(), res.end());
45
46 if (charSet.size() > 10) return {};
47
48 vector<char> chars(charSet.begin(), charSet.end());
49 unordered_set<char> leading = {w1[0], w2[0], res[0]};
50 unordered_map<char, int> map;
51 vector<bool> used(10, false);
52
53 if (backtrack(0, chars, leading, map, used, w1, w2, res)) return map;
54 return {};
55 }
56};
57
58int main() {
59 Solution sol;
60 auto map = sol.solve("SEND", "MORE", "MONEY");
61 for (auto p : map) cout << p.first << " -> " << p.second << ", ";
62 cout << endl;
63 return 0;
64}

Time & Space Complexity

  • Time complexity: O(P(10, U) * L) — Pruning leading zero skips 1/10th of root permutations.
  • Space complexity: O(U) — Call stack depth is bounded by U <= 10.

3. Column-by-Column Right-to-Left Arithmetic Constraint Backtracking (Optimal)

Intuition

Align words by columns right-to-left. At column col (units, tens, etc.), assign digits to w1[col], w2[col], and verify with res[col] and carry: (d1 + d2 + carry) % 10 == d_res and new_carry = (d1 + d2 + carry) / 10. Any invalid assignment fails immediately at column 1 without exploring deeper columns.

When to apply: The state-of-the-art optimal constraint satisfaction engine approach for cryptarithmetic puzzles.

Algorithm

  1. Align word1, word2, and result from right to left.
  2. Backtrack on (column, row, carry):
  3. - If finished all columns, check carry == 0 and leading zero conditions.
  4. - If current character is already assigned, proceed with assigned digit.
  5. - If unassigned, iterate through unused digits (1..9 for leading, 0..9 otherwise).
  6. - Verify column sum constraint when row reaches result character.

Column-by-Column Carry Constraint Trace

2 of 2 questions left today
Step 1 / 5
Trace timeline20% explored
Current operationSTEP 1 OF 5
Column 0 (Units place): D + E = Y + 10carry1
Visual state
Values and pointers at this exact step
table
S
D(7) + E(5) = Y(2) [c:1]
0
col0
mapped{"D":7,"E":5,"Y":2}
carry1
Variables at this step
col
0
mapped
{"D":7,"E":5,"Y":2}
carry
1
Why this step matters

Column 0 (Units place): D + E = Y + 10*carry1. Assign D=7, E=5 -> Sum = 12 -> Y=2, carry1=1.

Step 1 / 5
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4#include <unordered_map>
5#include <unordered_set>
6
7using namespace std;
8
9class Solution {
10 bool solveCol(int col, int row, int carry,
11 const vector<string>& words, const string& result,
12 unordered_map<char, int>& map, vector<bool>& used,
13 const unordered_set<char>& leading) {
14 int maxLen = result.length();
15 if (col == maxLen) {
16 return carry == 0;
17 }
18
19 // Processing word1 and word2
20 if (row < words.size()) {
21 string w = words[row];
22 int idx = w.length() - 1 - col;
23 if (idx < 0) {
24 // No character in this column for this word
25 return solveCol(col, row + 1, carry, words, result, map, used, leading);
26 }
27
28 char c = w[idx];
29 if (map.count(c)) {
30 return solveCol(col, row + 1, carry + map[c], words, result, map, used, leading);
31 }
32
33 for (int d = 0; d <= 9; d++) {
34 if (!used[d]) {
35 if (d == 0 && leading.count(c)) continue;
36 used[d] = true;
37 map[c] = d;
38 if (solveCol(col, row + 1, carry + d, words, result, map, used, leading)) return true;
39 map.erase(c);
40 used[d] = false;
41 }
42 }
43 return false;
44 }
45
46 // Processing result word at column col
47 int resIdx = result.length() - 1 - col;
48 char resChar = result[resIdx];
49 int expectedDigit = carry % 10;
50 int nextCarry = carry / 10;
51
52 if (map.count(resChar)) {
53 if (map[resChar] == expectedDigit) {
54 return solveCol(col + 1, 0, nextCarry, words, result, map, used, leading);
55 }
56 return false;
57 }
58
59 if (!used[expectedDigit]) {
60 if (expectedDigit == 0 && leading.count(resChar)) return false;
61 used[expectedDigit] = true;
62 map[resChar] = expectedDigit;
63 if (solveCol(col + 1, 0, nextCarry, words, result, map, used, leading)) return true;
64 map.erase(resChar);
65 used[expectedDigit] = false;
66 }
67
68 return false;
69 }
70
71public:
72 unordered_map<char, int> solveCryptarithm(string w1, string w2, string res) {
73 unordered_map<char, int> map;
74 vector<bool> used(10, false);
75 unordered_set<char> leading = {w1[0], w2[0], res[0]};
76 vector<string> words = {w1, w2};
77
78 if (solveCol(0, 0, 0, words, res, map, used, leading)) return map;
79 return {};
80 }
81};
82
83int main() {
84 Solution sol;
85 auto map = sol.solveCryptarithm("SEND", "MORE", "MONEY");
86 for (auto p : map) cout << p.first << " = " << p.second << ", ";
87 cout << endl;
88 return 0;
89}

Time & Space Complexity

  • Time complexity: O(P(10, U) with massive early branch pruning) — Column-level arithmetic validation eliminates non-viable paths in early columns, evaluating a tiny fraction of full permutations.
  • Space complexity: O(U) — Recursion depth is proportional to total characters across words.

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Permutation Library GeneratorO(P(10, U) * L)O(U)Generate all permutations of digits and evaluate whole equation.P(10, U) search space size
2.Recursive Backtracking with Leading-Zero PruningO(P(10, U) * L)O(U)Sequential character assignment with leading zero check.Leaf node evaluation
3.Column-by-Column Arithmetic BacktrackingOptimalO(P(10, U) with massive pruning)O(U)Validate column addition and carry from units column upwards.Column transition state management

Common Pitfalls & Crucial Edge Cases

Pitfall 1:

Allowing leading letters of any word to be assigned digit 0.

Pitfall 2:

Assigning the same digit to multiple distinct letters (violating bijective mapping).

Pitfall 3:

Not handling carry properly across column boundaries.

Crucial Edge Cases to Validate:

  • More than 10 Unique Characters: returns empty map / false immediately.
  • Single Letter Words: A + B = C -> valid mappings like A=1, B=2, C=3.
  • Result Length Greater by More than 1: result length can exceed word length by at most 1 (since max carry from 2 digits is 1).

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Mention the constraint satisfaction problem (CSP) nature of cryptarithmetic.
  2. Discuss why right-to-left column-by-column pruning is vastly superior to whole-word evaluation.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.Why can a valid cryptarithmetic addition puzzle have at most 10 unique letters?

2.Why is column-by-column right-to-left verification faster than assigning all letters first?

Back to DSA Sheet