% Title : Résolveur de Sudoku
% Autors : Luchez Lionel And Nimour Sonia
% Date : 17/06/2006
% Language : Prolog


% change_directory('C:\\').
% consult(sudoku).
% [sudoku].




sudoku([
		[8,4,0,9,0,0,0,0,0],
		[0,0,0,0,0,0,2,0,0],
		[0,0,0,6,5,0,3,0,4],
		[1,0,0,0,0,0,0,0,5],
		[0,7,0,0,6,0,0,1,0],
		[4,0,0,0,0,0,0,0,9],
		[2,0,5,0,4,3,0,0,0],
		[0,0,9,0,0,0,0,0,0],
		[0,0,0,0,0,2,0,5,7]
	]).



sudoku_moyen([
		[7,0,4,0,0,0,0,0,0],
		[5,0,0,0,3,2,0,0,0],
		[0,0,0,0,0,4,5,8,0],
		[0,6,2,0,0,0,0,0,0],
		[0,0,0,9,1,8,0,0,0],
		[0,0,0,0,0,0,3,4,0],
		[0,5,3,6,0,0,0,0,0],
		[0,0,0,7,4,0,0,0,9],
		[0,0,0,0,0,0,6,0,1]
	]).


sudoku_diabolique([
		[0,0,5,7,0,0,0,0,9],
		[0,7,0,0,0,0,0,4,8],
		[0,0,0,3,6,0,0,5,0],
		[0,0,0,5,0,3,4,2,0],
		[0,0,0,0,0,0,0,0,0],
		[0,3,2,4,0,8,0,0,0],
		[0,4,0,0,3,9,0,0,0],
		[1,8,0,0,0,0,0,9,0],
		[2,0,0,0,0,1,3,0,0]
	]).


listeCandidate([
	[[1,2,3,4,5,6,7,8,9],[1,2,3,4,5,6,7,8,9],[1,2,3,4,5,6,7,8,9],[1,2,3,4,5,6,7,8,9],[1,2,3,4,5,6,7,8,9],[1,2,3,4,5,6,7,8,9],[1,2,3,4,5,6,7,8,9],[1,2,3,4,5,6,7,8,9],[1,2,3,4,5,6,7,8,9]],
	[[1,2,3,4,5,6,7,8,9],[1,2,3,4,5,6,7,8,9],[1,2,3,4,5,6,7,8,9],[1,2,3,4,5,6,7,8,9],[1,2,3,4,5,6,7,8,9],[1,2,3,4,5,6,7,8,9],[1,2,3,4,5,6,7,8,9],[1,2,3,4,5,6,7,8,9],[1,2,3,4,5,6,7,8,9]],
	[[1,2,3,4,5,6,7,8,9],[1,2,3,4,5,6,7,8,9],[1,2,3,4,5,6,7,8,9],[1,2,3,4,5,6,7,8,9],[1,2,3,4,5,6,7,8,9],[1,2,3,4,5,6,7,8,9],[1,2,3,4,5,6,7,8,9],[1,2,3,4,5,6,7,8,9],[1,2,3,4,5,6,7,8,9]],
	[[1,2,3,4,5,6,7,8,9],[1,2,3,4,5,6,7,8,9],[1,2,3,4,5,6,7,8,9],[1,2,3,4,5,6,7,8,9],[1,2,3,4,5,6,7,8,9],[1,2,3,4,5,6,7,8,9],[1,2,3,4,5,6,7,8,9],[1,2,3,4,5,6,7,8,9],[1,2,3,4,5,6,7,8,9]],
	[[1,2,3,4,5,6,7,8,9],[1,2,3,4,5,6,7,8,9],[1,2,3,4,5,6,7,8,9],[1,2,3,4,5,6,7,8,9],[1,2,3,4,5,6,7,8,9],[1,2,3,4,5,6,7,8,9],[1,2,3,4,5,6,7,8,9],[1,2,3,4,5,6,7,8,9],[1,2,3,4,5,6,7,8,9]],
	[[1,2,3,4,5,6,7,8,9],[1,2,3,4,5,6,7,8,9],[1,2,3,4,5,6,7,8,9],[1,2,3,4,5,6,7,8,9],[1,2,3,4,5,6,7,8,9],[1,2,3,4,5,6,7,8,9],[1,2,3,4,5,6,7,8,9],[1,2,3,4,5,6,7,8,9],[1,2,3,4,5,6,7,8,9]],
	[[1,2,3,4,5,6,7,8,9],[1,2,3,4,5,6,7,8,9],[1,2,3,4,5,6,7,8,9],[1,2,3,4,5,6,7,8,9],[1,2,3,4,5,6,7,8,9],[1,2,3,4,5,6,7,8,9],[1,2,3,4,5,6,7,8,9],[1,2,3,4,5,6,7,8,9],[1,2,3,4,5,6,7,8,9]],
	[[1,2,3,4,5,6,7,8,9],[1,2,3,4,5,6,7,8,9],[1,2,3,4,5,6,7,8,9],[1,2,3,4,5,6,7,8,9],[1,2,3,4,5,6,7,8,9],[1,2,3,4,5,6,7,8,9],[1,2,3,4,5,6,7,8,9],[1,2,3,4,5,6,7,8,9],[1,2,3,4,5,6,7,8,9]],
	[[1,2,3,4,5,6,7,8,9],[1,2,3,4,5,6,7,8,9],[1,2,3,4,5,6,7,8,9],[1,2,3,4,5,6,7,8,9],[1,2,3,4,5,6,7,8,9],[1,2,3,4,5,6,7,8,9],[1,2,3,4,5,6,7,8,9],[1,2,3,4,5,6,7,8,9],[1,2,3,4,5,6,7,8,9]]
]).



% _ _ _ _ Manipulations de listes _ _ _ _ _ _ %

%retourne le ième elt d'une liste
i_elt([A|_], 1, A).
i_elt([_|B], P, Res) :- i_elt(B, Q, Res), P is Q+1.

%concatène deux listes
concat([],L2,L2).
concat([T|Q], L2, [T|R]) :- concat(Q,L2,R).

%renvoi la position d'un elt dans une liste
position([X|_], X, 1):- !.
position([_|Q], X, Res):- position(Q, X, Res2), Res is Res2+1.


%recupère l'indice de la sous-liste dans laquelle la liste est présente
getIndiceSousListe([T|_], X, 1):- member(X, T),!.
getIndiceSousListe([T|Q], X, Res):- T \= X, getIndiceSousListe(Q, X, I), Res is I+1,!.


%supprime le ième elt
supprime([], _, []).
supprime([_|Q], 1, Q).
supprime([T|Q], I, [T|Res]):- I2 is I-1, supprime(Q, I2, Res), !.


%applatit une liste
flatten([],[]).
flatten([[]|Q], R):- flatten(Q,R),!.
flatten([[T|Q]|Q2], R):- !, flatten([T|Q],R1), flatten(Q2, R2), concat(R1, R2, R).
flatten([X|Q], [X|R]):- flatten(Q,R).


%nombre d'occurances de X dans la liste
nombre(_,[],0).
nombre(X,[X|Q],Res) :- nombre(X,Q,Nb), Res is Nb+1,!.
nombre(X,[Y|Q],Res) :- X \= Y, nombre(X,Q,Res).


%nombre d'éléments dans une liste
nbElts([],0).
nbElts([_|T], X) :- nbElts(T, Y), X is Y + 1.



% -------------------
% Affichage du Sudoku
% -------------------

affichage([]) :- write('#####################################'), nl, nl.
affichage([L|R]) :- nbElts([L|R], X), Mod is X mod 3, Mod = 0,
		write('#####################################'), nl,
		write('#'), affichageLigne(L), nl, affichage(R).
affichage([L|R]) :- nbElts([L|R], X), Mod is X mod 3, Mod \= 0,
		write('#---+---+---#---+---+---#---+---+---#'), nl,
		write('#'), affichageLigne(L), nl, affichage(R).


convert(0,' ').
convert(A,A).

affichageLigne([]).
affichageLigne([L|R]) :- nbElts([L|R], X), Mod is X mod 3, Mod = 1,
		convert(L, A), write(' '), write(A), write(' '), write('#'),
		affichageLigne(R).
affichageLigne([L|R]) :- nbElts([L|R], X), Mod is X mod 3, Mod \= 1,
		convert(L, A), write(' '), write(A), write(' '), write('|'),
		affichageLigne(R).


% ------------------------------
% Concordance Région-Coordonnées
% ------------------------------

region(1, [[1,1],[1,2],[1,3],[2,1],[2,2],[2,3],[3,1],[3,2],[3,3]]).
region(2, [[1,4],[1,5],[1,6],[2,4],[2,5],[2,6],[3,4],[3,5],[3,6]]).
region(3, [[1,7],[1,8],[1,9],[2,7],[2,8],[2,9],[3,7],[3,8],[3,9]]).
region(4, [[4,1],[4,2],[4,3],[5,1],[5,2],[5,3],[6,1],[6,2],[6,3]]).
region(5, [[4,4],[4,5],[4,6],[5,4],[5,5],[5,6],[6,4],[6,5],[6,6]]).
region(6, [[4,7],[4,8],[4,9],[5,7],[5,8],[5,9],[6,7],[6,8],[6,9]]).
region(7, [[7,1],[7,2],[7,3],[8,1],[8,2],[8,3],[9,1],[9,2],[9,3]]).
region(8, [[7,4],[7,5],[7,6],[8,4],[8,5],[8,6],[9,4],[9,5],[9,6]]).
region(9, [[7,7],[7,8],[7,9],[8,7],[8,8],[8,9],[9,7],[9,8],[9,9]]).


getNumRegion(L, C, Res):- region(Res, List), member([L,C],List),!.

getRegion(L, C, List):- region(_, List), member([L,C],List),!.



% --------------------------------------
%             Extractions
% --------------------------------------

extraireLigne([A|_], 1, A).
extraireLigne([_|B], P, Res) :- extraireLigne(B, Q, Res), P is Q+1.

extraire3eltLigne([A,B,C|_], 1, [A,B,C]).
extraire3eltLigne([_|Q], Ind, Res):- extraire3eltLigne(Q, Ind2, Res), Ind is Ind2+1.

extraireColonne([],_,[]).
extraireColonne([A|B], I, Res) :- i_elt(A, I, Elt),
			extraireColonne(B, I, Res2), concat([Elt], Res2, Res).

extraireRegion(S, Reg, Res) :- Region is Reg-1, Region > -1, Region < 9,
		Ligne1 is (Region//3)*3+1, Colonne is (Region mod 3)*3+1,
		Ligne2 is Ligne1+1, Ligne3 is Ligne1+2,
		extraireLigne(S, Ligne1, L1), extraireLigne(S, Ligne2, L2), extraireLigne(S, Ligne3, L3),
		extraire3eltLigne(L1, Colonne, SL1),
		extraire3eltLigne(L2, Colonne, SL2),
		extraire3eltLigne(L3, Colonne, SL3),
		concat(SL1, SL2, SL12), concat(SL12, SL3, Res), !.

extraireElt(S, L, C, Res) :- extraireLigne(S, L, Ligne), i_elt(Ligne, C, Res).



% -------------------------------
% Vérifie l'intégrité d'une ligne
% -------------------------------

verifieLigne([], 1).
verifieLigne([T|Q], Res3) :- T \= 0, nombre(T, Q, Res2), Res2 =:= 0,
	verifieLigne(Q, Res3),!.
verifieLigne([T|Q], 0) :- T \= 0, nombre(T, Q, Res2), Res2 \= 0, !.
verifieLigne([T|Q], Res3) :- T =:= 0, verifieLigne(Q, Res3).


% -------------------------------------
% Vérification de l'intégrité du Sudoku
% -------------------------------------

verifieSudoku(S, Res) :- verifieSudo(S, 9, Res).

verifieSudo(_, 0, 1).

verifieSudo(S, Ind, 0) :- extraireLigne(S, Ind, Res2), verifieLigne(Res2, Res3),
		Res3 = 0, write('erreur lig'),nl,!.

verifieSudo(S, Ind, 0) :- extraireColonne(S, Ind, Res2), verifieLigne(Res2, Res3),
		Res3 = 0, write('erreur col'),nl,!.

verifieSudo(S, Ind, 0) :- extraireRegion(S, Ind, Res2), verifieLigne(Res2, Res3),
		Res3 = 0, write('erreur reg'),nl,!.

verifieSudo(S, Ind, Res) :- Ind2 is Ind-1, verifieSudo(S, Ind2, Res),!.


% Vérifie que le sudoku sera bien complétément résolvable

verifieToutSudoku([], []).
verifieToutSudoku([TS|QS], [TC|QC]) :- flatten(TC, []), \+ member(0,TS),
	verifieToutSudoku(QS, QC).
verifieToutSudoku([_|QS], [TC|QC]) :- \+ flatten(TC, []), verifieToutSudoku(QS, QC).


% ------------------------------------------------
% Supprime X de la liste candidate de coord(C,L)
% ------------------------------------------------

supprimerEltListe([], _, _, []). 
supprimerEltListe([T|Q], 1, X, [Res|Q]) :- !, delete(T, X, Res),!.
supprimerEltListe([T|Q], I, X, [T|Res]) :- I2 is I-1, supprimerEltListe(Q, I2, X, Res).

supprimerEltGrille([], _, _, _, []).
supprimerEltGrille([T|Q], 1, C, X, [Ligne2|Q]):- !,
			supprimerEltListe(T, C, X, Ligne2).
supprimerEltGrille([T|Q], L, C, X, [T|Ligne]):- L2 is L-1,
			supprimerEltGrille(Q, L2, C, X, Ligne).


% ------------------------------------------------------------------
% Supprime X de la liste candidate de coord(C,L) : balaye les lignes
% ------------------------------------------------------------------

supprimerTousEltGrille(LCand, _, _, X, LCand):- X > 9,!.
supprimerTousEltGrille(LCand, L, C, X, NewCand):- X < 10, supprimerEltGrille(LCand, L, C, X, LCand2),!,
			X2 is X+1, supprimerTousEltGrille(LCand2, L, C, X2, NewCand).

supprimerTousEltCandidats(LCand, L, C, NewCand) :- supprimerTousEltGrille(LCand, L, C, 1, NewCand).


% ---------------------------------------------------------------------
% Supprime X de la liste candidate pour ses régions, lignes et colonnes
% ---------------------------------------------------------------------

% supprimerEltLigneCol(Cand, L, C, I, X, ListReg, Res)
supprimerEltLigneCol([], _, _, _, _, _, []).
supprimerEltLigneCol(Cand, _, _, 0, _, _, Cand).
supprimerEltLigneCol(Cand, L, C, I, X, [[L2,C2]|QReg], Res):- I > 0,
			supprimerEltGrille(Cand, L, I, X, Res1),
			supprimerEltGrille(Res1, I, C, X, Res2),
			supprimerEltGrille(Res2, L2, C2, X, Res3),!,
			Ind2 is I-1, supprimerEltLigneCol(Res3, L, C, Ind2, X, QReg, Res).


% --------------------------------
% Mise à jour d'une case du Sudoku
% --------------------------------

modifierEltListe([], _, _, []).
modifierEltListe([_|Q], 1, NewValeur, [NewValeur|Q]):-!.
modifierEltListe([T|Q], Index, NewValeur, [T|LRes]):- Index2 is Index-1,
			modifierEltListe(Q, Index2, NewValeur, LRes).

modifierEltSudoku([], _, _, _, []).
modifierEltSudoku([T|Q], 1, C, NewValeur, [Res2|Q]):- !,
			modifierEltListe(T, C, NewValeur, Res2),!.
modifierEltSudoku([T|Q], L, C, NewValeur, [T|Res]):- L2 is L-1,
			modifierEltSudoku(Q, L2, C, NewValeur, Res).


% -------------------------------
% Jouer X en (C,L) dans le Sudoku
% -------------------------------

jouer(S, LCand, L, C, X, NewS, NewCand) :- extraireElt(S, L, C, Res), Res =:= 0,
			modifierEltSudoku(S, L, C, X, NewS), getRegion(L,C,EltsReg),
			supprimerEltLigneCol(LCand, L, C, 9, X, EltsReg, LCand2),
			supprimerTousEltCandidats(LCand2, L, C, NewCand).
			
			


% _ _ _ _ Mise à jour de la liste candidate _ _ _ _ _ _ %


majLigneListeCand([], LCand, _, _, LCand).
majLigneListeCand([T|Q], LCand, L, C, NewCand):- T > 0,
			getRegion(L,C,EltsReg),
			supprimerEltLigneCol(LCand, L, C, 9, T, EltsReg, Cand2), !,
			supprimerTousEltCandidats(Cand2, L, C, Cand3),!,
			C2 is C+1, majLigneListeCand(Q, Cand3, L, C2, NewCand).
majLigneListeCand([T|Q], LCand, L, C, NewCand):- T =:= 0,
			C2 is C+1, majLigneListeCand(Q, LCand, L, C2, NewCand).


majListeCand([], LCand, _, LCand).
majListeCand([T|Q], LCand, L, NewCand):- majLigneListeCand(T, LCand, L, 1, Cand2), !, 
			L2 is L+1, majListeCand(Q, Cand2, L2, NewCand).



% --------------------------------------------
% Lance les stratégies de résolution du Sudoku
% --------------------------------------------

%affichage de la résolution du Sudoku coup / coup
%rechercherCoup(S, LCand, _, _) :- affichage(S), write(LCand), nl, nl, fail.

rechercherCoup(S, LCand, S, LCand) :- flatten(S, S2), \+ member(0, S2),!. 

rechercherCoup(S, LCand, NewS2, NewCand2) :- rechercheCandidatUnique(LCand, 1, L, C, X), 
			jouer(S, LCand, L, C, X, NewS, NewCand),
			rechercherCoup(NewS, NewCand, NewS2, NewCand2).

rechercherCoup(S, LCand, NewS2, NewCand2) :- croise_balayeL(LCand, 1, L, C, X),
			jouer(S, LCand, L, C, X, NewS, NewCand),
			rechercherCoup(NewS, NewCand, NewS2, NewCand2).

rechercherCoup(S, LCand, NewS2, NewCand2) :- croise_balayeC(LCand, 1, C, L, X),
			jouer(S, LCand, L, C, X, NewS, NewCand),
			rechercherCoup(NewS, NewCand, NewS2, NewCand2).

rechercherCoup(S, LCand, NewS2, NewCand2) :- croise_balayeR(LCand, 1, L, C, X),
			jouer(S, LCand, L, C, X, NewS, NewCand),
			rechercherCoup(NewS, NewCand, NewS2, NewCand2).

rechercherCoup(S, LCand, NewS, NewCand):- 
			empirique(S, LCand, NewS, NewCand).



% ---------------------------
% Stratégie : candidat unique
% ---------------------------

rechercheListeCandidatUnique(Liste, L, L, C, X):- position(Liste, [X], C).

rechercheCandidatUnique([T|_], L, ResL, ResC, ResX):- rechercheListeCandidatUnique(T, L, ResL, ResC, ResX), !.
rechercheCandidatUnique([T|Q], L, ResL, ResC, ResX):- L<10, \+ rechercheListeCandidatUnique(T, L, _, _, _),!, 
			L2 is L+1, rechercheCandidatUnique(Q, L2, ResL, ResC, ResX).



% -------------------------
% Stratégie : Flatten Ligne
% -------------------------

eltUniqueLigne(Ligne, X, X) :- X < 10, nombre(X, Ligne, 1),!.
eltUniqueLigne(Ligne, X, Res) :- X < 10, X2 is X + 1, eltUniqueLigne(Ligne, X2, Res), !.


croise_balayeLigne(LCand, L, C, X):- extraireLigne(LCand, L, Ligne), flatten(Ligne, L2),
		eltUniqueLigne(L2, 1, X), !, getIndiceSousListe(Ligne, X, C).

croise_balayeColonne(LCand, L, C, X):- extraireColonne(LCand, C, Ligne), flatten(Ligne, L2),
		eltUniqueLigne(L2, 1, X), !, getIndiceSousListe(Ligne, X, L).

croise_balayeRegion(LCand, Reg, L, C, X):- extraireRegion(LCand, Reg, Ligne), flatten(Ligne, Ligne2),
		eltUniqueLigne(Ligne2, 1, X), !, getIndiceSousListe(Ligne, X, Res),
		region(Reg, [[L2,C2]|_]), Res2 is Res-1, R is (Res2 mod 3), S is (Res2//3),
		L is L2 + S, C is C2 + R.


croise_balayeL(LCand, L, L, C, X):- L < 10, croise_balayeLigne(LCand, L, C, X),!.
croise_balayeL(LCand, L, Res, C, X):- L < 10, L2 is L+1, croise_balayeL(LCand, L2, Res, C, X).

croise_balayeC(LCand, C, C, L, X):- C < 10, croise_balayeColonne(LCand, L, C, X),!.
croise_balayeC(LCand, C, Res, L, X):- C < 10, C2 is C+1, croise_balayeC(LCand, C2, Res, L, X).

croise_balayeR(LCand, Reg, L, C, X):- Reg < 10, croise_balayeRegion(LCand, Reg, L, C, X),!.
croise_balayeR(LCand, Reg, L, C, X):- Reg < 10, R2 is Reg+1, croise_balayeR(LCand, R2, L, C, X).


% ---------------------
% Stratégie : empirique
% ---------------------

premierEltCandidat(S, Cand, L, C, Coups) :-
		verifieToutSudoku(S, Cand),
		i_elt(S, L, LS), i_elt(Cand, L, LC),
		i_elt(LS, C, 0),!, \+ i_elt(LC, C, []), i_elt(LC, C, Coups).

empirique(S, Cand, S, Cand):- flatten(S, S2), \+ member(0, S2),!.

empirique(S, Cand, ResS, ResC):- verifieToutSudoku(S, Cand),
		premierEltCandidat(S, Cand, L, C, Coups),
		member(X, Coups),
		jouer(S, Cand, L, C, X, S2, Cand2), verifieSudoku(S2, 1),
		empirique(S2, Cand2, ResS, ResC).



% _ _ _ _ Jeux de Tests _ _ _ _ _ _ %


% extraire une région
  test1 :- sudoku(X), extraireRegion(X, 9, R), write(R),!.

% extraire 3 elts consécutifs
  test2 :- extraire3eltLigne([1,5,9,2,3,4,6,7,8], 5, Res), write(Res), !.

% vérifier l'intégrité d'une ligne
  test3 :- verifieLigne([1,5,9,2,6,3,4,7,8],Res), write(Res),!.

% vérifier l'intégrité du Sudoku
  test4 :- sudoku(X), verifieSudoku(X, Res), nl, write(Res),!.

% vérifier l'intégrité des régions
  test5 :- sudoku(X), extraireRegion(X, 1, Reg), verifieLigne(Reg, Res), write(Res),!.

% modifie un elt d'une liste
  test6 :- modifierEltListe([1,2,3,4,5,6,7,8,9], 5, 0, Res),write(Res).

% supprime un elt d'une liste
  test7 :- supprimerElt([1,2,3,4,5,6,7,8,9], 5, Res),write(Res).

% modifie une case du Sudoku
  test8 :- sudoku(X), !, modifierEltSudoku(X, 5, 4, 9, Res), !, affichage(Res), !.

% modifie un elt de la liste candidate
  test9 :- listeCandidate(X), getRegion(7,3,EltsReg), supprimerEltLigneCol(X, 7, 3 , 9, 5, EltsReg, Res), !, write(Res), nl.

% extraire une région
  test10 :- getRegion(5,1,Res), write(Res), nl.

% jouer un coup
  test11 :- sudoku(S), listeCandidate(LCand), jouer(S, LCand, 8, 3, 5, NewS, NewCand), affichage(NewS), nl, write(NewCand), nl, !.

% MaJ de la liste candidate à partir d'un sudoku contenat déja des données
  test12 :- sudoku(S), listeCandidate(LCand), majListeCand(S, LCand, 1, NewCand), write(NewCand), nl, !.

% Résolution d'un Sudoku moyen
  test13 :- sudoku_moyen(S), listeCandidate(LCand), majListeCand(S, LCand, 1, NewCand), rechercherCoup(S, NewCand, S2, _), affichage(S2),!, nl.

% Résolution d'un Sudoku moyen
  test14 :- sudoku_diabolique(S), listeCandidate(LCand), majListeCand(S, LCand, 1, NewCand), rechercherCoup(S, NewCand, S2, _), affichage(S2),!, nl.