What is Crypt Arithmetic?

Crypt Arithmetic is a type of mathematical puzzle where digits are replaced by letters. Each letter represents a unique digit (0–9), and the goal is to find an assignment that makes the arithmetic equation valid.

The classic SEND+MORE=MONEY has a unique solution: S=9, E=5, N=6, D=7, M=1, O=0, R=8, Y=2.

Constraint Satisfaction Problem (CSP)

A CSP is defined by three components:

• Variables — each unique letter in the puzzle
• Domain — digits 0–9 for each variable
• Constraints — all-different digits, no leading zeros, equation must hold

The solver narrows down possibilities by propagating constraints before and during search, dramatically reducing the search space compared to brute force.

Backtracking Algorithm

Backtracking is a depth-first search with pruning. It works like this:

1. Pick the next unassigned letter
2. Try each digit in its domain
3. Check if constraints are still satisfied
4. If yes → recurse deeper; if no → backtrack
5. Continue until all letters are assigned (solution!) or all options exhausted (no solution)

Optimizations Used

• Constraint Propagation — eliminate impossible values early
• Most Constrained Variable (MCV) — assign letters in order of appearance to enable early failure detection
• Forward Checking — verify partial assignments satisfy column-wise carry constraints
• Leading Zero Pruning — immediately reject any assignment that puts 0 on a leading letter