Search code examples
prologzebra-puzzle

How does this Zebra solution in prolog work?

zebra_owner(Owner) :-
    houses(Hs),
    member(h(Owner,zebra,_,_,_), Hs).

water_drinker(Drinker) :-
    houses(Hs),
    member(h(Drinker,_,_,water,_), Hs).


houses(Hs) :-
    length(Hs, 5),                                            %  1
    member(h(english,_,_,_,red), Hs),                         %  2
    member(h(spanish,dog,_,_,_), Hs),                         %  3
    member(h(_,_,_,coffee,green), Hs),                        %  4
    member(h(ukrainian,_,_,tea,_), Hs),                       %  5
    adjacent(h(_,_,_,_,green), h(_,_,_,_,white), Hs),         %  6
    member(h(_,snake,winston,_,_), Hs),                       %  7
    member(h(_,_,kool,_,yellow), Hs),                         %  8
    Hs = [_,_,h(_,_,_,milk,_),_,_],                           %  9
    Hs = [h(norwegian,_,_,_,_)|_],                            % 10
    adjacent(h(_,fox,_,_,_), h(_,_,chesterfield,_,_), Hs),        % 11
    adjacent(h(_,_,kool,_,_), h(_,horse,_,_,_), Hs),              % 12
    member(h(_,_,lucky,juice,_), Hs),                         % 13
    member(h(japanese,_,kent,_,_), Hs),                       % 14
    adjacent(h(norwegian,_,_,_,_), h(_,_,_,_,blue), Hs),          % 15
    member(h(_,_,_,water,_), Hs),       % one of them drinks water
    member(h(_,zebra,_,_,_), Hs).       % one of them owns a zebra

adjacent(A, B, Ls) :- append(_, [A,B|_], Ls).
adjacent(A, B, Ls) :- append(_, [B,A|_], Ls).

How come the houses(Hs) predicate not fail the various member(elem, list) checks, if the list is actually empty all the time? I know it might sound like a dumb question, but wrapping my head around Prolog is actually hard, especially after years of Object-oriented programming. Any help is appreciated!

Edit: I didn't mention the query I was asking prolog, which is this zebra_owner(Owner)

Edit 2: Also posting the text of the problem (which is kinda famous) for reference:

  1. Five colored houses in a row, each with an owner, a pet, cigarettes, and a drink.
  2. The English lives in the red house.
  3. The Spanish has a dog.
  4. They drink coffee in the green house.
  5. The Ukrainian drinks tea.
  6. The green house is next to the white house.
  7. The Winston smoker has a serpent.
  8. In the yellow house they smoke Kool.
  9. In the middle house they drink milk.
  10. The Norwegian lives in the first house from the left.
  11. The Chesterfield smoker lives near the man with the fox.
  12. In the house near the house with the horse they smoke Kool.
  13. The Lucky Strike smoker drinks juice.
  14. The Japanese smokes Kent.
  15. The Norwegian lives near the blue house.

Who owns the zebra and who drinks water?

Solution

  • How come the Houses(Hs) predicate not fail the various member(elem, list) checks, if the list is actually empty all the time?

    That's because the list isn't actually empty! The empty list in Prolog is []. It contains no elements.

    But the list inside a call to houses(Hs) is controlled by the first goal in that predicate, namely length(Hs, 5). What does this goal mean?

    An important thing to learn about Prolog is that a goal or query doesn't just mean "is this statement true?". A Prolog goal or query means "under what circumstances is this statement true?". Prolog will try to do work to describe circumstances to you under which your query becomes true.

    So even if we know absolutely nothing about Hs before, when executing this length query, GNU Prolog says:

    | ?- length(Hs, 5).

Hs = [_,_,_,_,_]

    So length(Hs, 5) becomes true if Hs is of the form [_, _, _, _, _]. This is not an empty list. It is not even a possibly empty list. It is a list that definitely contains exactly five elements. We don't know anything about those elements yet! But the length of the list is definitely fixed.

    Maybe you got mislead by the fact that Prolog allows you to talk about a list that definitely has elements but whose elements are not yet known. This is a concept that is not possible in typical object oriented languages. But the fact that we don't know the elements doesn't mean that there is nothing there, i.e., that the list is empty.

    As for how the member calls succeed: Again, they aren't just checks for "is X a member of Hs". They are questions meaning "under what circumstances is X a member of Hs?". Again, Prolog will do some work for you to describe those circumstances:

    | ?- length(Hs, 5), member(x, Hs).

Hs = [x,_,_,_,_] ? ;

Hs = [_,x,_,_,_] ? ;

Hs = [_,_,x,_,_] ? ;

Hs = [_,_,_,x,_] ? ;

Hs = [_,_,_,_,x]

    So x is a member of Hs if x is the first element of Hs, or the second, or the third, or so on. In each of these cases, "describing the circumstances" means that Prolog actually binds the appropriate element of the list (which before was a variable) to the element x. For each of these possibilities, further computations following the member goal could further instantiate the list. This is what builds up the solutions to the Zebra puzzle: Instead of just answering "yes" to the question "does the puzzle have a solution", Prolog builds up a data structure actually describing a solution.