It’s a rainy bank holiday in Northumberland.
Cryptoarithmetic also called alphametics is a family of math puzzles where you figure out the unknown digits in a given group of arithmetic operations.
ME plus ME equals BEE
This is a simple example: \(ME+ME=BEE\) where \(\{M, E, B\in i|0\leq i\leq 9,i\in\mathbb{Z}\}\). In other words, all the terms are integers between \(0\) and \(9\) inclusive, i.e. decimal digits.
The trouble is, my inclination on seeing such problems is not to directly solve them but rather to “solve for the solver.” My mind instantly leaps to wondering what the solver would look like, how it would work by abstracting away to the meta-problem: the problem of the problem. Is that laziness? Maybe a long time in software engineering focuses the mind on that approach. If the developer can construct a solver then solutions to all problems become generically trivial.
The Solver
Prolog is a very useful tool for this type of problem-solving. Most Prolog implementations equip a CLP(FD) module—short for Constraint Logic Programming over Finite Domains. So our quest to solve for the solver will utilise CLP(FD).
First, we need a relation between digits and integers. This might seem a little redundant. The relation is obvious and implicit, is it not? \(123\) is one hundred and twenty-three, surely. What does that really mean though? Actually not obvious, not without adding a slew of assumptions. Decimal is the first assumption. \(123\) is also \(291\) if hexadecimal is the radix, for instance. We naturally apply a digit constraint without thinking about it: digit \(d\in0\dots9,\mathbb{Z}\).
When we logically decompose the decimal \(123\) what we really mean is \(1\times10^2 + 2\times10^1 + 3\times10^0\). Hence the column position adds an implied exponent. In logic, therefore, an arbitrary sequence of decimal digits carries an implied base-10 exponential relation.
What we are saying, logically, by “\(123\)” or any other decimal sequence amounts to dig([1, 2, 3], 123) where the dig relation is:
dig([Digit], Integer0, Integer) :-
Digit in 0..9,
Integer #= Integer0 * 10 + Digit,
!.
dig([Digit|Digits], Integer0, Integer) :-
dig([Digit], Integer0, Integer_),
dig(Digits, Integer_, Integer).This is a simple Prolog predicate that captures the recursive relation between digits and their integer value. The predicate uses a trailing underscore to denote intermediate prime variables and reuses itself to factor out the common multiply and add relation. It uses an accumulator approach. Digits appear as the first argument in order to assist unification and an initial accumulator Integer0 unifies with some initial accumulated value. The bang is important because it solves for one digit without backtracking1.
Arity-2
In practice, the initial accumulated value always equals \(0\) so we can add a second arity-22 predicate to supply the initial value. The implementation below also swaps the argument order so that it reads more naturally as dig(123, [One, Two, Three]).
dig(Integer, Digits) :- dig(Digits, 0, Integer).We can now express any decimal-digit relation combining arbitrary knowns and unknowns.
“There are unknown unknowns.”—Donald Rumsfeld, 2002
Querying dig/2 with an Integer of \(123\) gives:
?- dig(123, [One, Two, Three]).
One = 1,
Two = 2,
Three = 3.Additional CLP
Now that we can abstract the implied digital logic, we can add the higher-level constraints.
me_plus_me_equals_bee(M, E, B) :-
dig(ME, [M, E]),
dig(BEE, [B, E, E]),
BEE #= ME + ME.This relation says that two integer values ME and BEE exist as decimal digits and that two ME values sum to BEE.
Solving gives two solutions, \((M, E, B) = (0, 0, 0)\) and \((M, E, B) = (5, 0, 1)\).
?- me_plus_me_equals_bee(M, E, B), label([M, E, B]).
M = E, E = B, B = 0 ;
M = 5,
E = 0,
B = 1 ;
false.Success.
The label/1 predicate asks for the unknowns to receive their values, i.e. resolve them to “ground” terms in Prolog speak.
The trailing false indicates that the solver has found no further solutions based on the known-knowns (thanks Donald). No real false exists only truth because the logic would need to have access to all knowledge in order to come to a fully-conclusive negative result but all possible solutions appear based on the knowns and their relations.
Double Me
The predicate could also write 2 * ME as follows.
?- dig(ME, [M, E]),
dig(BEE, [B, E, E]),
BEE #= 2 * ME,
BEE #\= 0,
label([M, E, B]).
ME = 50,
M = 5,
E = 0,
BEE = 100,
B = 1 ;
false.In this case, an additional \(BEE\ne0\) removes the first unwanted solution.
No Gun, No Hunt
Does it work for other problems? The same approach works for more complicated puzzles.
?- dig(NO, [N, O]),
dig(GUN, [G, U, N]),
dig(HUNT, [H, U, N, T]),
HUNT #= NO + GUN + NO,
all_different([N, O, G, U, H, T]),
H #\= 0,
label([N, O, G, U, H, T]).
NO = 87,
N = 8,
O = 7,
GUN = 908,
G = 9,
U = 0,
HUNT = 1082,
H = 1,
T = 2.Correct answer. In this case, the query adds a differential requirement for all the digits using all_different/1 and \(H\ne0\) because the most-significant digit must be at least \(1\) otherwise it would be UNT rather than HUNT.
Conclusions
CLP is a very powerful tool and easy to use with a little practice. Thinking in relational terms is not so easy, however. For the imperative programmer, trained in everyday machine-oriented languages, the mind tends to think in terms of “what do I tell the computer to do” rather than “how do I tell the computer my problem.” One approach is not necessarily better than the other. Rather, one informs the other. Abstracting to the relationships in-between elements of the problem nevertheless is an essential part of the software development process whether a small problem like ME+ME=BEE or a piece of embedded firmware or even a large parallel event streaming compute farm.