Solving Cryptarithmetic Puzzles Hard 0 attempts
GeeksforGeeks ↗

Solving Cryptarithmetic Puzzles

Hard BacktrackingRecursion GeeksforGeeks

A cryptarithmetic puzzle replaces digits with letters in an arithmetic equation. Each letter stands for a unique digit (0–9), and the leading letter of any word cannot be zero. Given an equation like SEND + MORE = MONEY, find a digit assignment that satisfies it.

Example 1:

Input: "SEND + MORE = MONEY"
Output: {S:9, E:5, N:6, D:7, M:1, O:0, R:8, Y:2}
Explanation: 9567 + 1085 = 10652

Example 2:

Input: "TWO + TWO = FOUR"
Output: {T:7, W:3, O:4, F:1, U:6, R:8}
Explanation: 734 + 734 = 1468

Edge cases: No valid assignment exists (return null or indicate no solution). Up to 10 unique letters is the maximum since there are only 10 digits.

Sample Input
SEND + MORE = MONEY
Sample Output
S=9, E=5, N=6, D=7, M=1, O=0, R=8, Y=2
Constraints
  • Each word has at most 10 unique characters
  • Total unique characters <= 10
Topics
BacktrackingRecursion

Approach: Backtracking with Constraint Checking

Extract all unique letters, then try assigning each an unused digit via backtracking. After all letters are assigned, check if the equation holds. Prune by enforcing the leading-letter-not-zero constraint early.

function solveCryptarithmetic(words, result) {
  const letters = [...new Set([...words.join(''), ...result])];
  const leadingLetters = new Set([...words.map(w => w[0]), result[0]]);
  const assignment = {};
  const usedDigits = new Set();

  function wordToNum(word) {
    return word.split('').reduce((acc, ch) => acc * 10 + assignment[ch], 0);
  }

  function solve(idx) {
    if (idx === letters.length) {
      const sum = words.reduce((acc, w) => acc + wordToNum(w), 0);
      return sum === wordToNum(result);
    }

    const letter = letters[idx];
    const start = leadingLetters.has(letter) ? 1 : 0;

    for (let d = start; d <= 9; d++) {
      if (usedDigits.has(d)) continue;
      assignment[letter] = d;
      usedDigits.add(d);
      if (solve(idx + 1)) return true;
      usedDigits.delete(d);
      delete assignment[letter];
    }
    return false;
  }

  if (solve(0)) return { ...assignment };
  return null;
}

Time Complexity: O(10! / (10-n)!) where n is the number of unique letters

Space Complexity: O(n) for recursion and the assignment map

Saved in this browser only. Private to you.

JavaScript