How to solve a cryptographic puzzle in Prolog

Question

I need to write a Prolog program to solve a cryptographic puzzle.

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

I started writing this function, but ran into problems when starting my program. I set the constraints of A, P, and D to not equal zero. When I went through the algorithm, I realized that D must be 1, so I defined this at the beginning of my program. I defined two different variables for M (M1 and M2) and set them equal to each other, since different Ms in the puzzle must be assigned to the same value. I assigned locations for different variables and added them based on the puzzle. I took into account any variables that carry with portable variables. My program compiles, but the function fails.

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 variables M or enough?

Answer 1

Here is my solution for your puzzle. We simply rely on PROLOG return traffic. First, we select all the variables, and then check the conditions of the puzzle. I do not think 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 2

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

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

Not surprising. First of all, there is no /= operator in Prolog. I assume you mean \= . But A \= B means that "A cannot be unified with B". In your case, B is 0, but A is an undefined logical variable. It can be combined with anything. You should use \= to check for inequality, after all the logs have been involved!

So A \= 0 does not work . (Another thing, M1=M2 superfluous, you can just use M everywhere).

A common tool for solving such puzzles is the unique choice of domain narrowing :

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

With it, your puzzle is simple

 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 the right idea to find out the purpose before looking for where it is possible. Using your approach, it can 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

In addition to what others have posted, I would like to reflect on this a bit.

The following solution uses GNU Prolog and its CLP (FD) . Such restrictions 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.

Now I highlight several key benefits to use the CLP (FD) constraints in this case.

First, it’s obvious that with such restrictions we can model all requirements using an extremely straightforward one . The program is really almost a literal translation of your task into an embedded relationship:

• I need to write a solve function ([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 specific integers. In such cases, we can use the predicate to check the solutions. The call to "solve" does not make sense in cases where the puzzle is already completely solved. In addition, we can use the predicate to complete partially constructed solutions. Prolog recommends avoiding imperatives for predicate names.

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

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

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

  Thus, the equation is A*10 + M + P*10 + M #= D*100 + A*10 + Y

• Each variable is assigned 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 indicated by A #\= 0 , etc.

Secondly, 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 otherwise:

  |  ? - 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 necessarily 1 in this puzzle. And it also shows several other interesting things that go beyond what you found: P necessarily 9 9. Moreover, fairly strict estimates are valid for M , and areas A and Y also significantly reduced.

This shows that the distribution of constraints has a significantly reduced search space.

What do specific solutions look like? Here are some 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

Thirdly, you can use different labels to try different search strategies to explore the solution space without having to change or recompile the program.

Finally, a significantly reduced search space usually gives programs much faster . I leave this as an exercise to run several tests that show how much faster the CLP (FD) based version is in this case.

See clpfd for more information on this important declarative paradigm.

Answer 4

I think your problem is in the multiple "assignments" of D. First, D is attached to 1, after which it cannot change the value (union in Prolog, not assignment). Then both

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

will fail if D is different from 1