How to Solve Cryptarithmetic Puzzle in Prolog

Tag: prolog , puzzle Author: zj7469588 Date: 2012-11-27

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?

Why are you checking A,P,D at start ? You need to assign values to A,P,D then check if they are different from zeros.

Best Answer

-Hello codegirl, here is my solution for your puzzle.The solution is simple we rely or PROLOG's backtracking. We select all variables at first, then we check the puzzle conditions. I dont 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.

comments:

Thank you for your response. I really appreciate it. Also, is there a way to solve it using the mod 10 way (as I attempted implementing in my original post)?
I think you can do it with mod 10 , but in order to find Y for example (using mod 10), we need to get DAY first, then Y is simply DAY mod 10,A is (DAY div 10) mod 10,D is DAY div 100,same goes for AM and PM. But DAY is a three digit number, hence the select will be from [100,101,...,99+99] for DAY,[10,11,...,99] for AM,PM (2 digits ) . Hope this helps.
Also, why did you add a WA (without A) variable? There are duplicates of As and Ms.
Ehem with select(A,[0,1....,9],WA) we get some list that doesn't contain the value ( I named it WA ) for A. Also A in DAY and in AM must have the same value.

Other Answer1

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.

Other Answer2

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