Cryptarithmetic

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 ${\mbox{T}}$ on the right side.

The "hundreds" place has an $F$ on the left side and a ${\mbox{R}}$ on the right side.

The "tens" place becomes the expression $(C+I+U)\times base$ on the left side and $U\times base$ on the right.

The "ones" place becomes the expression $P+S+N$ on the left and $E$ on the right, which, combining, gives:

$Fr^{2}+(C+I+U)r+(P+S+N)=Tr^{3}+Rr^{2}+Ur+E$

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

$b^{6}(b-1)^{4}$

For radix 10, that's:

$10^{6}\times 9^{4}=6,561,000,000=6.56\times 10^{9}$

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