This is something I wrote but a long time ago, but never finished, while I was learning constraint logic programming in the clpfd module. For various reasons I’ve been discussing declarative programming and Prolog a fair bit recently, so though I’d post this little piece as an example how nifty it can be.

Here’s another nice little puzzle. Consider the following:

   SEND
 + MORE
-------  
= MONEY

To solve this puzzle you must identify a (unique) digit for each letter such that the equation is correct. Multi digit numbers are not zero padded.

This is an example of a cryptarithm, there are many others. I especially like:

      T H I S
 +      I S A
 +  G R E A T
 +    T I M E
-------------       
= W A S T E R

Typically you’d solve a cryptarithm by first figuring out as much as you can to simplify the problem and then using brute force. This can be really quite challenging. In the SEND + MORE = MONEY example there are more than 1.8 million possibilities for assignment of digits to the letter in puzzle.

As well as proving a nice time waster cryptarithms also provide an excellent example of a problem that can be solved with constraint programming. We’ll specifically look at solving these puzzles using constraint logic programming (CLP).

CLP extends regular logic programming with constraints over the values logic variables can have. There’s noting special about this, you can include constraints in regular Prolog programs:

B(X, 1) :- X < 0.

Unfortunately though Prolog isn’t always that smart. For example the following fails:

3 = 1 + Y.

Even though there can be only one valid value for Y Prolog can’t find it because it doesn’t like that Y isn’t sufficiently instantiated. In effect it’s wanting to backtrack over all possible values for Y and fails.

Using the constraint logic module (actually constraint logic over finite domains), we can constrain Y to the set of values, in this case literally the values that satisfy the term. This works:

:- use_module(library(clpfd)).
3 #= 1 + Y.

This is neat, because we can simply state the rules of our puzzle as constraints and ask Prolog to solve it for us.

So for the cryptarithm:

     H U R R A Y  
+    H U Z Z A H  
=  P U Z Z L E S

we can write:

puzzles(Characters) :-
    Characters = [H,U,R,A,Y,Z,P,L,E,S],
    Characters ins 0..9,
    H #\= 0,
    P #\= 0,
    all_different(Characters),
                   100000*H + 10000*U + 1000*R +100*R + 10*A + Y  
    +              100000*H + 10000*U + 1000*Z +100*Z + 10*A + H  
    #= 1000000*P + 100000*U + 10000*Z + 1000*Z +100*L + 10*E + S.

So this says:

  • The characters are in the set [H,U,R,A,Y,Z,P,L,E,S].
  • Each character is a number from 0 - 9.
  • H and P can’t be zero because we said zero padding isn’t allowed.
  • All the characters represent a different number.
  • The puzzle must sum as defined.

If you run this and ask clpfd to provide all possible values it’ll give you the single correct solution.

This is both a super efficient representation of the problem, and very fast to run. It’s an excellent example of the power of declarative programming.