Seating Arrangements: Solutions ************************************** *** PROGRAM 1, for smodels *** By Son Cao Tran (tson@cs.nmsu.edu) ************************************** % const tables and chairs are input parameters % number of guests equals tables*chairs const guests = tables*chairs. % type predicates table(1..tables). guest(1..guests). % at(G,T) - guest G sits at the Tth table % each guest has one sit 1{at(G,T) : table(T)}1 :- guest(G). chairs {at(G,T) : guest(G)} chairs :- table(T). % defining what is means to be on the same/different tables same_table(G,G):- guest(G). same_table(G1,G2):- table(T), guest(G1), guest(G2), neq(G1,G2), at(G1,T), at(G2,T). % guests, who like each other, should sit on the same table :- guest(G1), guest(G2), like(G1,G2), not same_table(G1,G2). % guests, who hate each other, should not sit on the same table :- guest(G1), guest(G2), dislike(G1,G2), same_table(G1,G2). hide. show at(I,J). ******************************************* *** PROGRAM 2,for PAL *** By Pedro Cabalar (cabalar@dc.fi.udc.es) ******************************************* options not concurrent; constants m = 3; n = 2; sets chair = [1,m]; table = [1,n]; seat = chair x table; person = [1,m*n]; dislikes = {(1,2),(3,7)}; likes = {(2,5)}; actions sit: person -> seat; fluents at: seat -> person + {empty}; pos: person -> seat + {standing}; vars P,P2 : person; S : seat; C,C2 : chair; T : table; rules /* Any person will be at the place where he is sat */ pos(P):=sit(P); /* The content of the occupied seat is the person we have sat */ at(sit(P)):=P; /* Sit down on empty seats */ false if prev(at(sit(P))) != empty; /* Sit persons that were standing */ false if pert(sit(P)) and prev(pos(P))!=standing; /* Avoid "dislikes" */ false if pos(P)=(C,T) and pos(P2)=(C2,T) and (P,P2) in dislikes; /* Force "likes" */ false if pos(P)=(C,T) and pos(P2)=(C2,T2) and T!=T2 and (P,P2) in likes; initially at(S):=empty, pos(P):=standing; query ...{m*n} ? ***************************************** *** PROGRAM 3, for smodels *** By Paolo Ferraris (pieffe8@libero.it) ***************************************** % number of tables const n=2. % number of seats per table const m=3. % number of guests const tot=n*m. guest(1..tot). table(1..n). % two friends sit at the same table atTable(Y,Z) :- friend(X,Y), atTable(X,Z), table(Z). % two not friends cannot sit at the same table :- notFriend(X,Y), atTable(X,Z), atTable(Y,Z), table(Z). % one person sits at only one table 1 [atTable(X,Y): table(Y)] 1 :- guest(X). % exactly M persons sit at the same table m [atTable(X,Y): guest(X)] m :- table(Y). ***************************************** *** PROGRAM 4, for smodels *** By Paolo Ferraris (pieffe8@libero.it) ***************************************** % number of tables const n=2. % number of seats per table const m=3. % number of guests const tot=n*m. guest(1..tot). % two friends sit at the same table sameTable(X,Y) :- friend(X,Y). % two not friends cannot be at the same table :- sameTable(X,Y), notFriend(X,Y). % reflexive property of SameTable sameTable(X,X) :- guest(X). % transitive property of SameTable sameTable(X,Y) :- sameTable(Y,Z), sameTable(Z,X), guest(X), guest(Y), guest(Z). % note: symmetry can obtained from the previous rule when Z=X % exactly M persons sit at the same table m [sameTable(X,Y): guest(X)] m :- guest(Y). ************************************************************** *** PROGRAM 5, for SLDNA *** By Marc Denecker (Marc.Denecker@cs.kuleuven.ac.be) *** and Bert Van Nuffelen (Bert.VanNuffelen@cs.kuleuven.ac.be) ************************************************************** table(X)<- X in 1..N person(X)<- X in 1..MN open_function at_table: person -> table likes(..,..)<- true. dislikes(..,..)<-true. fol forall X,Y: likes(X,Y), at_table(X,TX), at_table(Y,TY) -> TX=TY. fol forall X,Y: dislikes(X,Y), at_table(X,TX), at_table(Y,TY) -> TX\=TY. fol forall X,Cap,NrX: capacity(Cap),table(X), Card(set(Y,at_table(Y,X)),NrX) -> NrX= table } { assign_chair : guest -> chair } { likes : guest guest -> BOOL } { dislikes : guest guest -> BOOL } %% Clauses [ likes(1,3) ] [ likes(2,4) ] [ dislikes(1,5) ] [ dislikes(3,4) ] [ -likes(x,y) | assign_table(x) = assign_table(y) ] [ -dislikes(x,y) | assign_table(x) != assign_table(y) ] [ assign_chair(x) != assign_chair(y) | assign_table(x) != assign_table(y) | x=y] ************************************ *** PROGRAM 10, for smodels *** By Chitta Baral (chitta@asu.edu) ************************************ const n = 3. const m = 3. const k = n*m. table(1..n). person(1..k). m { assigned(P,T) : person(P) } m :- table(T). 1 { assigned(P,T) : table(T) } 1 :- person(P). :- person(I), person(J), table(T), table(TT), together(I,J), assigned(I,T), assigned(J,TT), neq(T,TT). :- person(I), person(J), table(T), separate(I,J), assigned(I,T), assigned(J,T). together(1,2). together(7,4). together(6,8). separate(2,3). separate(3,4). separate(5,6). separate(9,4). hide person(X). hide table(X). hide together(X,Y). hide separate(X,Y). ************************************ *** PROGRAM 11, for smodels *** By Chitta Baral (chitta@asu.edu) ************************************ const n = 3. const m = 3. const k = n*m. table(1..n). person(1..k). :- m+1 { assigned(P,T) : person(P) }, table(T). :- { assigned(P,T) : person(P) } m-1, table(T). not_assigned(P,T) :- person(P), table(T), table(TT), assigned(P,TT), neq(T,TT). not_assigned(P,T) :- person(P), person(PP), table(T), table(TT), together(P,PP), assigned(PP,TT), neq(T,TT). %by having together(P,P), we can remove the last but one rule. not_assigned(P,T) :- person(P), person(PP), table(T), separate(P,PP), assigned(PP,T). assigned(P,T) :- person(P), table(T), not not_assigned(P,T). %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% together(1,2). together(7,4). together(6,8). separate(2,3). separate(3,4). separate(5,6). separate(9,4). hide person(X). hide table(X). hide together(X,Y). hide separate(X,Y). hide not_assigned(X,Y). ************************************ *** PROGRAM 12, for smodels *** By Chitta Baral (chitta@asu.edu) ************************************ const n = 3. const m = 3. const k = n*m. table(1..n). person(1..k). m { assigned(P,T) : person(P) } m :- table(T). :- person(I), table(T), table(TT), assigned(I,T), assigned(I,TT), neq(T,TT). :- person(I), person(J), table(T), table(TT), together(I,J), assigned(I,T), assigned(J,TT), neq(T,TT). :- person(I), person(J), table(T), separate(I,J), assigned(I,T), assigned(J,T). together(1,2). together(7,4). together(6,8). separate(2,3). separate(3,4). separate(5,6). separate(9,4). hide person(X). hide table(X). hide together(X,Y). hide separate(X,Y). ******************************************** *** PROGRAM 13, for smodels *** By Michael Gelfond (mgelfond@cs.ttu.edu) ******************************************** % There is one to one correspondence % between the solutions and the sets of atoms of the % form at(person,table) from stable models of our program. %%%%%%%%% INPUT const n=10. % number of tables const m=10. % number of chairs const k=n*m. % number of people table(1..n). person(1..k). % The input database. We assume the data to be correct. like(1,2). like(3,4). like(5,6). like(10,13). like(10,11). like(4,5). dislike(1,5). dislike(1,6). dislike(12,16). dislike(13,14). dislike(7,8). dislike(7,9). % Symmetry Rules like(X,Y) :- like(Y,X), person(X), person(Y). dislike(X,Y) :- dislike(Y,X), person(X), person(Y). %%%%%%%%%%% SOLUTION % SELECT a candidate solution - m people to seat at each table m{at(P,T) : person(P)}m :- table(T). % People who dislike each other should seat at different tables :- table(T), person(P1), person(P2), at(P1,T), at(P2,T), dislike(P1,P2). % People who like each other should seat at the same table :- table(T), person(P1), person(P2), at(P1,T), not at(P2,T), like(P1,P2). % A person is seated at at most one table. :- table(T1), table(T2), neq(T1,T2), person(P), at(P,T1), at(P,T2). hide like(A,B). hide dislike(A,B). hide person(A). hide table(A). ********************************************* *** PROGRAM 14, for smodels *** By Marcello Balduccini (marcy@cs.ttu.edu) ********************************************* % Objects % ------- % % o Tables (N) % o Chairs (M) % o Guests (MN) % % Relations % --------- % % o SModels Types (table/1, chair/1, guest/1) % % o Guest G1 likes guest G2 % likes(G1,G2) % % o Guest G1 dislikes guest G2 % dislikes(G1,G2) % % o Guest g sits at table t on chair c % sits(g,t,c) % no two guests can sit on the same chair at the same table :- guest(G1), guest(G2), table(T), chair(C), sits(G1,T,C), sits(G2,T,C), neq(G1,G2). % a guest cannot sit in two different positions at the same time :- guest(G), table(T1), chair(C1), table(T2), chair(C2), sits(G,T1,C1), sits(G,T2,C2), neq(T1,T2). :- guest(G), table(T), chair(C1), chair(C2), sits(G,T,C1), sits(G,T,C2), neq(C1,C2). % if G1 likes G2, then G1 and G2 cannot be at different tables :- guest(G1), guest(G2), table(T1), table(T2), chair(C1), chair(C2), likes(G1,G2), sits(G1,T1,C1), sits(G2,T2,C2), neq(T1,T2). % if G1 dislikes G2, then G1 and G2 cannot be at the same table :- guest(G1), guest(G2), table(T), chair(C1), chair(C2), dislikes(G1,G2), sits(G1,T,C1), sits(G2,T,C2). %--------> arrangement generation <---------- % assign a chair at a table to each guest sits(G,T,C) :- guest(G), table(T), chair(C), not other_location(G,T,C). other_location(G,T1,C1) :- guest(G), table(T1), table(T2), chair(C1), chair(C2), sits(G,T2,C2), neq(T1,T2). other_location(G,T,C1) :- guest(G), table(T), chair(C1), chair(C2), sits(G,T,C2), neq(C1,C2). ******************************************** *** PROGRAM 15, for smodels *** By Veena Mellarkod