/* Examen de Programmation par Contraintes 2024/2025, corrigé de l'exo 3
                              préparé par Mr Isli (amar.isli@usthb.edu.dz) */
:-use_module(library('clp/bounds')).
/* prédicat coloriage testé avec les deux questions suivantes :
    ?- coloriage(
    ?-
*/
coloriage(N,P,M,Vars):-length(Vars,N), /* nombre de variables du CSP = nombre de sommets du graphe */
	/* domaine commun des variables = {1, ..., P} */
	Vars in 1..P,
	/* extraire les contraintes du CSP, qui sont toutes des contraintes 'différent' :
	   pour tout I<J tq sommets I et J reliés par une arête, extraire contrainte XI#\=XJ */
	ext_cont(1,2,N,Vars,M),
	/* nous avons toutes les données du CSP : appel du solveur */
	label(Vars),
	write('Solution = '),
	writeln(Vars).
ext_cont(N,_,N,_,_):-!.
ext_cont(I,J,N,Vars,M):-J>N,
	!,
	Iplus1 is I+1,
	Iplus2 is I+2,
	ext_cont(Iplus1,Iplus2,N,Vars,M).
ext_cont(I,J,N,Vars,[0|M]):-!,
	Jplus1 is J+1,
	ext_cont(I,Jplus1,N,Vars,M).
ext_cont(I,J,N,Vars,[_|M]):-Imoins1 is I-1,
	length(Vars1,Imoins1),
	append(Vars1,[XI|_],Vars),
	Jmoins1 is J-1,
	length(Vars2,Jmoins1),
	append(Vars2,[XJ|_],Vars),
	XI#\=XJ,
	Jplus1 is J+1,
	ext_cont(I,Jplus1,N,Vars,M).