% 	Date: Mon 28 Mar 83 16:15:41-PST
% 	From: PEREIRA@SRI-AI.ARPA
% 	Return-Path: <PEREIRA@SRI-AI.ARPA>
% 	Subject: Zebra puzzle
% 
% 
% (Who Owns the Zebra?)
% 
%      There are five houses, each of a different color and inhabited by
% men of different nationalities, with different pets, drinks and
% cigarettes.
% 
% 
% :- public solution/3.

% 1.  The Englishman lives in the red house.

condition(1,[C]) :- man_of(C,englishman), house_of(C,red).
args(1,[_]).

% 2.  The Spaniard owns the dog.

condition(2,[C]) :- man_of(C,spaniard), pet_of(C,dog).
args(2,[_]).

% 3.  Coffee is drunk in the green house.

condition(3,[C]) :- drink_of(C,coffee), house_of(C,green).
args(3,[_]).

% 4.  The Ukrainian drinks tea.

condition(4,[C]) :- man_of(C,ukranian), drink_of(C,tea).
args(4,[_]).

% 5.  The green house is immediately to the right (your right) of the
%     ivory house.

condition(5,[C1,C2]) :-
   house_of(C1,green), house_of(C2,ivory),
   position_of(C1,P1), position_of(C2,P2),
   right_to(P1,P2).
args(5,[_,_]).

% 6.  The Winston smoker owns snails.

condition(6,[C]) :- smoke_of(C,winston), pet_of(C,snails).
args(6,[_]).

% 7.  Kools are smoked in the yellow house.

condition(7,[C]) :- smoke_of(C,kools), house_of(C,yellow).
args(7,[_]).

% 8.  Milk is drunk in the middle house.

condition(8,[C]) :- drink_of(C,milk), position_of(C,middle).
args(8,[_]).

% 9.  The Norwegian lives in the first house on the left.

condition(9,[C]) :- man_of(C,norwegian), position_of(C,leftmost).
args(9,[_]).

% 10. The man who smokes Chesterfields lives in the house next to the
%     man with the fox.

condition(10,[C1,C2]) :-
   smoke_of(C1,chesterfields), position_of(C1,P1),
   pet_of(C2,fox), position_of(C2,P2), single_next_to(P1,P2).
args(10,[_,_]).

% 11. Kools are smoked in the house next to the house where the horse
%    is kept.

condition(11,[C1,C2]) :-
   smoke_of(C1,kools), position_of(C1,P1),
   pet_of(C2,horse), position_of(C2,P2), single_next_to(P1,P2).
args(11,[_,_]).

% 12. The Lucky Strike smoker drinks orange juice.
condition(12,[C]) :- smoke_of(C,lucky_strike), drink_of(C,orange_juice).
args(12,[_]).

% 13. The Japanese smokes Parliaments.
condition(13,[C]) :- man_of(C,japanese), smoke_of(C,parliaments).
args(13,[_]).

% 14. The Norwegian lives next to the blue house.

condition(14,[C1,C2]) :-
   man_of(C1,norwegian), position_of(C1,P1),
   house_of(C2,blue), next_to(P1,P2).
args(14,[_,_]).

% THE PROBLEM: Who owns the Zebra?  Who drinks water?

solution(Man1,Man2,Situation) :-
   valid_situation(Situation),
   select_args([C1],Situation,_),
   pet_of(C1,zebra),
   man_of(C1,Man1),
   select_args([C2],Situation,_),
   drink_of(C2,water),
   man_of(C2,Man2).

% General rules

valid_situation(S) :-
   situation_template(S),
   conditions(Cs),
   satisfies_all(Cs,S),
   coherent(S).

situation_template([
	c(englishman,_,_,_,_,_),
	c(japanese,_,_,_,_,_),
	c(ukranian,_,_,_,_,_),
	c(spaniard,_,_,_,_,_),
	c(norwegian,_,_,_,_,_) ]).

conditions([1,2,3,4,5,6,7,8,9,10,11,12,13,14]).

satisfies_all([],S).
satisfies_all([C|Cs],S) :-
   args(C,Args),
   select_args(Args,S,_),
   condition(C,Args),
   satisfies_all(Cs,S).

select_args([],S,S).
select_args([Arg|Args],S0,S) :-
   remove(Arg,S0,S1),
   select_args(Args,S1,S).

remove(X,[X|S],S).
remove(X,[Y|S0],[Y|S]) :- remove(X,S0,S).

coherent(S) :-
   attributes(A),
   unique(S,A).

unique([],_).
unique([C|S],A0) :-
   pairs(C,P),
   select_args(P,A0,A),
   unique(S,A).

pairs(c(Man,House,Pet,Drink,Smoke,Position),
      [man=Man,
       house=House,
       pet=Pet,
       drink=Drink,
       smoke=Smoke,
       position=Position]).

% Basic Predicates

man_of(c(M,_,_,_,_,_),M).

house_of(c(_,H,_,_,_,_),H).

pet_of(c(_,_,P,_,_,_),P).

drink_of(c(_,_,_,D,_,_),D).

smoke_of(c(_,_,_,_,S,_),S).

position_of(c(_,_,_,_,_,P),P).

right_to(left,leftmost).
right_to(middle,left).
right_to(right,middle).
right_to(rightmost,right).

next_to(P1,P2) :- right_to(P1,P2).
next_to(P1,P2) :- right_to(P2,P1).

single_next_to(left,leftmost).
single_next_to(right,rightmost).

attributes(
       [man=englishman,
	man=ukranian,
	man=norwegian,
	man=spaniard,
	man=japanese,
	house=red,
	house=blue,
	house=yellow,
	house=green,
	house=ivory,
	pet=zebra,
	pet=snails,
	pet=fox,
	pet=horse,
	pet=dog,
	drink=water,
	drink=milk,
	drink=coffee,
	drink=tea,
	drink=orange_juice,
	smoke=winston,
	smoke=parliaments,
	smoke=chesterfields,
	smoke=kools,
	smoke=lucky_strike,
	position=leftmost,
	position=left,
	position=middle,
	position=right,
	position=rightmost]).

% Results on DEC-20 Prolog:

% :- compile(puzzle).
% 
% puzzle compiled: 2207 words,     3.17 sec.
% 
% yes
% | ?- statistics.
% core     55296  (9728 lo-seg + 45568 hi-seg)
% heap      4608 =   3497 in use +   1111 free
% global    1233 =     32 in use +   1201 free
% local     1024 =    100 in use +    924 free
% trail      511 =      4 in use +    507 free
%     0.02 sec. for 1 GCs gaining 579 words
%     0.02 sec. for 2 local shifts and 3 trail shifts
%     3.80 sec. runtime
% 
% yes
solution(Zebra,Water,All), ! ?

% Water = japanese,
% All = [ c(englishman,red,snails,milk,winston,middle),
% 	c(japanese,blue,horse,water,parliaments,rightmost),
% 	c(ukranian,yellow,zebra,tea,kools,right),
% 	c(spaniard,green,dog,coffee,chesterfields,left),
% 	c(norwegian,ivory,fox,orange_juice,lucky_strike,leftmost)],
% Zebra = ukranian ;
% 
% no
% | ?-
% core     55296  (9728 lo-seg + 45568 hi-seg)
% heap      4608 =   3497 in use +   1111 free
% global    1233 =     16 in use +   1217 free
% local     1024 =     16 in use +   1008 free
% trail      511 =      0 in use +    511 free
%     0.02 sec. for 1 GCs gaining 579 words
%     0.03 sec. for 3 local shifts and 5 trail shifts
%    15.59 sec. runtime