/* librairie à intégrer */

:-use_module(library(assoc)).


/*  successeurs_liste(L,Sl) est vrai si Sl est la liste 
    de tous les successeurs de L*/
successeurs_liste(L,Sl):-
    maplist(successeurs,L,Lp),
    flatten(Lp,Lpp),
    list_to_assoc(Lpp,A),
    assoc_to_list(A,Sl).

    
/*  list_minus(L1,L2,L3) est vrai si 
    L3 est la liste de tous les éléments Conf-_ de L1 dont 
    Conf n appartient pas à L2 */ 
list_minus([],_,[]).
list_minus([Conf-_|L1],L2,Res):-
    member(Conf,L2),!,
    list_minus(L1,L2,Res).
list_minus([El|L1],L2,[El|Res]):-
    list_minus(L1,L2,Res).

filtre_conf(X-_,X).

/* but(L,Ch) est vrai si L contient une configuration
    finale et si Ch est le chemin qui a mené a cette configuration */
but([Conf-Chemin|_],Chemin):-final(Conf),!.
but([_|L],Chemin):-but(L,Chemin).



/* largeur(Atraiter,Visites,C,Res) est vrai si
    Atraiter est la liste des configurations-chemins qu il reste à visiter
    Visites est la liste des configurations déjà visités
    C est l entier représentant la profondeur de recherche
    Res est le chemin menant à une configuration finale */
largeur(Atraiter,_,_,Res):-
    but(Atraiter,Res),!.
largeur(Atraiter,Visites,C,Res):-
    Cp is C+1,
    writef("boucle %d \n",[C]),
    maplist(filtre_conf,Atraiter,V1),
    append(V1,Visites,Omis),
    successeurs_liste(Atraiter,Succ),
    list_minus(Succ,Omis,Atraiter2),
    largeur(Atraiter2,Omis,Cp,Res).


    
resoud(_):-
    get_time(T0),
    init(X),
    largeur([X-[]],[],0,Res),
    writeln(Res),
    get_time(T1),
    DT1 is T1 - T0,
    writef('Duree : % \n',[DT1]).


