crypt Test Program

The crypt riddle is a complication of the well-known SEND + MORE = MONEY riddle. Our riddle is found in W.C. Trigg’s collection [1, problem 223] and it will not only involve addition but also multiplication. We have already introduced this problem in the benchmark for the Jekejeke Runtime. We use the same pure Prolog solution here. This solution is based on the graphical problem statement and implements a digit wise multiplication:

        O E E
          E E
      ------- *
      E O E E
      E O E
      -------
      O O E E

A letter E stands for an even digit. The letter O stands for an odd digit. The initial E letters are not allowed to receive the zero value. In the pure Prolog solution the corresponding generators for the digits are placed at their least possible position in the problem query so as to reduce the backtracking. The CLP(FD) solution takes another approach and uses multiplication constraints for the row multiplication. It then leaves the generator selection to the constraint system. Both approaches produce the same single solution:

        3 4 8
          2 8
      ------- *
      2 7 8 4
      6 9 6
      -------
      9 7 4 4

The crypt problem is a challenge for a CLP(FD) system since the two domains even and odd have a lot of holes, so that range bounds don’t deliver much information.

Comments