:-use_module(library('clp/bounds')).

/* TP 1 Exo 3 */
fusion_lt([],L,L):-!.
fusion_lt(L,[],L):-!.
fusion_lt([X|L1],[Y|L2],[X|L3]):-X=<Y,
	!,
	fusion_lt(L1,[Y|L2],L3).
fusion_lt(L1,[X|L2],[X|L3]):-fusion_lt(L1,L2,L3).

/* TP 1 Exo 4 */
supp_occ_se2([],[]).
supp_occ_se2([X],[X]).
supp_occ_se2([X,Y|L1],[X|L2]):-supp_toutes(X,[Y|L1],L3),
	supp_occ_se2(L3,L2).
supp_toutes(_,[],[]):-!.
supp_toutes(X,[X|L1],L2):-!,
	supp_toutes(X,L1,L2).
supp_toutes(X,[Y|L1],[Y|L2]):-supp_toutes(X,L1,L2).

/* TP 1 Exo 5 */
tri_sel([X],[X]).
tri_sel([X,Y|L1],[Z|L2]):-min([X,Y|L1],Z),
	supp_occ1(Z,[X,Y|L1],L3),
	tri_sel(L3,L2).
min([X],X):-!.
min([X,Y|L1],Min):-min([Y|L1],Min),
	Min=<X,
	!.
min([X|_],X).
supp_occ1(X,[X|L],L):-!.
supp_occ1(X,[Y|L1],[Y|L2]):-supp_occ1(X,L1,L2).

/* Solveur de CSP discrets de Swi-Prolog :
   illustration avec CSP modélisant l'instance "coloriage d'un triangle avec 3 couleurs"
   du problème de coloriage d'un graphe */
col_tri(Vars):-Vars=[X1,X2,X3],
	Vars in 1..3,
	X1#\=X2,
	X1#\=X3,
	X2#\=X3,
	/* la conjonction des trois contraintes ci-dessus peut être exprimée
	   avec la contrainte globale all_different(Vars) */
	label(Vars).

/* TP 2 : le problème des N reines
   Testez avec la question suivante :
   ? reinesN(Vars,6).
*/
reinesN(Vars,N):-length(Vars,N),
	Vars in 1..N,
	/* contraintes :
	  1) contraintes lignes
	  2) contraintes diagonales :
	       a) diagonales ascendantes : parallèles à la 1ère biss des axes ==> Xi-Xj#\=i-j
	       b) diagonales descendantes : parallèles à la 2ème biss des axes ==> Xi-Xj#\=-i+j */
	all_different(Vars),
	cont_diag(1,Vars),
	label(Vars).
cont_diag(_,[_]):-!.
cont_diag(I,[XI|Vars]):-Iplus1 is I+1,
	dist(XI,I,Iplus1,Vars),
	cont_diag(Iplus1,Vars).
dist(_,_,_,[]):-!.
dist(XI,I,J,[XJ|Vars]):-XI-XJ#\=I-J,
	XI-XJ#\=J-I,
	Jplus1 is J+1,
	dist(XI,I,Jplus1,Vars).

/* TP 3 : le sudoku
   Testez avec la question suivante :
   ? sudoku([1,0,0,0,0,0,0,0,0,
	     0,2,0,0,0,0,0,0,0,
	     0,0,3,0,0,0,0,0,0,
	     0,0,0,4,0,0,0,0,0,
	     0,0,0,0,5,0,0,0,0,
	     0,0,0,0,0,6,0,0,0,
	     0,0,0,0,0,0,7,0,0,
	     0,0,0,0,0,0,0,8,0,
	     0,0,0,0,0,0,0,0,9],Vars) */
sudoku(Init,Vars):-length(Init,81),
	length(Vars,81),
	Vars in 1..9,
	/* contraintes :
	    contraintes lignes
	    contraintes colonnes
	    contraintes carrés
	    contraintes initialisation
	*/
	    contLignes(Vars),
	    contColonnes(1,Vars),
	    contCarres(1,Vars),
	    contInit(Init,Vars),
	/* appel du solveur */
	label(Vars),
	afficher(1,Vars).
afficher(I,_):-I>81,
	!.
afficher(I,[X|L]):-Reste is I mod 9,
	Reste==0,
	!,
	write(X),
	write(' '),
	nl,
	Iplus1 is I+1,
	afficher(Iplus1,L).
afficher(I,[X|L]):-write(X),
	write(' '),
	Iplus1 is I+1,
	afficher(Iplus1,L).
contLignes([]):-!.
contLignes(Vars):-length(L1,9),
	append(L1,L2,Vars),
	all_different(L1),
	contLignes(L2).
contColonnes(I,_):-I>9,
	!.
contColonnes(I,Vars):-extColonne(I,CI,Vars),
	all_different(CI),
	Iplus1 is I+1,
	contColonnes(Iplus1,Vars).
extColonne(_,_,[]):-!.
extColonne(I,[XI|L1],Vars):-Imoins1 is I-1,
	length(L2,Imoins1),
	append(L2,[XI|_],Vars),
	length(L4,9),
	append(L4,L5,Vars),
	extColonne(I,L1,L5).
contCarres(I,_):-I>9,
	!.
contCarres(I,Vars):-extCarre(I,CarreI,Vars),
	all_different(CarreI),
	Iplus1 is I+1,
	contCarres(Iplus1,Vars).
extCarre(I,[X1,X2,X3,X4,X5,X6,X7,X8,X9],Vars):-Quotient is (I-1) div 3,
	Reste is (I-1) mod 3,
	Longueur1 is Quotient*27+Reste*3,
	length(L1,Longueur1),
	append(L1,[X1,X2,X3|_],Vars),
	Longueur2 is Longueur1+9,
	length(L2,Longueur2),
	append(L2,[X4,X5,X6|_],Vars),
	Longueur3 is Longueur2+9,
	length(L3,Longueur3),
	append(L3,[X7,X8,X9|_],Vars).
contInit([],_):-!.
contInit([0|L1],[_|L2]):-!,
	contInit(L1,L2).
contInit([C|L1],[X|L2]):-X#=C,
	contInit(L1,L2).