dan@ttds.UUCP (Dan Sahlin) (08/08/84)
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)