ligett (03/28/83)
Be warned: this is a long article because it includes a Prolog
program to solve the "Who owns the zebra?/Who drinks the water?"
puzzle I posted a couple of weeks ago.
Bruce Smith (decvax!duke!unc!bts) was kind enough to mail me
an article entitled "A PROLOG program illustrating a 'verify and choose'
method", by Lewis Baxter, that discussed the solution to this puzzle.
Mr. Baxter wrote the program, and deserves all the credit. I was slow
in posting this response because I wanted to get Mr. Baxter's permission
to include his program - he has consented.
The program runs in about 15 seconds under CProlog on our VAX,
and seems to work fine. I'm embarrassed to say that I don't understand
all of it yet, but I didn't want to let that stop me from posting the
solution.
My thanks to those of you how mailed me hints and help.
Dan Ligett (617) 649-9731
Wang Institute of Graduate Studies !decvax!wivax!ligett (USENET)
70 Tyng Road ligett.wang-inst@udel-relay (CSNET)
Tyngsboro, MA 01879
/*------------------------------------------------------------------*/
/* A PROLOG program to solve the "5 houses" problem */
/* using a "verify and choose" method. */
/* */
/* By Lewis Baxter */
/*------------------------------------------------------------------*/
/* Define ':' as infix. */ :-op(800,xfx,:).
solve :-
constraints(Colours,Drinks,Nationalities,Cigarettes,Pets),
candidate(Colours,Drinks,Nationalities,Cigarettes,Pets),
/****************************************************************/
/* The next four lines ask "Who owns the zebra?" */
/* and "Who drinks water?" */
/* member(water:House1,Drinks), */
/* member(Who1:House1,Nationalities), write(Who1), nl, */
/* member(zebra:House2,Pets), */
/* member(Who2:House2,Nationalities), write(Who2), nl. */
/****************************************************************/
write(Colours), nl,
write(Drinks), nl,
write(Nationalities), nl,
write(Cigarettes), nl,
write(Pets), nl.
/* A candidate solution is any of the (5!)**5 ways
of distributing 5 colours (C), 5 drinks (D),
5 nationalities (N), 5 cigarettes (S), and 5 pets (P)
amongst 5 houses. */
candidate([_:C1, _:C2, _:C3, _:C4, _:C5],
[_:D1, _:D2, _:D3, _:D4, _:D5],
[_:N1, _:N2, _:N3, _:N4, _:N5],
[_:S1, _:S2, _:S3, _:S4, _:S5],
[_:P1, _:P2, _:P3, _:P4, _:P5]) :-
permutation([C1,C2,C3,C4,C5],[1,2,3,4,5]),
permutation([D1,D2,D3,D4,D5],[1,2,3,4,5]),
permutation([N1,N2,N3,N4,N5],[1,2,3,4,5]),
permutation([S1,S2,S3,S4,S5],[1,2,3,4,5]),
permutation([P1,P2,P3,P4,P5],[1,2,3,4,5]).
/* The following constraints are placed on colours (C),
drinks (D), nationalities (N), cigarettes (S),
and pets (P). */
constraints(C,D,N,S,P) :-
member(englishman:House1,N), member(red:House1,C),
member(spaniard:House2,N), member(dog:House2,P),
member(norwegian:1,N),
member(kools:House3,S), member(yellow:House3,C),
member(chesterfields:House4,S), next(House4,Next4),
member(fox:Next4,P),
member(norwegian:House5,N), next(House5,Next5),
member(blue:Next5,C),
member(old_gold:House6,S), member(snails:House6,P),
member(lucky-strike:House7,S), member(orange_juice:House7,D),
member(ukranian:House8,N), member(tea:House8,D),
member(japanese:House9,N), member(parliaments:House9,S),
member(kools:House10,S), next(House10,Next10),
member(horse:Next10,P),
member(coffee:House11,D), member(green:House11,C),
member(green:House12,C), left(Left12,House12),
member(ivory:Left12,C),
member(milk:3,D).
/* --- Utility Predicates --- */
permutation([],[]).
permutation([A,..X],Y) :- delete(A,Y,Y1), permutation(X,Y1).
delete(A,[A,..X],X).
delete(A,[B,..X],[B,..Y]) :- delete(A,X,Y).
member(A,[A,..X]) :- !.
member(A1:A2,[B1:B2,..X]) :-
atomic(A1), atomic(A2), atomic(B1), atomic(B2),
( A1 == B1, A2 \== B2 ; A2 == B2, A1 \== B1 ),
!, fail.
member(A,[B,..X]) :- member(A,X).
next(X,Y) :- left(X,Y). next(X,Y) :- left(Y,X).
left(1,2). left(2,3). left(3,4). left(4,5).
:-end.