Einsteins Riddle Prolog

Question

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. :/

Solution 1

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.

Solution 2

This puzzle (also know as the Zebra Puzzle) has been discussed many times on Stackoverflow before, see e.g.:

• Solving "Who owns the Zebra" programmatically?
• Why cant i get the answer to the zebra puzzle in prolog?
• Solving logic puzzle in Prolog
• Einstein's riddle

Solution 3

A Prolog translation can be straightforward, rule by rule, still following the paradigm of instantiating the domain by selecting from it. Here it's the domain of house attributes; in the linked answer house attributes are fixed by a human programmer and the domain is the actual inhabited houses, which allows for a very succinct encoding.

In other words the difference is in the notation: a sophisticated notation takes us half way there already, but it was a human who invented it and followed it (like the programmer having to write down norwegian in the first house's specification directly, at the appropriate argument position) -- not a computer.

Here we try to inject as little human knowledge into the code as possible, following the homework's constraints. _{(though anything is debatable of course, and the ultimate in eschewing human interference would be a computer program that takes English text as its input ... which would again be open to criticism as to how specifically tailored that program is for finding solutions to this specific puzzle, or type of puzzles, etc., etc.)}

We code it in the top-down style. Apparently, the question is missing. It should be "who drinks water? who owns the zebra?":

zebra( Z, W ,HS) :-         
    length(        HS, 5),      % nation? color? what's that? define it later...
    member(  H1,   HS),    nation( H1, eng    ),    color( H1, red    ),
    member(  H2,   HS),    nation( H2, spa    ),    owns(  H2, dog    ),            
    member(  H3,   HS),    drink(  H3, coffee ),    color( H3, green  ),         
    member(  H4,   HS),    nation( H4, ukr    ),    drink( H4, tea    ),
    right_of(B, A, HS),    color(  A , ivory  ),    color( B , green  ),
    member(  H5,   HS),    smoke(  H5, oldgold),    owns(  H5, snails ),   
    member(  H6,   HS),    smoke(  H6, kools  ),    color( H6, yellow ), 
    middle(  C,    HS),    drink(  C , milk   ),  
    first(   D,    HS),    nation( D , nor    ),
    next_to( E, F, HS),    smoke(  E , chester),    owns(  F , fox    ),
    next_to( G, H, HS),    smoke(  G , kools  ),    owns(  H , horse  ),
    member(  H7,   HS),    smoke(  H7, lucky  ),    drink( H7, orange ),
    member(  H8,   HS),    nation( H8, jpn    ),    smoke( H8, parlamt),
    next_to( I, J, HS),    nation( I , nor    ),    color( J , blue   ),
    member(  W,    HS),    drink(  W , water  ),
    member(  Z,    HS),    owns(   Z , zebra  ).

right_of( B, A, HS) :- append( _, [A, B | _], HS).
next_to( A, B, HS) :- right_of( B, A, HS) ; right_of( A, B, HS).
middle( A, [_,_,A,_,_]).
first( A, [A | _]).

nation(H, V) :-  attr( H, nation-V).
owns(  H, V) :-  attr( H, owns-V).        % select an attribute
smoke( H, V) :-  attr( H, smoke-V).       %   from an extensible record H
color( H, V) :-  attr( H, color-V).       %   of house attributes
drink( H, V) :-  attr( H, drink-V).       %   which *is* a house

attr(House, Attr-Value) :- 
    memberchk( Attr-X, House),            % unique attribute names
    X = Value.

Testing, performing exhaustive search with a failure-driven loop,

3 ?- time((zebra(Z,W,_), maplist(nation,[Z,W],R), writeln(R), false ; true)).
[jpn,nor]
% 180,974 inferences, 0.016 CPU in 0.020 seconds (78% CPU, 11600823 Lips)
true.

Here's how the houses end up being defined:

5 ?- zebra(_, _, HS), maplist( writeln, HS),
     false.
[smoke-kools,  color-yellow, nation-nor,    owns-fox,      drink-water |_G859]
[nation-ukr,   drink-tea,    smoke-chester, owns-horse,    color-blue  |_G853]
[nation-eng,   color-red,    smoke-oldgold, owns-snails,   drink-milk  |_G775]
[nation-spa,   owns-dog,     color-ivory,   smoke-lucky,   drink-orange|_G826]
[drink-coffee, color-green,  nation-jpn,    smoke-parlamt, owns-zebra  |_G865]
false.

or, with attributes lists "frozen" by fixing their length, and then sorted,

7 ?- zebra( _, _, HS), maplist( length, HS, _), !, maplist( sort, HS, S),
     maplist( writeln, S), false.
[color-yellow, drink-water,  nation-nor,  owns-fox,    smoke-kools  ]
[color-blue,   drink-tea,    nation-ukr,  owns-horse,  smoke-chester]
[color-red,    drink-milk,   nation-eng,  owns-snails, smoke-oldgold]
[color-ivory,  drink-orange, nation-spa,  owns-dog,    smoke-lucky  ]
[color-green,  drink-coffee, nation-jpn,  owns-zebra,  smoke-parlamt]
false.

It is also easy to make the attr/2 predicate accept lists of Name-Value pairs, allowing for more naturally flowing, higher-level looking coding style with kind of "extensible records" -- one might even say "objects" -- specifications, like

zebra( Z, W ,HS):-         
    length(       HS, 5), 
    member(  H1,  HS),    attr( H1,  [nation-eng,   color-red  ] ),
    member(  H2,  HS),    attr( H2,  [nation-spa,   owns-dog   ] ),
    member(  H3,  HS),    attr( H3,  [drink-coffee, color-green] ),
    ......

etc..

Comments

[Thanos Tintinidis]

tbh, I think that these constrains enforce a not so suitable representation of the data and therefore resulting in awkward/not so elegant code. I used similar predicates on my first take but after a bit trashed the file (final solution: [users.ntua.gr/el06009/files/zebra.pl]). sorry for the not exactly helpful comment, just wanted to say that, imo, these constrains are indeed nasty :/

[Will Ness]

@thanosQR a Prolog solution is here. I think it's elegant and nice. :) the key is using select to make simultaneous mutually-exclusive choices from domain, to get the diff constraint satisfied by construction.

[Thanos Tintinidis]

@WillNess well, you are not using owns/2, smokes/2 and drinks/2, right? I'm not really saying that you can't have an elegant solution in prolog (on the contrary, I used to think that my solution is quite elegant till I saw yours (the link above appears broken github.com/thanosqr/side_projects/blob/master/zebra_puzzle.p‌​l)), just that the homework's constrains make it hard to write an elegant solution

[Will Ness]

@thanosQR very interesting approach! :) 1+1 = 1+1 indeed. Nice!

[Will Ness]

@thanosQR well, I've added here the answer that does use owns/2 and the like, and it's not too ugly too. :) Takes 75x more inferences than my other answer, but still runs very fast.

[false]

At least, a tag, please. Isn't there a generic name for this kind of riddle like: can be solved by drawing a couple of tables. That is what Einstein thought of it - and he claimed that only tiny percentage of people are able to solve it. Alas, that tiny percentage is here on SO!

[Will Ness]

here it's a little different: they don't want us to "draw a table", but invent a way to say "owns", "smokes" etc, to the computer. That's why I decided to add this answer. I think it's different enough approach.

[Thanos Tintinidis]

@false well, technically, you are not supposed to solve it with a program XD

[Will Ness]

@thanosQR this is kind of "extensible records" here, very easy to do in Prolog. :) I even later generalized it a little bit with attr( Record, FieldValuePairs). I esp. liked freezing the records here with maplist(length,Records, _). :)

[Thanos Tintinidis]

@WillNess Naturally, the next step is to write a program that accepts a configuration of data and then solves it :D