A Cryptarithmetic Puzzle in Prolog

Note: This example is taken from Prolog: Programming for Artificial Intelligence by Ivan Bratko

An example of a cryptarithmetic puzzle is

DONALD

GERALD

+________

ROBERT

Note that all letters have to be assigned different digits.  We need to define a relationship sum(N1,N2,N) where N1,N2, and N represent the three numbers that give the solution to the puzzle. However, it is not so easy to find the solution directly by this relationship, thus we define another relationship sum1. sum1(N1,N2,N,C1,C,Digits1,Digits). N1,N2, and N are still our three numbers as in the sum relation. C1 is carry from the right and C is carry to the left. One thing to be mentioned is nonvar built-in predicate. It checks whether a variable is already instantiated or not. Then here is the algorithm:

.

Then

?- puzzle1(N1,N2,N),sum(N1,N2,N).

gives us

N1 = [5, 2, 6, 4, 8, 5],
N2 = [1, 9, 7, 4, 8, 5],
N = [7, 2, 3, 9, 7, 0]

 

 

Reference:

Prolog Programming for Artificial Intelligence (4th Edition) (International Computer Science Series)  (A great book!)

4 thoughts on “A Cryptarithmetic Puzzle in Prolog

  1. I have to formulate the following problem as a search problem.
    SEND
    +MORE
    ——
    MONEY
    Can you please help me to find a solution

Leave a comment

Your email address will not be published. Required fields are marked *