5

I'm implementing a variation on Einstein's Riddle and i'm having some trouble.

When trying to calculate the solution i try this:

solve(Street) :- Street = [_House1,_House2,_House3,_House4,_House5],
%hint one goes here
%hint two goes here
%etc.

I can then ask the solution by typing: solve(Street)

However this comes up as solution:

  1. house(flower, food, pet, sport)
  2. house(flower, food, pet, sport)
  3. house(x , food, pet, sport)
  4. house(flower, food, pet, sport)
  5. house(x, flower, pet, sport)

As you can see there's 2 times x, the rest are all types of foods, flowers, pets and sports. But every type is unique: if one person likes flower X, noone else can like X.

Now, the reason why my solution gives 2 x's is easy to see: we are given an amount of hints but in all the hints there are only mentioned 4 flowers. So Prolog doesn't know there is another flower, and just uses x twice, just because it's possible and fulfills all the other hints.

What i want to say is that all the types of foods and flowers etc. in Street are unique so he should leave some blank when he used all types already. 3 would look like: house(x , food, pet ,sport) and 5 would look like: house(_, flower, pet, sport).

I also tried adding this to the hints: (let's say "cactus" is one of the flowers not mentioned in the hints) member(house(cactus,_,_,_), Street)

However then my program doesn't end...

A hint may look like this: is_neighbour(house(_,_,_,football),house(_,_,fish,_), Street), with : is_neighbour(A,B,List) giving true when A and B are next to each other in List. The hint can be translated to: the person who loves football lives next to the person who has fish.

If any more info need to be provided i'm willing to elaborate. :)

false
  • 10,264
  • 13
  • 101
  • 209
Aerus
  • 4,332
  • 5
  • 43
  • 62

1 Answers1

2

To express that no flower is reported twice, and also to make sure that all flowers are bound, you can use the permutation/2 predicate: the list of all flowers should be a permutation of the list of specified flowers. This would read like [untested]

flowers([], []).
flowers([house(Flower,_,_,_)|Street], [Flower|Rest]) :- flowers(Street, Rest).

-- ...
   flowers(Street, Flowers), 
   permutation(Flowers, [kaktus, tulpe, nelke, rose, fingerhut]),

Edit: for 10 flowers, using permutations is probably too slow. An alternative approach is

flower(kaktus).
flower(tulpe).
flower(nelke).
--...

       flowers(Street,[F1,F2,F3,F4,F5,F6,F7,F8,F9,F10]),
       flower(F1), flower(F2), F1\=F2,
       flower(F3), F3\=F1, F3\=F2,
       flower(F4), F4\=F1, F4\=F2, F4\=F3,
       --...
Martin v. Löwis
  • 124,830
  • 17
  • 198
  • 235
  • Sounds like a logic and understandable answer, however i must be doing something wrong.. I added all the flowers in the second list of permutation. I also put `flowers(Street, Flowers)` and the permutation to the `solve(Street)`. But now it doesn't seem to end. (usually it would end within 5 min. but now it's been over 15min.) Does it matter where i put the `permutation` ? – Aerus Dec 10 '10 at 22:19
  • Permutation should be symmetric for both arguments, so swapping the arguments should not help. Putting the permutation call in a different location should help very much, though: you should first put those conditions that constrain the solution space most. Put write calls into it to have it trace what it's doing. – Martin v. Löwis Dec 10 '10 at 22:27
  • When i put a call(write()) around the permutation at the end of the hints it gives: permutation([geranium,hyacint,**lelie**,dahlia,**lelie**],[cactus,lelie,geranium,hyacint,dahlia]). When i put it in front of all the hints it gives me: permutation([_46,_53,_60,_67,_74],[cactus,lelie,geranium,hyacint,dahlia]). I'm not sure what that first means. The output still gives me 2 x's but it does end now. Do i also need to add permutations for the other types in order for this single permutation to work ? – Aerus Dec 10 '10 at 22:53
  • Not sure what you mean by putting write "around" permutation(). Are you saying you use permutation as a structure that you merely print out? You should evaluate it as a predicate, and put the print *after*, not around, permutation. – Martin v. Löwis Dec 10 '10 at 23:07
  • I'm pretty sure i'm doing something wrong with the write thingie.. Here is my code: http://pastebin.com/5TjJJ5nj (it's long but all the things are similar so can be skipped pretty fast when reading), could you please tell me where do i put this write ? Also what do i put as argument for the write since it gives me an error when i don't pass any arguments... – Aerus Dec 10 '10 at 23:37
  • Could you please post a link to the version where you added a write call in the code ? – Aerus Dec 11 '10 at 09:37
  • Thank you, when i put it at the beginning of the hints, it does what it's meant to do: it calculates all permutations of the Flower list, however 10! (10 elements) is somewhat 3.5million permutations, so of course it takes way to long. I then put it at the end of the hints and it doesn't print out anything, probably because it takes to long? When adding it to the end of the hints, does it check if all possible answers till now are a permutation of the flower list or does it generate all permutations and check if all possible answers are a permutation? – Aerus Dec 11 '10 at 10:17
  • See my edit. For ten elements, using permutation is indeed not appropriate (your original posting had only 5 houses). – Martin v. Löwis Dec 11 '10 at 10:46
  • Indeed, i wanted to keep my question simple and adjusted it to 5. (although i should have stated that in fact i had 10 values for each type) I have no clue what the code in your edit does, i added: flower(value) for all 10 flowers, and completed to code up to `flower(F10), F10\=F1, F10\=F2,...,F10\=F8, F10\=F9.`. The program doesn't seem to end anywhere within half an hour. Since i don't really understand what the code is, i can't really give an explanation for this... – Aerus Dec 11 '10 at 17:23
  • Also, is it: `flower(F2), F1\=F2,` or `flower(F2), F2\=F1,` ? (it does end in the last case but still with two x's) – Aerus Dec 11 '10 at 17:34
  • Again, you should do write statements at strategic places, to find out how things get bound. AFAIK, \= is symmetric. As for: what this does - I'm not really willing to explain, as you should be able to interpret it yourself. And keep in mind that it is better to put more specific constraints with less alternatives earlier in the code. – Martin v. Löwis Dec 11 '10 at 18:00
  • Ok, the code wasn't that hard as i thought, it's just another way to express that every value has to be unique. I tested this on some easier examples and i understand what it does, also if i enable the more easy hints (member(house(..)), [_,_,X,_] = Street) it shows possible solutions with all unique values. So i will now start enabling hint per hint and see if it goes wrong somewhere... Thanks a lot so far, i'll keep this question updated as soon as i know more. – Aerus Dec 12 '10 at 13:53
  • It works now, it takes quite some time though. I also sorted the predicates according to how specific they were: first the `member()`, then the `is_two_further` then `is_one_further` and in the end `is_neighbour`. Thanks for your time and patience, i can't upvote your answer yet (need 15 points), but at least i can already accept it. Thanks. – Aerus Dec 12 '10 at 15:47