/* Code Prolog de l'algorithme génère et teste */

genereEtTeste(Affectation) :-
	variables(Variables),
	genere(Variables,Affectation),
	teste(Affectation).

genere([],[]).
genere([X:DX|Variables],[(X,V)|Affectation]) :-
	member(V,DX),
	genere(Variables,Affectation).

teste([]).
teste([(Xi,Vi)|L]) :-
	teste((Xi,Vi),L),
	teste(L).

teste(_,[]).
teste((Xi,Vi),[(Xj,Vj)|L]) :-
	consistants((Xi,Vi),(Xj,Vj)),
	teste((Xi,Vi),L).

/* Code Prolog de l'algorithme simple retour arrière */

simpleRetourArriere(Affectation) :-
	variables(Variables),
	simpleRetourArriere(Variables,[],Affectation).

simpleRetourArriere([],_,[]).
simpleRetourArriere([X:DX|Variables],AffectationPartielle,[(X,V)|Solution]) :-
	member(V,DX),
	teste((X,V),AffectationPartielle),
	simpleRetourArriere(Variables,[(X,V)|AffectationPartielle],Solution).

/* Code Prolog de l'algorithme anticipation/noeud */

anticipation(Affectation) :-
	variables(Variables),
	anticipation(Variables,[],Affectation).

anticipation([],_,[]).
anticipation([X:DX|Variables],AffectationPartielle,[(X,V)|Solution]) :-
	member(V,DX),
	filtre(X,V,Variables,VariablesFiltres),
	anticipation(VariablesFiltres,[(X,V)|AffectationPartielle],Solution).

filtre(_,_,[],[]).
filtre(Xi,Vi,[Xj:Dj|Variables],[Xj:DjFiltre|DomainesFiltres]) :-
	bagof(Vj, (member(Vj,Dj),consistants((Xi,Vi),(Xj,Vj))), DjFiltre),
	DjFiltre \= [],
	filtre(Xi,Vi,Variables,DomainesFiltres).

/* Code Prolog de l'algorithme anticipation/noeud avec l'heuristique échec d'abord */

echecDabord(Affectation) :-
	variables(Variables),
	echecDabord(Variables,[],Affectation).

echecDabord([],_,[]).
echecDabord(Variables,AffectationPartielle,[(X,V)|Solution]) :-
	extraitMin(Variables,X:DX,VariablesSansX),
	member(V,DX),
	filtre(X,V,VariablesSansX,VariablesFiltres),
	echecDabord(VariablesFiltres,[(X,V)|AffectationPartielle],Solution).

extraitMin([X:DX|Variables],Xmin:DXmin,VariablesSansXmin) :-
	length(DX,N),
	extraitMin(Variables,X:DX,N,Xmin:DXmin,VariablesSansXmin).

extraitMin([],X:DX,_,X:DX,[]).
extraitMin([X:DX|Variables],Y:DY,N,Z:DZ,[Y:DY|VariablesSansZ]) :-
	length(DX,M),
	M<N, !,
	extraitMin(Variables,X:DX,M,Z:DZ,VariablesSansZ).
	extraitMin([X:DX|Variables],Y:DY,N,Z:DZ,[X:DX|VariablesSansZ]) :-
	extraitMin(Variables,Y:DY,N,Z:DZ,VariablesSansZ).