:- use_module(library(apply), [maplist/2]).
:- use_module(library(dif), [dif/2]).
:- use_module(library(lists), [append/3, reverse/2, member/2]).

adj(a,6,b).
adj(a,1,c).
adj(b,3,c).
adj(b,1,e).
adj(c,2,f).
adj(c,6,g).
adj(d,1,h).
adj(e,1,d).
adj(e,2,f).
adj(f,5,h).
adj(f,8,i).
adj(g,4,i).
adj(h,5,i).

h(a, 10).
h(b, 5).
h(c, 6).
h(d, 7).
h(e, 5).
h(f, 7).
h(g, 3).
h(h, 4).
h(i, 0).

goal(i).

sol([_ | L], R) :-
    append(R, _, L),
    length(R, 4).

% DFS
dfs(X, [X]) :-
    goal(X).

dfs(X, [X | Sol]) :-
    adj(X, _, Y),
    dfs(Y, Sol).

% BFS
bfs(Start, Sol) :-
    bfs_aux([Start], [], Visited),
    reverse(Visited, Sol).

% bfs_aux(Queue, Visited, Solution)
bfs_aux([], Vis, Vis).

bfs_aux([N|Ns], Visited, Sol) :-
    maplist(dif(N), Visited),         % Ensure Node has not been visited yet
    findall(N1, adj(N, _, N1), Adjs), % Find all adjacent nodes
    append(Ns, Adjs, Ns1),
    bfs_aux(Ns1, [N|Visited], Sol).

bfs_aux([N|Ns], Visited, Sol) :-
    member(N, Visited),
    bfs_aux(Ns, Visited, Sol).

% Iterative Deepening

itd(X, Sol) :-
    itd(X, 0, Sol).

itd(X, N, Sol) :-
    dfsN(X, 0, N, Sol).

dfsN(_, D, N, []) :-
    D > N.

dfsN(X, D, N, [X | Sol]) :-
    D1 is D + 1,
    adj(X, _, Y),
    dfsN(Y, D1, N, Sol).