:- main.

q:- 	statistics(runtime,_), 
	q8, statistics(runtime,[_,Y]), 
 	statistics(runtime,_), 
	write('time : '), write(Y), nl,
	q10, statistics(runtime,[_,Y1]), 
	write('time : '), write(Y1), nl,
	halt_or_else(0,true).




q8:-	q([1,2,3,4,5,6,7,8],C), 
	write(C), nl.

q10:-	q([1,2,3,4,5,6,7,8,9,10],C), 
	write(C), nl.

q(L,C):-
	perm(L,P), 
	pair(L,P,C),
	safe([],C).




perm([],[]).

perm(Xs,[Z|Zs]):-
	sel(Z,Xs,Ys), 
	perm(Ys,Zs).




sel(X,[X|Xs],Xs).    

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




pair([],[],[]).

pair([X|Y],[U|V],[p(X,U)|W]):-
	pair(Y,V,W).




safe(X,[]).

safe(X,[Q|R]):-
	test(X,Q),
	safe([Q|X],R).




test([],X).

test([R|S],Q):-
	test(S,Q),
	nd(R,Q).




nd(p(C1,R1),p(C2,R2)):-
	C  is C1-C2, 
	R  is R1-R2, C=\=R,
	NR is R2-R1, C=\=NR.




:- q.