Solving Cryptarithmetic Puzzles Hard 0 attempts
GeeksforGeeks ↗

Solving Cryptarithmetic Puzzles

Hard BacktrackingRecursion GeeksforGeeks

In a cryptarithmetic puzzle, every letter in an arithmetic expression stands for one fixed, unique digit from 0 through 9, and no word may begin with a letter mapped to 0. Given the addends as a string array words and the result as a string result, such as ["SEND", "MORE"] and "MONEY", work out a digit-to-letter mapping that makes the arithmetic correct.

Edge cases: If no mapping satisfies the equation, return null. Since only 10 digits are available, a puzzle can involve at most 10 distinct letters.

Input Format
Implement solveCryptarithmetic(words, result). Inputs below show JavaScript function arguments; there is no stdin parsing.
Output Format
Return the result described in the statement. Any result satisfying the statement is accepted.

Sample Input and Output

Example 1 · Run Sample

Input
words = ["SEND","MORE"]
result = "MONEY"
Output
{"S":9,"E":5,"N":6,"D":7,"M":1,"O":0,"R":8,"Y":2}

Example 2

Input
words = ["A","B"]
result = "AA"
Output
null
Constraints
  • 1 <= words.length <= 5
  • 1 <= words[i].length, result.length <= 20
  • All characters are uppercase English letters.
  • At most 10 distinct letters occur across all words.
  • Every leading letter must map to a non-zero digit.
Test Cases (2)
Case 1
Args: [["SEND","MORE"],"MONEY"] Expected: {"S":9,"E":5,"N":6,"D":7,"M":1,"O":0,"R":8,"Y":2}
Case 2
Args: [["A","B"],"AA"] Expected: null
Topics
BacktrackingRecursion

Approach: Column-by-Column Backtracking

Work from the units column toward the left. Assign unused digits to the addend letters, then enforce the result digit and carry immediately. Repeated letters reuse their assigned digit. Reject zero for leading letters. This prunes invalid assignments before completing the whole mapping and avoids converting long words to JavaScript numbers.

javascript
function solveCryptarithmetic(words, result) {
  const letters = [...new Set(words.join('') + result)];
  if (letters.length > 10) return null;
  const leading = new Set([...words.map(w => w[0]), result[0]]);
  const assignment = {}, used = new Set();
  const width = Math.max(result.length, ...words.map(w => w.length));
  function column(col, row, sum) {
    if (col === width) return sum === 0;
    if (row < words.length) {
      const word = words[row], ch = word[word.length - 1 - col];
      if (!ch) return column(col, row + 1, sum);
      if (assignment[ch] !== undefined) return column(col, row + 1, sum + assignment[ch]);
      for (let d = leading.has(ch) ? 1 : 0; d <= 9; d++) {
        if (used.has(d)) continue;
        assignment[ch] = d; used.add(d);
        if (column(col, row + 1, sum + d)) return true;
        delete assignment[ch]; used.delete(d);
      }
      return false;
    }
    const ch = result[result.length - 1 - col];
    if (!ch) return sum === 0 && column(col + 1, 0, 0);
    const digit = sum % 10, carry = Math.floor(sum / 10);
    if (assignment[ch] !== undefined) return assignment[ch] === digit && column(col + 1, 0, carry);
    if (used.has(digit) || (digit === 0 && leading.has(ch))) return false;
    assignment[ch] = digit; used.add(digit);
    if (column(col + 1, 0, carry)) return true;
    delete assignment[ch]; used.delete(digit);
    return false;
  }
  return column(0, 0, 0) ? { ...assignment } : null;
}

Time Complexity: O(L × 10! / (10-U)!) as a loose upper bound, where U is the number of unique letters and L is the total input length

Space Complexity: O(L + U) for recursion and the assignment map

Saved in this browser only. Private to you.

JavaScript