Prolog falling into infinite loop

prolog

Solution

1) I don't think that you end in an infinite loop, but you let your program explore all ways that two people are connected, which will be a very large number. Since you probably are only interested in whether they are connected at all, you should add cuts at the end of the `connected/3` clauses that will prevent backtracking once you have successfully determined that two people are connected, e.g.:

connected(X,Y,_) :- X == Y,!.
connected(X,Y,Visited) :- 
    ancestor(X,Z),
    notmember(Z,Visited),
    connected(Z,Y,[Z|Visited]),!.
...

2) I didn't get infinitely increasing values for N when I tested your code, but still the `distance/3` predicate would determine different paths how two people are connected. Depending on the people, the minimum distance would not be the first to be computed. I would change the definition of `distance/3` to something like this:

distance(X,Y,N) :- 
    findall(N0, distance(X,Y,[],N0), Ns), !,
    minimum(N, Ns).

This is reusing your `minimum/2` predicate. Note that you should add cuts to the first two clauses of this predicate in order to avoid spurious choicepoints.

Regarding your additional questions:

3) you have to distinguish between looking for the smallest N and looking for people matching degree N:

distance(X,Y,N) :-
  nonground(N),!,
  findall(N0, distance(X,Y,[],N0), Ns), !,
  minimum(N, Ns).
distance(X,Y,N) :-
  distance(X,Y,[X],N).

Also, you need to remove the cuts that you added to `distance/4`. This is different from the cuts added to `connected/3`!

There's probably a better way that avoids distinguishing between these two modes, but all I can think of at the moment is using some kind of breadth-first-search (in order to guarantee the minimum degree)...

4) I don't get duplicate answers for queries like `?- connected(X,victoria).` Do you have an example?

Problem

I have two problems that have bugged me for hours. `connected/2` is supposed to judge whether two people are connected or not; `distance/3` is supposed to measure the kinship. But: - I keep getting `true`s infinitely for the query `connected(x,y)`; - and I'm getting infinitely increasing `N` for `distance(x,y,N)` query. Any suggestions? Here are my facts: ``` male(ted). male(barney). male(ranjit). male(marshall). male(tony). male(swarley). male(steve). male(chuck). male(john). male(devon). male(morgan). female(robin). female(lily). female(wendy). female(stellar). female(abby). female(victoria). female(carina). female(sarah). female(ellie). married(ted, robin). married(marshall, lily). married(ranjit, wendy). married(stellar, tony). married(steve, carina). married(sarah, chuck). married(ellie, devon). father(ted, barney). father(ted, ranjit). father(marshall, wendy). father(ranjit, stellar). father(tony, abby). father(tony, swarley). father(tony, victoria). father(steve, chuck). father(steve, ellie). father(chuck, john). father(devon, morgan). mother(robin, barney). mother(robin, ranjit). mother(lily, wendy). mother(wendy, stellar). mother(stellar, abby). mother(stellar, swarley). mother(stellar, victoria). mother(carina, chuck). mother(carina, ellie). mother(sarah, john). mother(ellie, morgan). ``` Now, my predicates: ``` parent(X,Y) :- father(X,Y). parent(X,Y) :- mother(X,Y). son(X,Y) :- male(X), parent(Y,X). daughter(X,Y) :- female(X), parent(Y,X). sibling(X,Y) :- parent(Z,X), parent(Z,Y). cousin(X,Y) :- parent(Z,X), parent(W,Y), parent(G,Z), parent(G,W). ancestor(X,Y) :- parent(X,Z), ancestor(Z,Y). ancestor(X,Y) :- parent(X,Y). notmember(X,[]). notmember(X,[H|T]) :- X \= H, notmember(X,T). connected(X,Y,_) :- X == Y. connected(X,Y,Visited) :- ancestor(X,Z), notmember(Z,Visited), connected(Z,Y,[Z|Visited]). connected(X,Y,Visited) :- ancestor(Z,X), notmember(Z,Visited), connected(Z,Y,[Z|Visited]). connected(X,Y,Visited) :- sibling(X,Z), notmember(Z,Visited), connected(Z,Y,[Z|Visited]). connected(X,Y,Visited) :- married(X,Z), notmember(Z,Visited), connected(Z,Y,[Z|Visited]). connected(X,Y) :- connected(X,Y,[X]). minimum(X,[X]). minimum(X,[M,H|T]) :- M =< H, minimum(X,[M|T]). minimum(X,[M,H|T]) :- M > H, minimum(X,[H|T]). distance(X,X,_,0). distance(X,Y,Visited,N) :- parent(X,Z), notmember(Z,Visited), distance(Z,Y,[Z|Visited],N1), N is N1+1. distance(X,Y,Visited,N) :- parent(Z,X), notmember(Z,Visited), distance(Z,Y,[Z|Visited],N1), N is N1+1. distance(X,Y,N) :- distance(X,Y,[],N). ``` EDIT: Thank you, i think i've managed to solve half way through the problems now. Taking @twinterer's advice, I have fixed the predicates like this ``` connected(X,Y,_) :- X == Y. connected(X,Y,V) :- married(X,Z), notmember(Z,V), connected(Z,Y,[Z|V]),!. connected(X,Y,V) :- sibling(X,Z), notmember(Z,V), connected(Z,Y,[Z|V]),!. connected(X,Y,V) :- parent(X,Z), notmember(Z,V), connected(Z,Y,[Z|V]),!. connected(X,Y,V) :- parent(Z,X), notmember(Z,V), connected(Z,Y,[Z|V]),!. connected(X,Y) :- connected(X,Y,[X]). minimum(X,[X]). minimum(X,[M,H|T]) :- M =< H, minimum(X,[M|T]). minimum(X,[M,H|T]) :- M > H, minimum(X,[H|T]). count(X,[],0). count(X,[X|T],N) :- count(X,T,N1), N is N1+1. count(X,[H|T],N) :- X \== H, count(X,T,N1), N is N1. distance(X,X,Visited,0) :- count(X,Visited,N), N =< 1, !. distance(X,Y,Visited,N) :- parent(X,Z), (notmember(Z,Visited)-> distance(Z,Y,[Z|Visited],N1), N is N1+1 ; fail ),!. distance(X,Y,Visited,N) :- parent(Z,X), (notmember(Z,Visited)-> distance(Z,Y,[Z|Visited],N1), N is N1+1 ; fail ),!. distance(X,Y,N) :- findall(N1,distance(X,Y,[X],N1),L),!, minimum(N,L),!. ``` But there is a new set of problems now - it can't take arbitrary queries like `distance(X,y,n)` - queries like `connected(X,y)` return duplicate results I think removing duplicate results can be achieved by using that `findall/3` predicate, but I am clueless as to how I can actually implement it.

Original source