8

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.

Community
  • 1
  • 1
jbx
  • 21,365
  • 18
  • 90
  • 144
  • 1
    `dif(V1,V2)` etc. `maplist(dif(V1),[V2,V3,V3])` – false Jan 29 '13 at 19:44
  • 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?! – jbx Jan 30 '13 at 09:38
  • 1
    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. – false Jan 30 '13 at 12:44
  • 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`. – jbx Jan 30 '13 at 14:38
  • 1
    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. – Will Ness Jan 30 '13 at 18:49

3 Answers3

10

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

false
  • 10,264
  • 13
  • 101
  • 209
  • 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. – jbx Jan 30 '13 at 15:35
  • @jbx: You can add it also at the beginning! In this manner the search space will be reduced – false Jan 30 '13 at 15:37
  • Good idea, thanks. Its already good enough that I managed to get the exercise working :) – jbx Jan 30 '13 at 15:38
  • 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? – jbx Jan 30 '13 at 15:40
  • @jbx: Ask Prolog: The answers to `?- maplist(dif(E), Es).` are perfectly clear! – false Jan 30 '13 at 15:46
  • @jbx: Hope this does not confuse you. But the answers Prolog produces are often the most insightful way to understand a relation. – false Jan 30 '13 at 15:50
  • Yep, honestly no idea :). I tried `maplist(dif(E), Es)`. and just got `Es = []`. Whatever that means :) – jbx Jan 30 '13 at 18:04
  • 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`? – jbx Jan 30 '13 at 18:29
  • @jbx: via `call(dif(X),A)`. Which is the same as `dif(X,A)` see the link on maplist for more. – false Jan 30 '13 at 18:32
0

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.

Thanos Tintinidis
  • 5,828
  • 1
  • 20
  • 31
  • 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. – jbx Jan 30 '13 at 09:42
0

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, _).
Community
  • 1
  • 1
Will Ness
  • 70,110
  • 9
  • 98
  • 181
  • Thanks, your approach seems elegant. But you modified the fact list given in the exercise? – jbx Jan 30 '13 at 09:39
  • @jbx 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`. – Will Ness Jan 30 '13 at 11:02
  • 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? – jbx Jan 30 '13 at 11:54
  • @jbx 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. – Will Ness Jan 30 '13 at 16:20
  • 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. – jbx Jan 30 '13 at 18:02
  • @jbx 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? – Will Ness Jan 30 '13 at 18:36