How to Solve Cryptarithmetic Puzzle in Prolog

Question

I have to write a Prolog program for solving a cryptarithmetic puzzle.

I need to write a function solve([A, M, P, D, Y]) which assigns the variables [A, M, P, D, Y] to values from 0 to 9 so that it satisfies the equation AM+PM=DAY. Each variable is assigned to a different value, and A, P, and D cannot be equal to 0.

I started writing this function, but ran into problems running my program. I set the restrictions of A, P, and D not being zero. As I was going through the algorithm, I realized that D has to be 1, so I defined that in the beginning of my program. I defined two different variables for M (M1 and M2) and set them equal to each other, since the different M’s in the puzzle should be assigned to the same value. I assigned locations to the different variables and added them up based on the puzzle. I accounted for any variables being carried with carry in variables. My program compiles but the function does not execute.

solve([A, M1, M2, P, D, Y]):- D is 1,
A/=0,
P/=0,
D/=0,
M1 = M2,
select(M1, [0,2,3,4,5,6,7,8,9], R1),
select(M2, R1, R2),
Y is (M1+M2) mod 10,
C1 is (M1+M2) // 10,
select(Y, R2, R3),
select(A, R3, R4),
select(P, R4, R5),
select(D, R5, R6),
A is (A+P+C1) mod 10,
D is (A+P+C1)// 10.

What am I doing wrong? Is there something wrong with my variable definitions? Do I need to define two different M variables, or is one sufficient?

Answer 1

I think your problem are the multiple 'assignments' to D. First D get bound to 1, after that cannot change value (Prolog use unification, not assignment). Then both

...
select(D, R5, R6),
...
D is (A+P+C1)// 10.

will fail when D is different than 1

Answer 2

You write: "My program compiles but the function does not execute: "

solve([A, M1, M2, P, D, Y]):- D is 1,
    A/=0,

No wonder. First of all, there's no /= operator in Prolog. I assume you meant \=. But A \= B means "A can not be unified with B". In your case B is 0, but A is a yet not set logical variable. It can be unified with anything. You should only use \= to check inequality, after all logvars involved had been instantiated!

So, A \= 0 fails. (Another thing is, M1=M2 is superfluous, you can just use M throughout).

A general tool to solve such puzzles is unique selection from narrowing domains:

selectM([A|As],S,Z):- select(A,S,S1),selectM(As,S1,Z).
selectM([],Z,Z).

With it, your puzzle is just

solve([A,M,P,D,Y]):-
  selectM([A,P,D],[1,2,3,4,5,6,7,8,9],R),     % R is the remaining domain
  selectM([M,Y],[0|R],_),                     % don't care what remains
  10*(A+P)+M+M =:= 100*D+10*A+Y.

---

You have a right idea of finding out the assignments before searching, where possible. Using your approach, it could be written as

solve([A,M,P,D,Y]):-    
  selectM([M,A],[0,1,2,3,4,5,6,7,8,9],R),
  A =\= 0,
  Y  is (M+M) mod 10,     % AM+PM=DAY
  C1 is (M+M) // 10,
  A  is (A+P+C1) mod 10,
  D  is (A+P+C1) // 10,
  selectM([P,D,Y],R,_),   % ensure all are different
  p =\= 0, D =\= 0.

Again, we must select A before testing its value.

Answer 3

Here is my solution for your puzzle. We simply rely on PROLOG's backtracking. We select all variables first, then check the puzzle conditions. I don't think that you need to define two Ms.

solve([A,M,P,D,Y]):- 
select(A,[0,1,2,3,4,5,6,7,8,9],WA), % W means Without
not(A=0),
select(M,WA,WMA),
select(P,WMA,WMAP),
not(P=0),
select(D,WMAP,WMAPD),
not(D=0),
select(Y,WMAPD,WMAPDY),
DAY is 100*D+10*A+Y,
AM  is 10*A+M,
PM  is 10*P+M,
DAY is AM+PM.

Answer 4

In addition to what others have posted, I would like to present a slightly different take on this.

The following solution uses GNU Prolog and its CLP(FD) constraints. Such constraints are available in all widely used Prolog systems.

solution(Vs) :-
        Vs = [A,M,P,D,Y],
        fd_domain(Vs, 0, 9),
                   A*10 + M
                 + P*10 + M
        #= D*100 + A*10 + Y,
        fd_all_different(Vs),
        A #\= 0,
        P #\= 0,
        D #\= 0.

I now highlight a few key advantages of using CLP(FD) constraints in this case.

First, it is obvious that we can model all requirements in an extremely straight-forward way with such constraints. The program is really an almost verbatim translation of your task to built-in relations:

• I need to write a function solve([A, M, P, D, Y])

  I used solution/1 instead of the imperative solve/1, because the predicate makes sense in all directions, including specific instances where all variables are already bound to concrete integers. In such cases, we can use the predicate to verify solutions. Calling it "solve" does not make sense in cases where the puzzle is already completely solved. Also, we can use the predicate to complete partially instantiated solutions. In Prolog, it is good practice to avoid imperatives for predicate names.

• which assigns the variables [A, M, P, D, Y] to values from 0 to 9

  This is stated via fd_domain(Vs, 0, 9).

• so that it satisfies the equation AM+PM=DAY.

  The equation is thus A*10 + M + P*10 + M #= D*100 + A*10 + Y.

• Each variable is assigned to a different value

  This is expressed by the built-in constraint fd_all_different/1.

• and A, P, and D cannot be equal to 0.

  This is stated via A #\= 0 etc.

Second, we can use the most general query to study the effects of constraint propagation:

| ?- solution([).

Vs = [_#3(2..8),_#24(5..8),9,1,_#87(0:2..6)]

or, put differently:

| ?- solution([A,M,P,D,Y]).

A = _#3(2..8)
D = 1
M = _#24(5..8)
P = 9
Y = _#87(0:2..6)

This confirms what you say: D is necessarily 1 in this puzzle. And this also shows several other interesting things which go beyond what you found: P is necessarily 9. Moreover, quite strict bounds hold for M, and the domains of A and Y have also been pruned significantly.

This shows that constraint propagation has significantly reduced the search space.

What do concrete solutions look like? Here are a few examples:

| ?- solution(Vs), fd_labeling(Vs).

Vs = [2,5,9,1,0] ? ;

Vs = [2,7,9,1,4] ? ;

Vs = [2,8,9,1,6] ?

yes

Third, you can run different labeling options to try various search strategies for exploring the solution space, without the need to change or recompile the program.

Finally,a significantly reduced search space typically yields much faster programs. I leave it as an exercise to run a few benchmarks that show how much faster the CLP(FD)-based version is in this case.

See clpfd for more information about this important declarative paradigm.