Search code examples
prologbacktrackingunificationfamily-tree

Prolog: Unification or Backtracking errors in program


I have a simple knowledge base that encodes a family tree. Some important rules in this representation are as follows:

% fathers
father(michael,cathy).
father(michael,sharon).
father(charles_gordon,michael).
father(charles_gordon,julie).
father(charles,charles_gordon).
father(jim,melody).
father(jim,crystal).
father(elmo,jim).
father(greg,stephanie).
father(greg,danielle).
% mothers
mother(melody,cathy).
mother(melody,sharon).
mother(hazel,michael).
mother(hazel,julie).
mother(eleanor,melody).
mother(eleanor,crystal).
mother(crystal,stephanie).
mother(crystal,danielle).
% parents
parent(X,Y) :- father(X,Y).
parent(X,Y) :- mother(X,Y).
% men
male(michael).
male(charles_gordon).
male(charles).
male(jim).
male(elmo).
male(greg).
% women
female(cathy).
female(sharon).
female(julie).
female(hazel).
female(eleanor).
female(melody).
female(crystal).
female(stephanie).
female(danielle). 

person(X) :- male(X) ; female(X).
parent(X,Y) :- father(X,Y) ; mother(X,Y).          % X is parent of Y
child(X,Y) :- parent(Y,X).
elder(X,Y) :-   parent(X,Y).                       % X is an elder of Y, meaning X is a parent or an ancestor of Y
elder(X,Y) :-   parent(X,Z), elder(Z,Y).
junior(X,Y) :-  child(X,Y).                        % X is a junior of Y, meaning X is a child or some descendant of Y
junior(X,Y) :-  child(X,Z), junior(Z,Y).

I am attempting to find the nearest elder between two individuals(predicate ne(X,Y,Z)). This individual Z is the elder of both X and Y, and no junior of Z is also an elder of BOTH X and Y.

My attempt looks like this:

ne(X,Y,Z) :-    person(X),
            person(Y),
            X \= Y,
            elder(Z,X),
            elder(Z,Y),
            junior(A,Z),
            not(elder(A,X)),
            not(elder(A,Y)).

but this is somehow incorrect, because whenever I run ?- ne(stephanie,cathy,Z). i get

Z = jim ;
Z = jim ;
Z = jim ;
Z = jim ;
Z = elmo ;
Z = elmo ;
Z = elmo ;
Z = elmo ;
Z = eleanor ;
Z = eleanor ;
Z = eleanor ;
Z = eleanor ;

but i'm only supposed to get one answer, and I can't figure out what's wrong. Thanks!


Solution

  • from this graph

    enter image description here seems this answer is correct

    ?- ne(stephanie,cathy,A).
    A = eleanor ;
    A = jim.
    

    here is my attempt to ne/3

    ne(X,Y,Z) :-
        setof(A, (
            elder(A, X),
            elder(A, Y),
            X \= Y,
            \+ (elder(A, T), elder(T, X) , elder(T, Y) ))
        , As), member(Z, As).
    

    not sure it's the better way...

    Setof/3 (joined with member/2) is used to eliminate duplicate answers, since we get

    ?- aggregate(count,A^ne(stephanie,cathy,A),N).
    N = 32.
    

    with this core logic

    ne(X,Y,A) :-
            elder(A, X),
            elder(A, Y),
            X \= Y,
            \+ (elder(A, T), elder(T, X) , elder(T, Y)).
    

    note variable A replaces locally the original Z

    edit

    I didn't took in account the savvy comment by @Boris, but after removing the duplicate parent/2 definition, the setof/3+member/2 trick become useless.