/* Examen de Programmation par Contraintes 2020/2021, corrigé de l'exo 3
                              préparé par Mr Isli (amar.isli@usthb.edu.dz) */
:-use_module(library('clp/bounds')).
somme([],[]):-!.
somme([L1|L2],[S|L3]):-somme_sousListe(L1,S),
	somme(L2,L3).
somme_sousListe([X],X):-!.
somme_sousListe([X,Y|L],S):-somme_sousListe([Y|L],S2),
	S is X+S2.
/* prédicat coloriage testé avec les deux questions suivantes :
    ?- coloriage(3,4,[[0,1,1,1],[1,1,0,1],[1,0,0,1],[1,1,1,0]],Vars).
    Vars = [1, 2, 2, 3] ;
    Vars = [1, 3, 3, 2] ;
    Vars = [2, 1, 1, 3] ;
    Vars = [2, 3, 3, 1] ;
    Vars = [3, 1, 1, 2] ;
    Vars = [3, 2, 2, 1].
    ?- coloriage(3,4,[[0,1,0,1],[1,1,0,1],[0,0,0,1],[1,1,1,0]],Vars).
    Vars = [1, 2, 1, 3] ;
    Vars = [1, 2, 2, 3] ;
    Vars = [1, 3, 1, 2] ;
    Vars = [1, 3, 3, 2] ;
    Vars = [2, 1, 1, 3] ;
    Vars = [2, 1, 2, 3] ;
    Vars = [2, 3, 2, 1] ;
    Vars = [2, 3, 3, 1] ;
    Vars = [3, 1, 1, 2] ;
    Vars = [3, 1, 3, 2] ;
    Vars = [3, 2, 2, 1] ;
    Vars = [3, 2, 3, 1].
    ?-
*/
coloriage(Nc,Ns,G,Vars):-length(Vars,Ns), /* nombre de variables du CSP = nombre de sommets du graphe */
	/* domaine commun des variables = {1, ..., Nc} */
	Vars in 1..Nc,
	/* vérifier que la matrice représentée par G est une matrice carrée Ns*Ns */
	verifier_matrice(Ns,G),
	/* 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,Vars,G),
	/* nous avons toutes les données du CSP : appel du solveur */
	label(Vars).
verifier_matrice(Ns,G):-length(G,Ns),
	longueur_sousListes(G,Ns).
longueur_sousListes([],_):-!.
longueur_sousListes([L1|L2],Ns):-length(L1,Ns),
	longueur_sousListes(L2,Ns).
ext_cont(_,_,[_]):-!.
ext_cont(I,Vars,[L1|L2]):-Imoins1 is I-1, /* L1 Ième ligne de la matrice d'adjacence */
	length(L3,Imoins1),
	append(L3,[XI|Vars2],Vars),       /* XI Ième variable de Vars et Vars2 variables
	                                     de Vars venant après XI */
	length(L4,Imoins1),
	append(L4,[_|L5],L1),		  /* L5 = Ligne L1 à partir de la position (I+1) */
	dist(XI,Vars2,L5),                /* contrainte XI#\=XJ entre XI et la variable XJ
	                                     de Vars2 d'indice J si arête entre XI et XJ,
					     c-à-d si Jème élément de L5 = 1 */
	Iplus1 is I+1,
	ext_cont(Iplus1,Vars,L2).
dist(_,[],_):-!.
dist(XI,[XJ|Vars],[1|L]):-!,
	XI#\=XJ,
	dist(XI,Vars,L).
dist(XI,[_|Vars],[_|L]):-dist(XI,Vars,L).