Specifying a simple puzzle in CLP

Hello marvelous Prolog community,
I watched Vsauces’ recent Future of Reasoning video on YouTube (https://youtu.be/_ArVh3Cj9rw?t=590) where he presented his audience with a simple logical puzzle:

Paul is looking at Mary.
Mary is looking at Peter.
Paul is married.
Peter is unmarried.

Is a married person looking at an unmarried person?

I wanted to specify this puzzle in Prolog, naturally I turned to clp libraries for this. I ended up using the following formulation:

:- use_module(library(clpfd)).

?- [Paul, Peter, Mary] ins 0..1,
   LookingAts = [Paul-Mary, Mary-Peter],
   Paul #= 1, Peter #= 0,
   member(1-0, LookingAts).
Paul = 1,
Peter = Mary, Mary = 0,
LookingAts = [1-0, 0-0] ;
Paul = Mary, Mary = 1,
Peter = 0,
LookingAts = [1-1, 1-0].

I encoded married as 1 and unmarried as 0, and placed looking at facts in a list which I eventually query to find solutions for a married person looking at an unmarried person with member(1-0, LookingAts)

I’m fairly inexperienced in clp and Prolog generally, but still I don’t find this solution overly satisfactory. Is there perhaps a more elegant, perhaps more readable or idiomatic way of expressing this puzzle?

Regards,
Drazen

Hi and welcome!

Can’t you do it as follows?

p(paul, looksAt, mary).
p(mary, looksAt, peter).
married(paul).
unmarried(peter).

With the query ?-married(X), p(X, looksAt, Y), unmarried(Y).

Or you explicitly wanted to use CLP?

Cheers/JCR

1 Like

If you try that simple program, you’ll find that the query fails.

However, if you know that a person is either married or unmarried, then you can try adding the fact married(mary), in which case you’ll get success (mary looks at peter); and if you try instead adding the fact unmarried(mary)', you’ll also get success (paul looks at mary).

So, the trick is encoding the married state as either married or unmarried, and setting up Mary accordingly. You can’t just have both married and unmarried facts for Mary; but you can have the married state as a list of Person-MarriedOrUnmarried.

looking_at(paul, mary).
looking_at(mary, peter).

married_state([paul-married,
               peter-unmarried,
               mary-M]) :-
    M = married ; M = unmarried.

query(P1, P2) :-
    married_state(MarriedState),
    looking_at(P1, P2),
    member(P1-married, MarriedState),
    member(P2-unmarried, MarriedState),
    P1 \= P2.

?- query(P1,P2).
P1 = mary, P2 = peter ;
P1 = paul, P2 = mary ;
false.

This isn’t a complete solution … you need to try all possible values of MarriedState and verify that the rest of the query succeeds. I’ll leave that extra piece as an exercise. :wink:

2 Likes

Thanks a lot Jean-Christophe and Peter!

Re JCR: As Peter suggested, there’s this silent fact that Mary can indeed be either married or unmarried, which, when considered explicitly, gives us solutions.

Re Peter: I like your solution as it’s pure Prolog and straight to the point. married_state represents world choices we’re searching through, very cool.

Hmmm, I honestly don’t see what’s lacking from your solution. married_state succeeds twice as that’s how many possible states there are:

married_state([paul-married,
               peter-unmarried,
               mary-M]) :-
    M = married ; M = unmarried.
?- married_state(X).
X = [paul-married, peter-unmarried, mary-married] ;
X = [paul-married, peter-unmarried, mary-unmarried].

I wonder what I’m missing :slight_smile:

1 Like

You’re running the test manually. A true programmer runs the tests with automation. :wink:
The all_query/0 predicate below will succeed if all states can have a married person looking at an unmarried person (if it fails, it might print out some intermediate results … again, I leave cleaning that up as an exercise).

This is essentially the same code as before, except I’ve added a MarriedState argument to query/2 (making it query/3) and added a query_all/0 predicate to verify that for all possible values from married_state/1 the query succeeds.

looking_at(paul, mary).
looking_at(mary, peter).

married_state([paul-married,
               peter-unmarried,
               mary-M]) :-
    M = married ; M = unmarried.

query(P1, P2, MarriedState) :-
    looking_at(P1, P2),
    member(P1-married, MarriedState),
    member(P2-unmarried, MarriedState),
    P1 \= P2.

all_query :-
    forall(married_state(MS),
           ( query(P1, P2, MS),
             format('~w looking at ~w with state=~w~n', [P1, P2, MS])
           )).
?- all_query.
mary looking at peter with state=[paul-married,peter-unmarried,mary-married]
paul looking at mary  with state=[paul-married,peter-unmarried,mary-unmarried]
3 Likes