% Pour un affichage entier des solutions
:- set_prolog_flag(toplevel_print_options, [quoted(true), portray(true), max_depth(0), attributes(portray)]).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Les N reines
% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
% Cas terminal, la liste des reines à placer est vide.
% Cas général: la liste des reines à placer est [X/Y|Others]
% Il faut alors que:
% (1) Others soit elle même une solution.
% (2) X et Y sont des entiers compris entre 1 et N (ici N=8).
% (3) X/Y ne doit pas attaquer les reines présentes dans Others.
%
% Call: ?- template8(S), solution(S).
% Call: ?- findall(S, (template8(S),solution(S)), LS), length(LS,N).

solution([]).
solution([X/Y|Others]) :-
	solution(Others),
	member(Y, [1,2,3,4,5,6,7,8]),
	noattack(X/Y, Others).

noattack(_,[]).
noattack(X/Y,[X1/Y1|Others]) :-
	Y =\= Y1,
	Y1 - Y =\= X1 - X,
	Y1 - Y =\= X - X1,
	noattack(X/Y,Others).

template8([1/Y1,2/Y2,3/Y3,4/Y4,5/Y5,6/Y6,7/Y7,8/Y8]).


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Graphe orienté
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


% Base de faits
arc(a,b).
arc(a,c).
arc(b,c).
arc(b,d).
arc(c,d).

% DECOMMENTER LES 3 FAITS SUIVANTS A PARTIR DE LA QUESTION 8
%arc(a,a).
%arc(b,b).
%arc(c,c).

% Prédicat chemin
chemin(X,Y):- arc(X,Y).
chemin(X,Y):- arc(X,Z), chemin(Z,Y).

% Question 6:
% ?- findall(X->Y,chemin(X,Y),L), list_to_set(L,S).
% L = [ (a->b), (a->c), (b->c), (b->d), (c->d), (a->c), (a->d), (a->d), (a->d), (b->d)],
% S = [ (a->b), (a->c), (b->c), (b->d), (c->d), (a->d)].

% Prédicat qui stocke les noeuds parcourus
chemin_trace(X,Y,[X,Y]):- arc(X,Y).
chemin_trace(X,Y,[X|C]):- arc(X,Z), chemin_trace(Z,Y,C).


% Prédicat chemin_pertinent d'arité 3
chemin_pertinent(X,Y,C):- chemin_pertinent(X,Y,[X],C).

% Prédicat chemin_pertinent d'arité 4
chemin_pertinent(X,X,_,[X]).
chemin_pertinent(X,Y,C_partiel,[X|C]):-
	arc(X,Z),
	not(member(Z,C_partiel)),
	chemin_pertinent(Z,Y,[Z|C_partiel],C).


