Can constraint satisfaction problems be solved with Prolog?

To solve a problem with Prolog, as with any programming language, be it declarative or imperative, you have to think about the representation of the solution and the input. Since this is a programming question, it would’ve been popular on StackOverflow.com where programmers solve programming problems. Here I would attempt to be more scientific. To solve the problem in the OP one has to reverse the relation defined by the dependencies stated in the input. Clauses of the form $Attend(X) to Attend(Y) wedge Attend(Z)$ are easy to reverse. The clauses $Attend(AD)wedge Attend(BM)to Attend(DD)$ like

Daisy Dodderidge said she would come if Albus Dumbledore and Burdock Muldoon both came

are more difficult to treat. With Prolog the first simple approach is to avoid a full reversal of the relationship and be goal directed instead. Assume an ordering on the list of guests and use a rule $qquad left{begin{align} A(X)wedge A(Y) &to A(Z), A(W)&to A(X), A(W)&to A(Y), X&<Z, Y&<Zend{align}right}quad vdash quad A(W) to A(Z)$ (We use $A(X)$ instead of $Attend(X)$ to keep it short) This rule is easy to implement. A rather naive approach For readability let follows be the relation given as an input, and brings be its reverse. Then the input is given by

follows(bm,[ad]). follows(cp,[ad]). follows(ad,[cp]). follows(dd,[cp]). follows(ad,[ec]). follows(bm,[ec]). follows(cp,[ec]). follows(cp,[fa]). follows(dd,[fa]). follows(bm,[cp,dd]). follows(ec,[cp,dd]). follows(fa,[cp,dd]). follows(dd,[ad,bm]). 

And brings can be defined as follows:

brings(X,S):-brings(X,S,[]).  brings(_X,[],_S). brings(X,[X|L],S):-brings(X,L,[X|S]). brings(X,[Y|L],S):-follows(Y,[X]),brings(X,L,[Y|S]). brings(X,[Y|L],S):-follows(Y,[A,B]),           member(A,S),member(B,S),brings(X,L,[Y|S]). 

Here the third argument in brings/3(X,L,S) is the list of guests that were already proven to attend if $X$ attends. If we define

 partymaker(X):-Guests=[ad,bm,cp,dd,ec,fa],member(X,Guests),brings(X,Guests). 

We get the following unique solutions:

 [ad,ec] 

This is not the complete list, since under the alphabetical ordering the clause

 follows(bm,[cp,dd]). 

is not working. A rather involved solution to the original puzzle To solve the problem completely you have to actually let the system try to prove attendance for later guests without introducing infinite loops to the search tree. There are multiple ways to accomplish this goal. Each has its advantages and disadvantages. One way is to redefine brings/2 as follows:

brings(X,S):-brings(X,S,[],[]).  % brings(X,RemainsToBring,AlreadyTaken,AlreadyTried). % % Problem solved brings(_X,[],_S,_N).  % Self brings(X,[X|L],S,N):-brings(X,L,[X|S],N).  % Follower brings(X,[Y|L],S,N):-follows(Y,[X]),brings(X,L,[Y|S],N).  % Y is not a follower, but X can bring 2 brings(X,[Y|L],S,N):- +member(Y,N),+follows(Y,[X]),                     follows(Y,[A,B]),                    try_bring(X,A,L,S,[Y|N]),                    try_bring(X,B,L,S,[Y|N]),brings(X,L,[Y|S],N). % Y is not a follower, but X can bring 1 brings(X,[Y|L],S,N):- +member(Y,N),+follows(Y,[X]),+follows(Y,[_A,_B]),                     follows(Y,[C]),                    try_bring(X,C,L,S,[Y|N]),brings(X,L,[Y|S],N).  try_bring(_X,A,_L,S,_N):-member(A,S). try_bring(X,A,L,S,N):- +member(A,S),sort([A|L],Y),brings(X,Y,S,N). 

The last argument in brings/4 is necessary to avoid an infinite loop in try_bring. This gives the following answers: Albus, Carlotta, Elfrida and Falco. However this solution is not the most efficient one since backtracking is introduced where it sometimes can be avoided. A general solution After the link to the Third International NoCOUG SQL & NoSQL Challenge was added to the original question, it became clear that what we are after is a general reachability checker on the set of subsets of the set of guests, where the transition relation is defined by rules given such that an application of the rule $r(X,S): V to V’$ is a guarded command:

if $S subseteq V$ then $V’ = V cup {X}$.

We are interested in the minimal subsets $V$ such that the whole set $U$ of guests is reachable from $V$ after a finite sequence of rule applications.

add_element(X,V,U):- ( var(V) -> % set difference that works in both modes                            member(X,U),subtract(U,[X],V);                       +member(X,V),sort([X|V],U) ).  support(V,U):- guests(G), % rule application                member(X,G),                add_element(X,V,U),                follows(X,S),                subset(S,V).  set_support(U,V):- support(V1,U), % sort of a minimal set                ( support(_V2,V1) ->                        set_support(V1,V) ;                   V = V1).   is_duplicate(X,[Y|L]):- ( subset(Y,X) ; is_duplicate(X,L) ).  % purging solutions that are not truly minimal minimal_support(U,L):-minimal_support(U,[],L). minimal_support([],L,L). minimal_support([X|L],L1,L2):-( append(L,L1,U),is_duplicate(X,U) ->                                      minimal_support(L,L1,L2);                                  minimal_support(L,[X|L1],L2) ).   solution(L):- guests(G),setof(X,set_support(G,X),S),               minimal_support(S,L). 

Now if for instance dataset #2 is given as

follows(fa,[dd,ec]). follows(cp,[ad,bm]). guests([ad,bm,cp,dd,ec,fa]). 

We get the answer L = [[ad, bm, dd, ec]]. Which means that all guests but Carlotte and Falco must be invited. The answers this solution gave me matched the solutions given in the Wicked Witch article with the exception of dataset #6, where more solutions were produced. This seems to be the correct solution. Finally, I must mention the CLP(FD) library of Prolog that is particularly suitable for this sort of problems.