liveBook · Manning

Cryptarithmetic puzzle

As explained in Classic Computer Science Problems in Swift: Essential techniques for practicing programmers

A mathematical puzzle in which letters represent digits and an arithmetic statement must be made true subject to digit-assignment constraints.

A cryptarithmetic puzzle replaces letters with digits so an arithmetic statement becomes true. Each letter represents one digit, repeated letters retain their digit, and different letters cannot share a digit. section 3.5

SEND + MORE = MONEY

Line up the words as an addition problem, assign digits to S, E, N, D, M, O, R, and Y, and test whether the resulting numbers satisfy the equation. One solution is 9567 + 1085 = 10652. section 3.5

As a constraint-satisfaction problem, the solver searches assignments incrementally. It rejects duplicate digits, accepts valid partial assignments for continued search, and checks the arithmetic equation once every letter is assigned. section 3.5

A genetic algorithm uses a different representation: array indices stand for digits, while array entries hold letters. Its fitness improves as the numerical difference between the two sides decreases. section 5.5

How Classic Computer Science Problems in Swift: Essential techniques for practicing programmers covers it

How deep it goes
Explains digit constraints, validation stages, chromosome representation, and fitness calculation, but does not develop formal proofs.
Examples
Uses SEND+MORE=MONEY, its aligned addition layout, a digit assignment, Swift CSP code, and genetic-algorithm output.
What it assumes
Assumes basic programming and arithmetic while defining digit assignment, uniqueness, partial solutions, and fitness through the puzzle.
What you can do after
Apply it via backtracking search or a genetic algorithm to solve SEND+MORE=MONEY in Swift.
How it connects
Connects cryptarithmetic puzzles to constraint-satisfaction problems, backtracking search, genetic algorithms, and fitness functions.

Related concepts

This explainer was generated by Manning's knowledge graph from the text of Classic Computer Science Problems in Swift: Essential techniques for practicing programmers. The section links point to the parts of the book it draws on.