%% FA13 5
link(san_diego, seattle).
link(seattle, dallas).
link(dallas, new_york).
link(new_york, chicago).
link(new_york, seattle).
link(chicago, boston).
link(boston, san_diego).

%% A)
path_2(A,B) :- link(A,C), link(C,B).


%% B)
path_3(A,B) :- link(A,C), path_2(C,B).

%% C)

% Case for N=1
path_N(A,B, N) :- N is 1, link(A,B).
% Case for N>1
path_N(A,B, N) :- N>1, M is N-1, link(A,C), path_N(C,B, M).

% Note that in the above rule, if we don't specify N>1, it will 
% loop eternally for queries like path_N(new_york, B, 2). Can you explain why?

%% D)
path(A,B) :- path_helper(A,B, [A]).

%% Base Case
path_helper(A,B,Seen) :- link(A,B), not(member(B, Seen)).

%% Inductive Case
path_helper(A,B,Seen) :- link(A,C), not(member(C, Seen)), path_helper(C,B, [C|Seen]).