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:

$ F r^2 + (C+I+U) r + (P+S+N) = T r^3 + R r^2 + U r + 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