About Cryptarithm Calculator

A cryptarithm is a type of mathematical puzzle where the digits in an arithmetic calculation are replaced with letters. The arithmetic operation is usually addition, although many puzzles include subtraction, multiplication, or rarely division. The goal is to find the correct digit for each letter, ensuring the calculation is valid.

For example, in the classic puzzle SEND + MORE = MONEY, each letter represents a unique digit from 0-9, and we need to figure out which digit each letter represents.

How The Calculator Works

Medium Mode: Constraint Satisfaction Problem (CSP)

The CSP approach uses intelligent search techniques with constraint heuristics to efficiently find solutions:

Each letter is a variable with a domain of possible digits (0-9)
Constraints ensure each letter maps to a unique digit
The arithmetic operation must be valid with the assigned digits
First letters cannot be zero (we can't have leading zeros)

This implementation uses backtracking with forward checking and the Minimum Remaining Values (MRV) heuristic to efficiently search the solution space.

Note: The CSP approach outperforms Brute Force enumeration for most practical cryptarithms, though Brute Force can be faster for very small puzzles due to CSP overhead. We exclude Brute Force here as it doesn't scale well with puzzle complexity. I can add the performance test comparison if wanted.

Hard Mode: Machine Learning Enhanced

For complex puzzles, we use a machine learning model to predict solvability before attempting to solve:

Features are extracted from the cryptarithm structure
A trained Random Forest classifier predicts if a solution exists
This helps avoid wasting time on unsolvable puzzles

If the ML model indicates the puzzle is solvable, we still use the CSP solver to find the actual solution.

Note: Cryptarithm solving is an NP-complete problem, meaning no poly-time algorithm exists to solve it. The ML approach allows us to identify potentially solvable instances before using exponential time on a search of the solution space of a invalid instance.

Project Information

This is a work in progress and is not yet complete. I plan to add more features such as an interactive performance comparison and add AC3 (Arc Consistency) to Medium Mode.