% ==============================================================================
% Solution pour les grilles de roulement de TP en utilisant la coupure
% www.gecif.net
% Juin 2026
% ==============================================================================

% ==============================================================================
% CONFIGURATION DYNAMIQUE
% ==============================================================================
nb_eleves(18).
nb_seances(6).

% Calcul automatique du nombre de TP
nb_tp(NB_TP) :- nb_eleves(E), NB_TP is E // 3.

% Génération de la liste des élèves (ex: [e1, e2, ..., e18])
generer_eleves(Eleves) :-
    nb_eleves(E),
    numlist(1, E, Ids),
    maplist(transformer_eleve, Ids, Eleves).

transformer_eleve(Id, E) :- 
    atom_concat(e, Id, E).

% ==============================================================================
% PREDICATS DE VERIFICATION DES CONTRAINTES
% ==============================================================================

% Un trio est une combinaison de 3 élèves distincts et triés (pour éviter les doublons)
trio_valide(Eleves, (X,Y,Z)) :-
    member(X, Eleves), member(Y, Eleves), member(Z, Eleves),
    X @< Y, Y @< Z.

% Vérifie qu'aucun élève d'un trio n'est présent dans une liste de cases déjà jouées
intersection_vide((X,Y,Z), CasesJouees) :-
    \+ ( member((A,B,C), CasesJouees),
         (X = A; X = B; X = C; Y = A; Y = B; Y = C; Z = A; Z = B; Z = C) ).

% Contrainte cruciale de brassage : aucun duo ne doit s'être déjà rencontré
duos_uniques((X,Y,Z), CasesJouees) :-
    \+ ( member((A,B,C), CasesJouees),
         ( (X = A, Y = B); (X = A, Y = C); (X = B, Y = C);
           (X = A, Z = B); (X = A, Z = C); (X = B, Z = C);
           (Y = A, Z = B); (Y = A, Z = C); (Y = B, Z = C) ) ).

% ==============================================================================
% RESOLUTION PAR BACKTRACKING AVEC COUPURE
% ==============================================================================

% Point d'entrée principal
generer_roulement :-
    generer_eleves(Eleves),
    findall(T, trio_valide(Eleves, T), TousLesTrios),
    nb_tp(NB_TP), nb_seances(NB_SEANCES),
    
    % Initialisation de la grille vide (liste de listes)
    length(Grille, NB_TP),
    maplist(creer_ligne(NB_SEANCES), Grille),
    
    % Lancement de la résolution
    remplir_grille(Grille, TousLesTrios, []),
    
    % Affichage du résultat
    afficher_grille(Grille),
    !. % <--- LA COUPURE : Empêche Prolog de chercher d'autres grilles si on demande ";"

creer_ligne(Lg, Ligne) :- length(Ligne, Lg).

% Remplissage de la grille case par case
remplir_grille([], _, _).
remplir_grille([Ligne|RestLignes], TousLesTrios, Historique) :-
    remplir_ligne(Ligne, TousLesTrios, Historique, NouvelHistorique),
    remplir_grille(RestLignes, TousLesTrios, NouvelHistorique).

remplir_ligne([], _, Historique, Historique).
remplir_ligne([Case|RestCases], TousLesTrios, Historique, FinalHistorique) :-
    member(Case, TousLesTrios),
    
    % Application des contraintes en fonction de l'historique des choix passés
    intersection_vide(Case, Historique),
    duos_uniques(Case, Historique),
    
    % Si c'est bon, on avance récursivement
    remplir_ligne(RestCases, TousLesTrios, [Case|Historique], FinalHistorique).

% ==============================================================================
% AFFICHAGE DES RÉSULTATS
% ==============================================================================
afficher_grille(Grille) :-
    nl, writeln('--- TABLEAU DE ROULEMENT PROLOG ---'),
    afficher_lignes(Grille, 1).

afficher_lignes([], _).
afficher_lignes([Ligne|Reste], NumTP) :-
    format('TP ~w : ', [NumTP]),
    afficher_cases(Ligne),
    nl,
    NumLigneSuivante is NumTP + 1,
    afficher_lignes(Reste, NumLigneSuivante).

afficher_cases([]).
afficher_cases([(X,Y,Z)|Reste]) :-
    format('[~w,~w,~w]   ', [X, Y, Z]),
    afficher_cases(Reste).