# Cryptarithmetic

### From charlesreid1

Cryptarithmetic example:

CP + IS + FUN -------- = TRUE

The challenge is to find integers to swap out for each letter such that the equation holds true. This is a constrained programming problem, and can be re-cast in terms of an arbitrary radix as follows:

The "thousands" place has nothing on the left side, and a on the right side.

The "hundreds" place has an on the left side and a on the right side.

The "tens" place becomes the expression on the left side and on the right.

The "ones" place becomes the expression on the left and on the right, which, combining, gives:

where r is the radix.

We can also limit the search space by constraining C, I, F, T to be nonzero.

We have 10 letters total, CPISFUNTRE, and of those 6 that are possibly (0 through base) and 4 which are possibly (1 through base), for a total search space of

For radix 10, that's:

which puts this problem squarely in the ballpark of problem sizes that can be solved. In particular, this constrained programming approach can be solved using a Combinatorics and Heuristics-based method. While this problem may have some local structure to the digit relationships, they are complicated - so we can treat this solution space as random. There are also many solutions - 72 solutions, to be exact.

Can also use Google's Operations Research (optimization tools) package: https://developers.google.com/optimization/puzzles/cryptarithmetic