Force Prolog to choose unique values of variables

Question

OK I am new to Prolog, so excuse me if this is something trivial, but I can't seem to find a proper elegant answer to this. I am trying to work out the exercise here on learnprolognow.org, exercise 2.4 (the crossword).

The exercise provides these facts:

   word(astante,  a,s,t,a,n,t,e). 
   word(astoria,  a,s,t,o,r,i,a). 
   word(baratto,  b,a,r,a,t,t,o). 
   word(cobalto,  c,o,b,a,l,t,o). 
   word(pistola,  p,i,s,t,o,l,a). 
   word(statale,  s,t,a,t,a,l,e).

And the solution I came up with to solve the crossword placement of each word is this:

crossword(V1, V2, V3, H1, H2, H3) :-
   word(V1, V1a, V1bH1b, V1c, V1dH2b, V1e, V1fH3b, V1g), 
   word(V2, V2a, V2bH1d, V2c, V2dH2d, V2e, V2fH3d, V2g), 
   word(V3, V3a, V3bH1f, V3c, V3dH2f, V3e, V3fH3f, V3g), 
   word(H1, H1a, V1bH1b, H1c, V2bH1d, H1e, V3bH1f, H1g), 
   word(H2, H2a, V1dH2b, H2c, V2dH2d, H2e, V3dH2f, H2g), 
   word(H3, H3a, V1fH3b, H3c, V2fH3d, H3e, V3fH3f, H3g).

With V1a to V1g etc. being the characters of each word, and the V1bH1b to V3fH3f being the characters in common between words in the crossword.

The solution seems to work, however the result is producing duplicate values, with the first result being:

?- crossword(V1, V2, V3, H1, H2, H3).
V1 = astante,
V2 = baratto,
V3 = statale,
H1 = astante,
H2 = baratto,
H3 = statale .

How can I force Prolog to have V1 \= V2 \= V3 \= H1 \= H2 \= H3 ? If I do them individually one by one I will need 120 permutations, so there must be a quicker way, and this is a beginners exercise so I must be missing something.

I found this similar question, but the answers provided seem so complicated, I hope there is a simpler way. I am using swi-prolog on Ubuntu, just in case it matters.

Thanks.

Cystic

dif(V1,V2) etc. maplist(dif(V1),[V2,V3,V3]) – Incapable

But isn't div(V1, V2) equivalent to V1 \= V2, so i still have to do it 120 times to ensure that the 6 variables are not the same?! – Cystic

Note, that it is dif/2. Yes, it is the same. with maplist you are already shorten. To shorten even further define an auxiliary predicate alldif/1 which is true if all elements of the list are different. – Incapable

OK, and how do I do that? Please remember I am still a beginner just starting this, so dont assume that I am able to fill in the etc. or insert more here. – Cystic

if you are that early in the game don't try to jump ahead; work out the stuff step by step. At first you'll have to type out more verbose solutions, no matter. Then when you get to the more advanced stuff you'll appreciate it even better. – Postman

Answer 1

Use alldif/1 defined like so:

alldif([]).
alldif([E|Es]) :-
   maplist(dif(E), Es),
   alldif(Es).

Which can be used even for the most general query:

?- alldif(Es).
   Es = []
;  Es = [_A]
;  Es = [_A,_B], dif(_A,_B)
;  Es = [_A,_B,_C],
   dif(_A,_B), dif(_A,_C),
   dif(_B,_C)
;  Es = [_A,_B,_C,_D],
   dif(_A,_B), dif(_A,_C), dif(_A,_D),
   dif(_B,_C), dif(_B,_D),
   dif(_C,_D)
;  ... .

The meaning of the goal maplist(dif(E),Es) is best understood by looking at the answers:

?- maplist(dif(E),Es).
   Es = []
;  Es = [_A], dif(E,_A)
;  Es = [_A,_B], dif(E,_A), dif(E,_B)
;  Es = [_A,_B,_C], dif(E,_A), dif(E,_B), dif(E,_C)
;  ... .

That is, Es is a list of elements that are all different to E. The goal maplist(dif(E),[A,B,C]) combines the first element (in this case dif(E)) with each element of the list. Thus dif(E,A), dif(E,B), dif(E,C).

Incapable

Cheers! I just added the alldif you indicated and at the end of my crossword() clause I added alldif([V1, V2, V3, H1, H2, H3]). Thanks for your help. There had to be a simple way. – Cystic

@jbx: You can add it also at the beginning! In this manner the search space will be reduced – Incapable

Good idea, thanks. Its already good enough that I managed to get the exercise working :) – Cystic

Small last question, which might be useful for potential readers. What is maplist(dif(E), Es) actually doing? What is dif/1 comparing E with? And what will maplist/2 actually provide? – Cystic

@jbx: Ask Prolog: The answers to ?- maplist(dif(E), Es). are perfectly clear! – Incapable

@jbx: Hope this does not confuse you. But the answers Prolog produces are often the most insightful way to understand a relation. – Incapable

Yep, honestly no idea :). I tried maplist(dif(E), Es). and just got Es = []. Whatever that means :) – Cystic

Thanks, so just to get a clear understanding, how is a predicate of arity 2 dif/2 being used with the form of arity 1 in the maplist? – Cystic

@jbx: via call(dif(X),A). Which is the same as dif(X,A) see the link on maplist for more. – Incapable

Answer 2

length(List, N): N is the length of the list
sort(List, SortedList): SortedList is a sorted version of List (duplicate elements are removed)

On the other hand, it may be faster to have a list of available words and remove one when it's used; not only you won't have to do the check at the end but you will avoid pointless instantiations (A1 = foo, A2 = foo will stop immediately instead of getting rejected at the end). In other words, branch pruning.

Kirin

Thanks, but can you elaborate a bit more how do I use the facts provided by the exercise to finally achieve crossword(V1, V2, V3, H1, H2, H3) which guarantees each are different? Thats the point of this exercise. – Cystic

Answer 3

Either what @false told you in the comments; or I like to use domain selection:

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

word(astante,  [a,s,t,a,n,t,e]). 
word(astoria,  [a,s,t,o,r,i,a]). 
word(baratto,  [b,a,r,a,t,t,o]). 
word(cobalto,  [c,o,b,a,l,t,o]). 
word(pistola,  [p,i,s,t,o,l,a]). 
word(statale,  [s,t,a,t,a,l,e]).

crossword(Words) :- findall(W, word(_,W), WS),
   Words = [[ _,A,_,B,_,C,_], 
            [ _,D,_,E,_,F,_], 
            [ _,G,_,H,_,I,_],
            [ _,A,_,D,_,G,_],
            [ _,B,_,E,_,H,_],
            [ _,C,_,F,_,I,_]],
   selectM( Words, WS, _).

Postman

Thanks, your approach seems elegant. But you modified the fact list given in the exercise? – Cystic

@Cystic yes I did. :) If you aren't allowed to, then you can convert one into another: wordL(W):- word(_, A,B,C,D,E,F,G), W=[ insert more here ].. Then you can use wordL instead of word in the call to findall. – Postman

Well its not I am not allowed to, thats the way the exercise is and I am trying to learn things slowly. What would the insert more here have? – Cystic

@Cystic I left it for you to figure out. :) Say, for word(day, d, a, y) we'd want W=[d,a,y], right? If that's hard for you right now, probably it's better to study some introduction to Prolog first. – Postman

Yes, thats the whole point. That exercise is chapter 2 of learnprolognow.org (chapter 1 just explains atoms, simple terms etc.). I clearly said that in the question to indicate I am a beginner, so its difficult for me to bridge the gap at the moment. But thanks for the answer too. – Cystic

@Cystic Let's try again. We convert word(day, d, a, y) to [d,a,y] with word(_,A,B,C), W=[A,B,C]. Or if we had a fact word(month, m,o,n,t,h) we'd convert it with word(_,A,B,C,D,E),W=[A,B,C,D,E]. Here we have 7 letter words, that's all. Does this help? – Postman