Learning Prolog: solving a crossword scheme

Question

I'm trying to learn Prolog following the tutorials on this site and I can't find a solution to an exercise (and there's no solution on the site).

Here's what I have to do:

Here are six Italian words:

astante , astoria , baratto , cobalto , pistola , statale .

They are to be arranged, crossword puzzle fashion, in the following grid:

The following knowledge base represents a lexicon containing these words:

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

Write a predicate crossword/6 that tells us how to fill in the grid. The first three arguments should be the vertical words from left to right, and the last three arguments the horizontal words from top to bottom.

Now, the same question has been asked there but each given solution uses things that I don't know (and I'm not supposed to know to solve this).

To clarify, while the things in the linked question are surely working, they use stuff that hasn't been explained yet in the guide that I'm following, and this means that I need to solve the exercise without using that kind stuff, so no maplist and things like that.

My idea was to fill the board with the letters from the given words, with some constraints:

the word in V1 must have, as its second character, the second character of the word in H1
the word in V1 must have, as its fourth character, the second character of the word in H2
the word in V1 must have, as its sixth character, the second character of the word in H3

and so on..

So here's my code:

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(V1,V2,V3,H1,H2,H3):- word(V1, V11,V12,V13,V14,V15,V16,V17),
                               word(H1, H11,V12,H13,H14,H15,H16,H17),
                               word(H2, H21,V14,H23,H24,H25,H26,H27),
                               word(H3, H31,V16,H33,H34,H35,H36,H37),

                               word(V2, V21,V22,V23,V24,V25,V26,V27),
                               word(H1, H11,H12,H13,V22,H15,H16,H17),
                               word(H2, H21,H22,H23,V24,H25,H26,H27),
                               word(H3, H31,H32,H33,V26,H35,H36,H37),

                               word(V3, V31,V32,V33,V34,V35,V36,V37),
                               word(H1, H11,H12,H13,H14,H15,V32,H17),
                               word(H2, H21,H22,H23,H24,H25,V34,H27),
                               word(H3, H31,H23,H33,H34,H35,V36,H37).

(I'm sorry if this is not formatted well but I still don't know what's the correct indentation style for Prolog).

Of course, event if my idea seems correct (at least to me), this code returns No and I don't know why.

Any hint on this?

EDIT:

Following @mbratch's comment, I've tried using the code found in this solution.

Here's the code:

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

The code works, but it has a problem with duplicates which I don't mind.

What I'd like to understand is why this one works while mine returns No.

You can look at this question http://stackoverflow.com/questions/9693501/crossword-solver-in-prolog/9698240#9698240 — joel76, Jan 19 '14 at 18:12
Did you actually took some time to read the question? I already said that I don't have to use the things proposed in that question. I edited the qustion to clarify this thing. — StepTNT, Jan 19 '14 at 18:14
Ok, but I think that you should read them carefully, for example you only need to define once V1, V2, V3, H1, H2, H3 and look at the cells that are common between them. — joel76, Jan 19 '14 at 18:18
Anything in this question helpful? http://stackoverflow.com/questions/14590761/force-prolog-to-choose-unique-values-of-variables/14595743#14595743 — lurker, Jan 19 '14 at 18:20
As written in the question, I can't use anything of the things written in the answer that you linked. The only allowed thing is the use of the `unification` — StepTNT, Jan 19 '14 at 18:23
`maplist` is very easily replaced with a simple, recursive list processing predicate. — lurker, Jan 19 '14 at 18:24
Anyway, maplist is not necessary to solve the crossword, StepTNT didn't actually write what he said : "My idea was to fill the board with the letters from the given words, with some constraints: the word in V1 must have, as its second character, the second character of the word in H1 the word in V1 must have, as its fourth character, the second character of the word in H2 the word in V1 must have, as its sixth character, the second character of the word in H3" — joel76, Jan 19 '14 at 18:47
don't go skimpy on whitespace. :) whitespace is very important on improving the legibility of your code. — Will Ness, Jan 19 '14 at 18:58

score 7 · Answer 1 · answered Sep 02 '15 at 13:18

7

crossword(V1,V2,V3,H1,H2,H3) :-
 word(V1, _, V12, _, V14, _, V16, _),
 word(V2, _, V22, _, V24, _, V26, _),
 word(V3, _, V32, _, V34, _, V36, _),
 word(H1, _, V12, _, V22, _, V32, _),
 word(H2, _, V14, _, V24, _, V34, _),
 word(H3, _, V16, _, V26, _, V36, _),
 V1 \= H1.

answered Sep 02 '15 at 13:18

Arik

180
2
9

Thanks for giving me the idea of adding `V1 \= H1`. I came up with the equivalent of yours, but minus that, and it gave me `astante, baratto, statale, astante, baratto, statale` (which fits, but seemed inelegant, as half the words go to waste). But why did it stop at that? I take it it is not in the nature of Prolog to give an exhaustive listing of all solutions, but to stop after finding one? – Lori Jan 12 '17 at 20:16
2

how do you actually run the query? – dopatraman Feb 15 '17 at 01:16

score 2 · Accepted Answer · edited Jan 19 '14 at 18:55

After few tries, and based on @joel76's comment, I noticed that my first code was wrong because I declared H1,H2 and H3 multiple times, so the result computed in the second line was being changed in the sixth and this led to the No returned by Prolog.

So, instead of doing things in multiple lines, I merged them with this result:

crossword(V1,V2,V3,H1,H2,H3):- word(V1, V11, V12, V13, V14, V15, V16, V17),
                               word(V2, V21, V22, V23, V24, V25, V26, V27),
                               word(V3, V31, V32, V33, V34, V35, V36, V37),
                               word(H1, H11, V12, H13, V22, H15, V32, H17),
                               word(H2, H21, V14, H23, V24, H25, V34, H27),
                               word(H3, H31, V16, H33, V26, H35, V36, H37).

and now it's working.

You would need to switch off the singleton check for this code to be accepted by the crop of Prolog systems. — , Mar 22 '19 at 20:23

Learning Prolog: solving a crossword scheme

2 Answers2

Linked