Einsteins Riddle Prolog
I need some help with a prolog homework for my AI class. The question is to write prolog code for einstein's puzzle. I know how to write it down in my own but there are some constraints in the homework.
there are 5 houses
the Englishman lives in the red house
the Spaniard owns the dog
coffee is drunk in the green house
the Ukrainian drinks tea
the green house is immediately to the right of the ivory house
the Old Gold smoker owns snails
Kools are smoked in the yellow house
milk is drunk in the middle house
the Norwegian lives in the first house
the man who smokes Chesterelds lives in the house next to the man with the fox
3 Kools are smoked in the house next to the house where the horse is kept
the Lucky Strike smoker drinks orange juice
the Japanese smokes Parliaments
the Norwegian lives next to the blue house
I know that I need to use list for houses because they are ordered. I wanted to use list for the house characteristics too but I got a problem here.
I was going to use anonymous variables house(englishman, red, _, _, _). but I dont know how to interpret that for the homework.
Here are the constraints: you should use the following binary predicate symbols:
owns(N,Pet)
smokes(N, Cigarette).
drinks(N, Drink).
Other than that you are free to use any number of predicates.
here is how I initialized the facts but I dont know how to make the rules in this case
next_to(X,Y) :- right_of(X,Y); right_of(Y,X).
owns(spaniard, dog).
drinks(ukrainian, tea).
smokes(japanese, parliaments).
right_of(ivory, green).
lives(englishman, red).
owns(X, snail) :- smokes(X, old_gold).
smokes(X, kools) :- owns(X, yellow).
smokes(X, lucky_strike) :- drinks(X, orange_juice).
drinks(X, coffee) :- owns(X, green_house).
it makes sense a little bit but it looks completely wrong at the same time. I don't think I can go anywhere with this one. :/
Answer
This site is devoted to solve such puzzles with CLP(FD). But the full power of CLP(FD) is overkill here: your assignment can be solved effectively searching the entire solution space when you have adequately described the constraints.
The solution will be composed of 5 houses, where each attribute satisfy all constraints imposed by description.
Be aware to use the very same symbol for each attribute (i.e. green and green_house is wrong, choose one of them).
Also next_to seems wrong: if you number from 1 to 5, this can be computed or enumerated, but refers to the immediate neighbour.
So complete the 'solution search space' data representation, something like
Problem = [
house(1, Nationality1, Color1, Pet1, Drinks1, Smokes1),
house(2, Nationality2, Color2, Pet2, Drinks2, Smokes2),
...
],
% place constraints
member(house(_, englishman, red, _, _, _), Problem),
member(house(_, spaniard, _, dog, _, _), Problem),
...
member/2 it's the simpler Prolog builtin, but in this case suffices to solve the problem: when all constraints have been posted, the variables will bind to appropriate values. The key is the ability of member to non deterministically select a member (duh) of the solution.
So when you need to express a constraint between 2 different elements, invoke 2 times member, and place the constraints between appropriate variables: i.e.
the man who smokes Chesterelds lives in the house next to the man with the fox
will be translated to
....,
member(house(N, _, _, _, _, chesterelds), Problem),
member(house(M, _, _, fox, _, _), Problem),
next_to(N, M),
...
When expressing many constraints in such way, beware to symbols identity: could be useful to code each predicate in a separate procedure, to avoid undue aliasing. But the couterpart is also true: if the same symbol is involved in more than a constraint, will be necessary to pass around the symbol, to narrow down the search.
I will let you to think about the right representation of 'geometric' predicates: next_to and right_of could be enumerated, or expressed by means of arithmetic.