Can constraint satisfaction problems be solved with Prolog?

Question

Is "party attendance" type of problems solvable in Prolog? For example:

Burdock Muldoon and Carlotta Pinkstone both said they would come if Albus Dumbledore came. Albus Dumbledore and Daisy Dodderidge both said they would come if Carlotta Pinkstone came. Albus Dumbledore, Burdock Muldoon, and Carlotta Pinkstone all said they would come if Elfrida Clagg came. Carlotta Pinkstone and Daisy Dodderidge both said they would come if Falco Aesalon came. Burdock Muldoon, Elfrida Clagg, and Falco Aesalon all said they would come if Carlotta Pinkstone and Daisy Dodderidge both came. Daisy Dodderidge said she would come if Albus Dumbledore and Burdock Muldoon both came. Whom is needs to be persuaded to attend the party in order to ensure that all her invitees attend?

I have tried to express this in GNU Prolog:

attend(BM) :- attend(AD).
attend(CP) :- attend(AD).
attend(AD) :- attend(CP).
attend(DD) :- attend(CP). 
attend(AD) :- attend(EC).
attend(BM) :- attend(EC).
attend(CP) :- attend(EC). 
attend(CP) :- attend(FA).
attend(DD) :- attend(FA).
attend(BM) :- attend(CP),attend(DD).
attend(EC) :- attend(CP),attend(DD).
attend(FA) :- attend(CP),attend(DD).
attend(DD) :- attend(AD),attend(BM).

attend(FA). /* try different seed invitees in order to see if all would attend*/

/* input:
write('invited:'),nl,
  attend(X),write(X),nl,
  fail.*/

I'm experiencing stack overflow (no pun), and have no knowledge of prolog evaluation, this is why I'm asking.

Generally speaking, this problem can be cast into Boolean CNF satisfaction formula (with 6 boolean variables). Therefore, does the prolog perspective have any merit?

Answer 1

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&<Z\end{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.

Answer 2

As spotted by svick, the first issue with the code in the OP is that names beginning with upper-case letters are variables in Prolog. So admit(CP) :- admit(AD) is equivalent to attend(X) :- attend(Y), which results in Prolog immediately entering an infinite loop trying to demonstrate that attend holds for some term by finding some term for which attend holds.

However, if you meant each set of initials to be a concrete distinct term, then you'll still run into a stack overflow because you have cycles, e.g.

attend(cp) :- attend(ad).
attend(ad) :- attend(cp).

So to work out whether attend(cp) holds Prolog will try to determine whether attend(ad) holds, which it will do by checking whether attend(cp) holds, and so on until stack overflow.

I don't believe vanilla Prolog makes any attempt to determine whether there is such a cycle, and examine other ways to make one of attend(cp) or attend(ad) true rather than get stuck in an infinite loop.

There may or may not be versions of Prolog that support such a feature. I'm more familiar with Mercury, and I think Mercury's "minimal model tabling" is exactly what you need for this case. I've never actually used it, but my understanding is it more-or-less allows a term that implies itself to be considered true if there is some other way of proving it, or false otherwise, without getting caught in an infinite loop. See the relevant section of the Mercury docs, and if you're interested a paper describing the implementation.

Mercury is an enforced-purity logical programming language, with similar syntax to Prolog but strong type and mode systems, and it's compiled rather than interpreted.

I've just re-skimmed the introduction to the paper (which I haven't read in a while), and it mentions tabling having been implemented in several versions of Prologs, so it may be that you can get further by googling for tabling in Prolog.

Answer 3

I found the following paper on SAT solving using prolog:

• A Pearl on SAT Solving in Prolog by Jacob M. Howe and Andy King

An implementation of the solver can be found here.

See this stackoverflow answer for details on the code and how to use it.

Answer 4

Putting aside the lowercase/uppercase issue, there is a cycle in the clauses:

attend(cp) :- attend(ad).
attend(ad) :- attend(cp).

So when you call a top-down interpreter, it will loop. You might have more luck with Answer Set Programming (ASP), which works bottom up. Here is a coding via library(minimal/asp):

:- use_module(library(minimal/asp)).

choose([admit(bm)]) <= posted(admit(ad)).
choose([admit(cp)]) <= posted(admit(ad)).
choose([admit(ad)]) <= posted(admit(cp)).
choose([admit(dd)]) <= posted(admit(cp)).
choose([admit(ad)]) <= posted(admit(ec)).
choose([admit(bm)]) <= posted(admit(ec)).
choose([admit(cp)]) <= posted(admit(ec)).
choose([admit(cp)]) <= posted(admit(fa)).
choose([admit(dd)]) <= posted(admit(fa)).
choose([admit(bm)]) <= posted(admit(cp)),posted(admit(dd)).
choose([admit(ec)]) <= posted(admit(cp)),posted(admit(dd)).
choose([admit(fa)]) <= posted(admit(cp)),posted(admit(dd)).
choose([admit(dd)]) <= posted(admit(ad)),posted(admit(bm)).

choose([admit(fa)]) <= posted(init).

Here is an example run:

Jekejeke Prolog 3, Runtime Library 1.3.8 (23 May 2019)

?- post(init), listing(admit/1).
admit(fa).
admit(cp).
admit(ad).
admit(bm).
admit(dd).
admit(ec).