Geek Answers Handbook

Force Prolog select unique variable values

OK I'm new to Prolog, so excuse me if this is something trivial, but I cannot find the right elegant answer to this question. I am trying to work out an exercise here on learnprolognow.org , exercise 2.4 (crossword).

The exercise contains the following 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 that I came up with to solve the crosswords of each word is the following:

 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).

From V1a to V1g , etc., which are the characters of each word, and V1bH1b to V3fH3f are the characters that occur between words in a crossword puzzle.

The solution seems to work, but the result is a duplicate value, 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 get Prolog to have V1 \= V2 \= V3 \= H1 \= H2 \= H3 ? If I do them individually one after the other, I will need 120 permutations, so there should be a faster way, and this is an exercise for beginners, so I'm missing something.

I found this similar question , but the answers provided seem so complicated, I hope there is an easier way. I use swi prolog on Ubuntu, just in case this is important.

Thanks.

+6
source share
3 answers

Use alldif/1 like this:

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

What can be used even for the most general request:

 ?- alldif(Es). Es = [] ; Es = [_G1924] ; Es = [_G2061, _G2064], dif(_G2061, _G2064) ; Es = [_G2163, _G2166, _G2169], dif(_G2163, _G2169), dif(_G2163, _G2166), dif(_G2166, _G2169) ; Es = [_G2309, _G2312, _G2315, _G2318], dif(_G2309, _G2318), dif(_G2309, _G2315), dif(_G2309, _G2312), dif(_G2315, _G2318), dif(_G2312, _G2315), dif(_G2312, _G2318) ...

The value of the maplist(dif(E),Es) target maplist(dif(E),Es) best understood by looking at the answers:

 ?- maplist(dif(E),Es). Es = [] ; Es = [_G1987], dif(E, _G1987) ; Es = [_G2040, _G2043], dif(E, _G2043), dif(E, _G2040) ; Es = [_G2093, _G2096, _G2099], dif(E, _G2099), dif(E, _G2096), dif(E, _G2093) ; Es = [_G2146, _G2149, _G2152, _G2155], dif(E, _G2155), dif(E, _G2152), dif(E, _G2149), dif(E, _G2146) ...

That is, Es is a list of elements that are all different from E The purpose of 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) .

+9
source

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

On the other hand, it may be faster to have a list of available words and delete it when using it; not only will you not have to do the check at the end, but you will avoid meaningless instances ( A1 = foo, A2 = foo will stop immediately, and will not be rejected at the end). In other words, pruning branches.

0
source

Or 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, _).
0
source

More articles:


All Articles