Hassan%upenn.csnet@csnet-relay.arpa (08/06/84)
From: Hassan Aitkaci <Hassan%upenn.csnet@csnet-relay.arpa>
The Zebra puzzle was the object of a Prolog-Digest exchange about a
year and a half ago. Many solutions were proposed. Fernando Pereira of
SRI compiled a set of those for his own interest. The most interesting
(in my opinion) solution in Prolog was found by Hector Levesque of
Fairchild AI Lab, making a clever use of logical variables and the
unification process as an effective means to solve two-way constraint
propagations (i.e., a logical variable in Prolog has the behavior of
both a "synthesized" and "inherited" attribute, and unification
operates as the propagating mechanism). Hector's solution is given here
since I don't think it ever got posted on the Prolog Digest.
Those who are really intrigued by the method rather than the problem
which, by the way, happens to be a large-size, albeit simple, assignment
problem (complete state space has (5!)^6 nodes, or 2,985,984,000,000
nodes if you prefer!) may be interested by an alternative solution
given in a language of my design in my dissertation, also reported in
the following paper:
Hassan Ait-Kaci, "A New Model of Computation Based on a Calculus
of Type Subsumption", Technical Report MS-CIS-83-40, Department
of Computer and Information Science, Univ. of Pennsylvania,
Philadelphia, PA 19104.
Prolog solutions may be obtained from the Prolog Digest Archives from
the editor Chuck Restivo from Stanford University. Now, please, stop
losing sleep from so much coffee -- or you may turn into a greenish
looking samourai riding a bucking zebra!
Hassan Ait-Kaci
Hassan%Upenn@Csnet-relay
/*********************************************************************
Hector Levesque's Solution to the Zebra Puzzle
*********************************************************************/
:- op(500,xfy,[has_left_neighbor,is_right_of,lives_next_to,is_not]).
rightmost_occupant has_left_neighbor midright_occupant.
midright_occupant has_left_neighbor middle_occupant.
middle_occupant has_left_neighbor midleft_occupant.
midleft_occupant has_left_neighbor leftmost_occupant.
X lives_next_to Y :- X has_left_neighbor Y.
X lives_next_to Y :- Y has_left_neighbor X.
X is_right_of Y :- X has_left_neighbor Y.
X is_right_of Y :- X has_left_neighbor Z, Z is_right_of Y.
X is_not Y :- X is_right_of Y.
X is_not Y :- Y is_right_of X.
differ(X1,X2,X3,X4,X5) :-
X1 is_not X2, X1 is_not X3, X1 is_not X4, X1 is_not X5,
X2 is_not X3, X2 is_not X4, X2 is_not X5,
X3 is_not X4, X3 is_not X5,
X4 is_not X5.
?- Englishman = RedHouser,
Spaniard = DogOwner,
CoffeeDrinker = GreenHouser,
Ukranian = TeaDrinker,
GreenHouser has_left_neighbor IvoryHouser,
WinstonSmoker = SnailOwner,
KoolSmoker = YellowHouser,
MilkDrinker = middle_occupant,
Norwegian = leftmost_occupant,
ChesterfieldSmoker lives_next_to FoxOwner,
KoolSmoker lives_next_to HorseOwner,
LuckyStrikeSmoker = OJDrinker,
Japanese = ParliamentSmoker,
Norwegian lives_next_to BlueHouser,
differ(GreenHouser,YellowHouser,RedHouser,IvoryHouser,BlueHouser),
differ(ZebraOwner,FoxOwner,HorseOwner,SnailOwner,DogOwner),
differ(OJDrinker,MilkDrinker,TeaDrinker,CoffeeDrinker,WaterDrinker),
differ(Englishman,Spaniard,Norwegian,Japanese,Ukranian),
differ(KoolSmoker,WinstonSmoker,ParliamentSmoker,LuckyStrikeSmoker,
ChesterfieldSmoker).
/*********************************************************************
To solve the puzzle, load this program... and wait!
It takes about 45 minutes when interpreted by UNH Prolog
on our (overloaded) VAX/780...
*********************************************************************/Hassan%upenn.csnet@csnet-relay.arpa (08/06/84)
From: Hassan Aitkaci <Hassan%upenn.csnet@csnet-relay.arpa> The Zebra puzzle was the object of a Prolog-Digest exchange about a year and a half ago. Many solutions were proposed. Fernando Pereira of SRI compiled a set of those for his own interest. The most interesting (in my opinion) solution in Prolog was found by Hector Levesque of ***Sender closed connection*** === Network Mail from host sri-ai.arpa on Fri Aug 10 00:52:58 ===