reverse(List,RevList) :- rev(List,[],RevList).

rev([],Ys,Ys).
rev([X|Xs],Ys,Zs) :- rev(Xs,[X|Ys],Zs).

subList(SubList, List) :- append(_,SubList,Prefix), append(Prefix,_,List).

append([],Ys,Ys).
append([X|Xs],Ys,[X|Zs]) :- append(Xs,Ys,Zs).

perm([],[]).
perm([X|Xs],PXXs) :- perm(Xs,PXs), insert(X,PXs,PXXs).

insert(X,Ys,[X|Ys]).
insert(X,[Y|Ys],[Y|Zs]) :- insert(X,Ys,Zs).

% without using insert
perm2([],[]).
perm2([X|Xs],PXXs) :- perm2(Xs,PXs), append(Ys,Zs,PXs), append(Ys,[X|Zs],PXXs).


houseLines([(1,2),(1,4),(1,5),(2,3),(2,4),(2,5),(3,4),(4,5)]).

findNiko(Niko) :-
        houseLines(Lines),
        perm(Lines,NikoUndir),
        flip(NikoUndir,Niko),
        niko(Niko).

flip([],[]).
flip([(X,Y)|XYs],[(X,Y)|YXs]) :- flip(XYs,YXs).
flip([(X,Y)|XYs],[(Y,X)|YXs]) :- flip(XYs,YXs).

niko([]).
niko([_]).
niko([(_,X),(X,Y)|Zs]) :- niko([(X,Y)|Zs]).

% | ?- findNiko(Niko).
% Niko = [(1,4),(4,2),(2,1),(1,5),(5,2),(2,3),(3,4),(4,5)] ? 
% yes

% | ?- findall(X,findNiko(X),Ys), length(Ys,NumSols).
% Ys = ..., NumSols = 88 ? 
% yes

% more efficient version (without using perm)
findNiko2(Niko) :-
        houseLines(LinesUndir),
        flip(LinesUndir,Lines),
        insert(Line,RestLines,Lines),
        extend(RestLines,[Line],Niko).

% search for valid line to extend with
extend([],Niko,Niko).
extend(XYXYs,[(Y,Z)|YZs],Niko) :-
        insert((X,Y),XYs,XYXYs),
        extend(XYs, [(X,Y),(Y,Z)|YZs], Niko).

% | ?- findNiko2(Niko).
% Niko = [(1,4),(4,2),(2,3),(3,4),(4,5),(5,1),(1,2),(2,5)] ? 
% yes

% | ?- findall(X,findNiko2(X),Ys), length(Ys,NumSols).
% Ys = ..., NumSols = 88 ? 
% yes