[Search for users]
[Overall Top Noters]
[List of all Conferences]
[Download this site]
| Title: | Mathematics at DEC |
|
| Moderator: | RUSURE::EDP |
|
| Created: | Mon Feb 03 1986 |
| Last Modified: | Fri Jun 06 1997 |
| Last Successful Update: | Fri Jun 06 1997 |
| Number of topics: | 2083 |
| Total number of notes: | 14613 |
125.0. "PROLOG and zebras" by HARE::STAN () Sat Aug 11 1984 02:16
While I tend to only rarely post the "logic puzzles" that come
in from net.puzzle (since they frequently don't involve much
mathematics), I am posting this solution to the classic
"Who owns the Zebra" puzzle because the attached solution in
PROLOG may interest some people at DEC. In fact, perhaps someone
would be interested in writing a more general prolog program that
could solve most of the problems of this type.
- Stan -
===================================================================
Newsgroups: net.math,net.puzzle,net.misc,net.lang.prolog
Path: decwrl!decvax!mcvax!enea!ttds!dan
Subject: Re: WHO OWNS THE ZEBRA, solution in Prolog (no spoiler)
Posted: Wed Aug 8 21:27:59 1984
The zebra problem (see below) was given last week in net.math,
net.puzzle and net.misc.
I found it irresistible to write a Prolog program that solves the puzzle.
Since it was a very straightforward translation of the problem, most of the
time taken to construct the program was the time to type it down.
Execution time was approx. two minutes on a VAX-11/750 for the first
solution. After three more minutes the interpreter says there are no more
solutions.
The first condition in the puzzle says that all houses have a different
colour and are inhabited by different nationalities etc.
In this solution I have not accounted for that, but the program can easily
be extended to check that. In MU-Prolog this becomes especially attractive
since the checking can be called first in the program, but is not performed
until the corresponding variables become instantiated. The execution time
also decreases somewhat since many attempted solutions become discarded
earlier.
/* I got this problem from Harriette L. Lilly at Tektronix */
/********************************
WHO OWNS THE ZEBRA .................
ON A CITY STREET, STRANGER ACCOSTS STRANGER WITH A XEROXED SHEET OF PAPER
AND THE QUESTION: "HAVE YOU SEEN THIS?". IN UNIVERSITY DORMITORIES THE
PROBLEM IS TACKED TO DOORS, MUCH AFTER THE MANNER OF MARTIN LUTHER.
IN SUBURBAN HOUSEHOLDS THE RING OF THE TELEPHONE IS LIKELY TO HEARLD
A VOICE THAT ASKS 'IS IT THE NORWEGIAN?'
THE CAUSE OF THE EXCITEMENT IS THE BRAINTEASER BELOW. IT'S HARD, BUT
CAN BE SOLVED BY USING DEDUCTION, ANALYSIS, AND A LOT OF PERSISTENCE.
1. THERE ARE FIVE HOUSES, EACH OF A DIFFERENT COLOR AND INHABITED BY
MEN OF DIFFERENT NATIONALITIES, WITH DIFFERENT PETS, DRINKS, AND
CIGARETTES.
2. THE ENGLISHMAN LIVES IN THE RED HOUSE
3. THE SPANIARD OWNS THE DOG.
4. COFFEE IS DRUNK IN THE GREEN HOUSE
5. THE UKRAINIAN DRINKS TEA.
6. THE GREEN HOUSE IS IMMEDIATELY TO THE RIGHT (YOUR RIGHT) OF THE
IVORY HOUSE.
7. THE OLD GOLD SMOKER OWNS SNAILS.
8. KOOLS ARE BEING SMOKED IN THE YELLOW HOUSE.
9. MILK IS DRUNK IN THE MIDDLE HOUSE.
10. THE NORWEGIAN LIVES IN THE FIRST HOUSE ON THE LEFT.
11. THE CHESTERFIELD SMOKER LIVES NEXT TO THE FOX OWNER.
12. KOOLS ARE SMOKED IN THE HOUSE NEXT TO THE HOUSE WHERE THE HORSE IS KEPT.
13. THE LUCKY STRIKE SMOKER DRINKS ORANGE JUICE.
14. THE JAPANESE SMOKES PARLIAMENTS.
15. THE NORWEGIAN LIVES NEXT TO THE BLUE HOUSE.
NOW ...........
WHO DRINKS WATER?
AND ...........
WHO OWNS THE ZEBRA?
GOOD LUCK!
****************************************************************/
/*
Prolog program to solve the zebra problem.
Aug 1984, Dan Sahlin, The Royal Inst. of Techn., Stockholm, Sweden
*/
zebra(Zebraowner,Drinkswater) :-
houses(5,List),
member(house( red, englishman, _, _, _) ,List),
member(house( _, spaniard, dog, _, _) ,List),
member(house(green, _, _, coffee, _) ,List),
member(house( _, ukrainian, _, tea, _) ,List),
sublist([house(ivory, _, _, _, _) ,
house(green, _, _, _, _)],List),
member(house( _, _,snail, _,old_gold),List),
member(house(yellow, _, _, _, kools),List),
[H1,H2,house( _, _, _, milk, _),H4,H5]=List,
[house( _, norwegian, _, _, _)|Hrest]=List,
nextto(house( _, _, _, _,chesterfield),
house( _, _, fox, _, _),List),
nextto(house( _, _, _, _, kools),
house( _, _,horse, _, _),List),
member(house( _, _, _, orange,lucky_strike),List),
member(house( _, japanese, _, _,parliaments),List),
nextto(house( _, norwegian, _, _, _),
house( blue, _, _, _, _),List),
member(house( _, Drinkswater, _, water, _),List),
member(house( _, Zebraowner,zebra, _, _),List).
houses(0,[]).
houses(N,[house(Color,Nat,Pet,Drink,Cig)|List]) :-
N>0, N1 is N-1,
houses(N1,List).
member(X,[X|R]).
member(X,[Y|R]) :- member(X,R).
sublist(S,L) :- append(S,S2,L).
sublist(S,[H|T]) :- sublist(S,T).
append([],L,L).
append([X|R],Y,[X|T]) :- append(R,Y,T).
nextto(H1,H2,L) :- sublist([H1,H2],L).
nextto(H1,H2,L) :- sublist([H2,H1],L).
-------
Dan Sahlin (..decvax!mcvax!enea!ttds!dan)
| T.R | Title | User | Personal
Name | Date | Lines |
|---|
| 125.1 | | ORPHAN::BRETT | | Sun Aug 12 1984 18:06 | 9 |
|
When I first saw this problem (in my mid-teens) I solved it by building a
jigsaw puzzle in which each piece represented a clue, then solving the
jigsaw puzzle!
The puzzle had the houses across the top, and the other aspects down the
side.
/Bevin
|
| 125.2 | | HARE::STAN | | Tue Aug 21 1984 20:18 | 244 |
| From: ROLL::USENET "USENET Newsgroup Distributor" 12-AUG-1984 22:07
To: HARE::STAN
Subj: USENET net.math newsgroup articles
Newsgroups: net.math,net.misc,net.puzzle
Path: decwrl!decvax!ittvax!dcdwest!sdcsvax!sdcrdcf!hplabs!tektronix!teklds!azure!harriett
Subject: WHO OWNS THE ZEBRA (Solution)
Posted: Fri Aug 10 09:27:34 1984
Re: WHO OWNS THE ZEBRA
Thanks to all who sent solutions to the "Who Owns The Zebra" brain
teaser. Various approaches were taken and all answers were correct (however,
I'm not to sure about the proof of the conclusions :-) ?!?!?). The hardest part
of the puzzle is to PROVE each of your conclusions, and this is how I did it.
Known:
____________ ____________ ____________ ___________ ___________
Norwegian Blue Milk
>From clues 10, 15, 9 resp.
Now: The Norwegian cannot live in:
1. The red house (clue 2), the Englishman does.
2. The blue house (clue 15), he lives next to it.
3. The green house, because it must have the Ivory house
to its left and it has no house to its left.
4. The ivory house, because it must have the green house
to its right and the Norwegians house has a blue
to its right.
Therefore: The Norwegian must live in the Yellow house and by clue 8 he must
smoke Kools.
So now we have:
____________ ____________ ____________ ___________ ___________
Norwegian Blue Milk
Yellow
Kools
Given this: The Norwegian cannot drink:
1. Coffee, because it is drunk in the green house
(clue 4).
2. Tea, because the Ukrainian drinks tea (clue 5).
3. Orange Juice, because he (whoever he is) smokes
Lucky Strike (clue 13).
4. Milk, because milk is drunk in the middle house
(clue 9).
Therefore: The Norwegian must drink WATER!
Also: By clue clue 12 the horse is kept in the blue house.
So now we have:
____________ ____________ ____________ ___________ ___________
Norwegian Blue Milk
Yellow Horse
Kools
Water
Now: For the Blue house:
1. The Norwegian can't live there (already solved).
2. The Englishman can't live there (clue 2).
3. The Spaniard can't live there because he owns a dog
(clue 3).
So It must be either the Japanese, or the Ukrainian. Therefore, we must now
eliminate one by testing the plausability of each.
For the Ukrainian:
1. He drinks tea, so he could also smoke Chesterfield
However plausable, there is no definite determining facter to support nor
dispute this. Thus, we must look at the case of the Japanese:
For the Japanese who smokes Parlaiments:
1. He cannot drink tea, the Ukrainian does (clue 5).
2. He cannot drink milk, he's not in the middle house
(clue 9).
3. He cannot drink water, the Norwegian does.
4. He cannot drink orange juice, the Lucky Strike
smoker drinks O. J. (clue 13).
5. He cannot drink coffee, he's not in the green house
(clue 4).
This eliminates all possibilities of drinks and therefore must eliminate him
from the blue house.
Therefore the Ukrainian who drinks tea must live in the Blue house.
So now we have:
____________ ____________ ____________ ___________ ___________
Norwegian Blue Milk
Yellow Horse
Kools Ukrainian
Water Tea
Now for the smokes of the Ukrainian:
1. He cannot smoke Parlaiment, the Japanese does (clue
14).
2. He cannot smoke Kools, the Norwegian does.
3. He cannot smoke Lucky Strike, he doesn't drink O.J.
(clue 13).
4. He cannot smoke Old Gold, he doesn't own snails (clue
7).
Therefore he must smoke Chesterfield.
So now we have:
____________ ____________ ____________ ___________ ___________
Norwegian Blue Milk
Yellow Horse
Kools Ukrainian
Water Tea
Chesterfield
Now: By clue 11 the fox must either live in the yellow house with the Norwegian
or in the middle house, but no clue defines at this point which one it is.
At this point, it is not possible to determine the order of the colors of the
remaining houses without determining some basic facts about the houses them-
selves. So, lets look at what can be determined about the green house.
Given:
____________ ___________
Ivory Green
Coffee
Whoever lives there cannot smoke:
1. Kools, the Norwegian smokes Kools.
2. Chesterfield, the Ukrainian smokes Chesterfield.
3. Lucky Strike, he drinks O.J.
Thus, it must be the Japanese who smokes Parlaiments, or the Old Gold smoker
who owns snails.
If it is the Old Gold smoker who owns snails he cannot be:
1. The Englishmen, he lives in the red house (clue 2).
2. The Spaniard, he owns a dog (clue 3).
3. The Ukrainian, he lives in the blue house.
4. The Norwegian, he lives in the yellow house.
5. The Japanese, he smokes Parlaiments.
Thus, again, all possibilities of each nationalities is eliminated so it can't
be the Old Gold smoker who owns snails, it must be the Japanese who smokes
Parlaiments.
So now we have:
____________ ___________
Ivory Green
Coffee
Japanese
Parlaiments
At this point we can make the following determinants about the Spaniard:
He cannot:
1. Smoke Kools
2. Chesterfield
3. Parlaiments
4. Old Gold, he owns a dog, not snails (clue 7).
So he must smoke Lucky Strikes and drink orange juice.
Now for the color of the middle house, it must be either Red or Ivory (green
must have the ivory house to it's left leaving the order of either:
Red Ivory Green; or Ivory Green Red).
For the red house in the middle, it again leaves a plausable solution but there
are no facts to support nor dispute it. So lets look at the Ivory house in the
middle.
For the ivory house in the middle:
1. The Norwegian can't live there.
2. The Ukrainian can't live there.
3. The Spaniard can't live there, he drink O.J.
4. The Japanese can't live there.
5. The Englishman can't live there, he lives in the red
house (clue 2).
This eliminates all the nationalities again so the red house must be in the
middle.
So now we have:
____________ ____________ ____________ ___________ ___________
Norwegian Blue Milk Ivory Green
Yellow Horse Red Coffee
Kools Ukrainian Englishman Japanese
Water Tea Parliaments
Chesterfield
We also know from the above determination that the Spaniard who owns the dog,
smokes Lucky Strike and drinks orange juice lives in the ivory house.
So now we have:
____________ ____________ ____________ ___________ ___________
Norwegian Blue Milk Ivory Green
Yellow Horse Red Spaniard Coffee
Kools Ukrainian Englishman Dog Japanese
Water Tea Orange Juice Parliaments
Chesterfield Lucky Strike
And with all the other smokes eliminated, it
also tells us that the Englishman must smoke Old Gold and own snails.
So now we have:
____________ ____________ ____________ ___________ ___________
Norwegian Blue Milk Ivory Green
Yellow Horse Red Spaniard Coffee
Kools Ukrainian Englishman Dog Japanese
Water Tea Old Gold Orange Juice Parliaments
Chesterfield Snails Lucky Strike
This leaves us with the last clue (#11) which states that the Chesterfield
smoker lives next to the fox owner which puts the fox in the Norwegian's house.
So now we have:
____________ ____________ ____________ ___________ ___________
Norwegian Blue Milk Ivory Green
Yellow Horse Red Spaniard Coffee
Kools Ukrainian Englishman Dog Japanese
Water Tea Old Gold Lucky Strike Parliaments
Fox Chesterfield Snails Orange Juice ??????
THUS, THEREFORE AND TO WIT: The Japanese who drinks coffee, lives in the
green house, and smokes Parliaments must own the Zebra!!!!!!
Taaaa Daaaa.
(Now, wasn't that easy?????)
Please send comments, questions, answers, diliberations, etc. to ----
tekmdp!harriett
LOVE THAT Z28 .........
Eight ball in the side pocket off of 6 rails!!!!!!
|
| 125.3 | | HARE::STAN | | Tue Aug 21 1984 20:19 | 20 |
| Newsgroups: net.math,net.puzzle,net.misc
Path: decwrl!amd!dual!zehntel!ihnp4!drutx!houxe!hogpc!houti!ariel!vax135!ukc!qtlon!ist!dt
Subject: Re: WHO OWNS THE ZEBRA
Posted: Mon Aug 20 20:36:01 1984
To those interested in such problems, there is a monthly
magazine called ``Logic Problems'' published in the U.K.
This magazine usually has 30 to 40 such problems, and though
most are to solve for only 4 classes (e.g., Hacker, Company,
Version of Unix, Editor) there are usually a few much more
difficult than the ZEBRA problem.
The ``Logic Problems Subscription Dept.'' address is
BEAP House,
106 Hammersmith Grove,
London W6 7HB
Warning: Problems sometimes require a knowledge of Cricket.
|