bts (03/29/83)
Here's another solution to the Zebra puzzle, thanks to Fernando
Pereira. Notice that statistics are included at the end. Of
course, if you're still working on the puzzle yourself you should
save this without reading it.
Date: Mon 28 Mar 83 16:15:41-PST
From: PEREIRA@SRI-AI.ARPA
Return-Path: <PEREIRA@SRI-AI.ARPA>
Subject: Zebra puzzle
Here is a solution to the zebra puzzle.
I leave to your discretion whether to
post it immediately or to leave a bit
more time for other people to puzzle.
Fernando
--------------
/*
(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([C1],Situation,_),
pet_of(C1,zebra),
man_of(C1,Man1),
select([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,S,_),
condition(C,Args),
satisfies_all(Cs,S).
select([],S,S).
select([Arg|Args],S0,S) :-
remove(Arg,S0,S1),
select(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(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
*/
-------