jono@bruce.OZ (Jonathan Oliver) (11/10/89)
In reply to the following article we present a solution closer to the problem statement: > From LAZBM%CUNYVM.CUNY.EDU@munnari Mon Oct 2 23:51:15 1989 > Path: bruce!munnari.oz.au!murtoa.cs.mu.oz.au!uunet!ginosko!gem.mps.ohio-state.edu!wuarchive!psuvax1!psuvm!cunyvm.bitnet!lazbm > From: LAZBM@CUNYVM.CUNY.EDU > Newsgroups: comp.lang.prolog > Subject: The jobs puzzle > Message-ID: <2572LAZBM@CUNYVM> > Date: 2 Oct 89 13:51:15 GMT > Organization: The City University of New York - New York, NY > Lines: 54 > DISCLAIMER: Author bears full responsibility for contents of this article > > This is my solution to the jobs puzzle. > It works, but it would be nice to write down the problem and that would > be the solution. > Anybody has a better solution? > > /* The jobs puzzle > * 1 There are four people roberta thelma steve and pete > * 2 Among them,they hold eight different jobs > * 3 Each holds exactly 2 jobs > * 4 The jobs are:chef,guard,nurse,telephone operator, > * police officer(gender not implied) teacher actor boxer > * 5 The job of nurse is held by a male > * 6 The husband of the chef is the telephone operator > * 7 Roberta is not the boxer > * 8 Pete has no education past ninth grade > * 9 Roberta, the chef and the police officer went golfing together > */ > solve:-joblist(Jlist), > del(J1,Jlist,Jl1),del(J2,Jl1,Jl2),J1 < J2 ,hasjobs(roberta,J1,J2), > del(J3,Jl2, Jl3),del(J4,Jl3,Jl4),J3 < J4 ,hasjobs(thelma ,J3,J4), > del(J5,Jl4 ,Jl5),del(J6,Jl5,Jl6),J5 < J6 ,hasjobs(steve ,J5,J6), > del(J7,Jl6 ,Jl7),del(J8,Jl7,Jl8),J7 < J8 ,hasjobs(pete ,J7,J8), > write('roberta '),write(J1),write(' '),write(J2),nl, > write('thelma '),write(J3),write(' '),write(J4),nl, > write('steve '),write(J5),write(' '),write(J6),nl, > write('pete '),write(J7),write(' '),write(J8),nl. > > hasjobs(X,chef,police):-!,fail. /*9 */ > hasjobs(X,police,chef):-!,fail. /*9 */ > hasjobs(X,telop,chef):-!,fail. /*6 */ > hasjobs(X,chef,telop):-!,fail. /*6 */ > hasjobs(X,J1,J2):- hasjob(X,J1), > hasjob(X,J2). > > hasjob(roberta,chef):-!,fail. /*9 */ > hasjob(roberta,police):-!,fail. /*9 */ > hasjob(pete,police):-!,fail. /*8*/ > hasjob(pete,nurse ):-!,fail. /*8*/ > hasjob(pete,teacher):-!,fail. /*8*/ > hasjob(roberta,boxer):- !,fail. /*7*/ > hasjob(X,nurse):- !,male(X). /*5*/ > hasjob(X,actor):- !,male(X). /* meaning of actor*/ > hasjob(X,telop):-!,male(X). /*6 */ > hasjob(X,chef ):-!,not male(X). /*6 */ > hasjob(X,Y). > > male(steve). > male(pete ). > > /* list symbol is { } in this prolog */ > joblist({chef,guard,nurse,telop,police,teacher,actor,boxer}). > del(X,{X|T},T). > del(X,{Y|T},{Y|T1}) :- del(X,T,T1). > Our Solution ------------------------------------------------------------------------- /* The problem is set out in a similar way to the Zebra Problem */ /* tested on mu_prolog version 3.1 */ /* person(name, jobs, gender) */ not_job(L, P, Job) :- member(person(P, J, _), L), member(Job, J), !, fail. not_job(L, _, _). s(L):- L = [ person(_, [_,_], _), person(_, [_,_], _), person(_, [_,_], _), person(_, [_,_], _) ], /* Sex */ member(person(thelma, _, female), L), member(person(roberta, _, female), L), member(person(steve, _, male), L), member(person(pete, _, male), L), /* 5. nurse is a male */ member(person(_, J1, male), L), member(nurse, J1), /* 6. husband of chef is telephone */ member(person(_, J2, female), L), member(chef, J2), member(person(_, J3, male), L), member(teleop, J3), /* define police, boxer, teacher, guard and actor as jobs */ member(person(_, J4, _), L), member(police, J4), member(person(_, J5, _), L), member(boxer, J5), member(person(_, J6, _), L), member(teacher, J6), member(person(_, J7, _), L), member(guard, J7), member(person(_, J8, _), L), member(actor, J8), /* 7. roberta is not the boxer */ not_job(L, roberta, boxer), /* 8. pete has no education beyond 9th grade */ /* The problem doesn't state explicitly which jobs are excluded so we assume that the following jobs are excluded: nurse, police and teacher */ not_job(L, pete, nurse), not_job(L, pete, police), not_job(L, pete, teacher), /* 9. roberta the chef the police went golfing together */ not_job(L, roberta, police), not_job(L, roberta, chef), not_both(L). member(X,[X|_]). member(X,[_|Y]) :- member(X,Y). /* not_both is derived from statement 9 */ not_both(L) :- member(person(_, [police, chef], _) , L), !, fail. not_both(L) :- member(person(_, [chef, police], _) , L), !, fail. not_both(L). ------------------------------------------------------------------------- Jon Oliver and Pierre Lim.
abbott@aerospace.aero.org (Russell J. Abbott) (11/14/89)
In article <1683@bruce.OZ> jono@bruce.OZ (Jonathan Oliver) writes: >> From LAZBM%CUNYVM.CUNY.EDU@munnari Mon Oct 2 23:51:15 1989 >> >> /* The jobs puzzle >> * 1 There are four people roberta thelma steve and pete >> * 2 Among them,they hold eight different jobs >> * 3 Each holds exactly 2 jobs >> * 4 The jobs are:chef,guard,nurse,telephone operator, >> * police officer(gender not implied) teacher actor boxer >> * 5 The job of nurse is held by a male >> * 6 The husband of the chef is the telephone operator >> * 7 Roberta is not the boxer >> * 8 Pete has no education past ninth grade >> * 9 Roberta, the chef and the police officer went golfing together >> */ I use puzzles like this in an AI class. (Sterling and Shapiro provide a generic solution.) It is nice for introducing students to Prolog since it illustrates declarative programming and can also be used to discuss backtracking and efficiency issues. Typically the solution for any specific puzzle looks like the following. (The clues for this puzzle are used for concreteness.) puzzle(List) :- % The List is a "world" that must satisfy the given constraints. % Instantiate the variables in elements of the List in such a way that the % constraints are satisfied. clue1(List), clue2(List), ..., clue_last(List), % Ensure that everything is mentioned. eveything_mentioned(List). % Create the list initially with some property fixed. % This prevents needless backtracking. The order in which the clues % are run can make a big difference in time. clue1(List) :- findall(Element, namex(Element, _), List). % Use data structure accessors to hide and access the structure of % the list elements. In this case, the accessor is also used to % instantiate (or check the validity of) the accessed component. % namex/2 is used instead of name/2 since name/2 is a standard predicate. % (If one used setof instead of findall, one would have to create a % namex/1 predicate that called namex/2.) namex(person(Name, _, _, ..., _), Name) :- member(name, [roberta, thelma, steve, pete]). % Clue 5. The job of nurse is held by a male. % In this clue one creates an element with the specified job, ensures % that that element is male, and inserts it into the list. job/2 and % gender/2 are similar to namex/2--although gender/2 presumably uses % namex/2 and ensures consistency between gender and name. clue5(List) :- job(X, nurse), gender(X, male), member(X, List). % Clue 7. Roberta is not the boxer. % The easiest way to deal with clues of this sort is to create two % entities and make sure they are both in the list. clue7(List) :- namex(P1, roberta), job(P2, boxer), distinct_in([P1, P2], List). distinct_in([X|Xs], Ys) :- delete(X, Ys, Zs), distinct_in(Xs, Zs). distinct_in([], _). % This approach leads to a potential inefficiency in that multiple % elements with the indicated properties may be created. Eventually % they are eliminated when one insists that everything be mentioned % somewhere. % One could also use clues of this sort as constraints and run them % after every step that instantiates a variable. That is, after every % clue in which "roberta" or "boxer" is mentioned, run a version of this % clue to ensure that roberta has not been made into a boxer, e.g., % after clue 9. In order to do that one would have to modify the accessor % predicates so that one could access the element components without % instantiating them. For example, clue7_constraint(List) :- member(P, List), has_name(P, N), has_job(P, boxer), !, fail. clue7_constraint(_). has_name(person(N1, _, ..., _), N2) :- nonvar(N1), N1 = N2. % Clearly, this is less pure, but it provides an opportunity to discuss % negation, variables, etc. % If one had the sort of system discussed by Van Hentenryck in his % _Constraint Satisfaction in Logic Programming_ (MIT Press) this sort % of clue could be dealt with more more satisfactorily. -- -- Russ abbott@itro3.aero.org