% 	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),
	print('The ', Who1, ' drinks water.'),
 	member(zebra:House2,Pets),
 	member(Who2:House2,Nationalities),
	print('The ', Who2, ' owns the zebra.').

%   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).