/* accesseurs sur ligne et colonne*/ colonne(1,[A,_,_,_],A). colonne(2,[_,A,_,_],A). colonne(3,[_,_,A,_],A). colonne(4,[_,_,_,A],A). ligne(1,[A,_,_,_,_],A). ligne(2,[_,A,_,_,_],A). ligne(3,[_,_,A,_,_],A). ligne(4,[_,_,_,A,_],A). ligne(5,[_,_,_,_,A],A). /* retourne le contenu "Contenu_case" de la case situé à la colonne "Col" et la ligne "Lig" du jeux en cours "Contenu_jeu" */ case(Lig,Col,Conf,Contenu) :- ligne(Lig,Conf,Ligne), colonne(Col,Ligne,Contenu). changeContenuColonne(1,X,[_,B,C,D],[X,B,C,D]). changeContenuColonne(2,X,[A,_,C,D],[A,X,C,D]). changeContenuColonne(3,X,[A,B,_,D],[A,B,X,D]). changeContenuColonne(4,X,[A,B,C,_],[A,B,C,X]). changeContenuLigne(1,X,[_,B,C,D,E],[X,B,C,D,E]). changeContenuLigne(2,X,[A,_,C,D,E],[A,X,C,D,E]). changeContenuLigne(3,X,[A,B,_,D,E],[A,B,X,D,E]). changeContenuLigne(4,X,[A,B,C,_,E],[A,B,C,X,E]). changeContenuLigne(5,X,[A,B,C,D,_],[A,B,C,D,X]). changeContenu(Conf1,Piece,Y,X,Conf2):- ligne(Y,Conf1,Ligne), changeContenuColonne(X,Piece,Ligne,Lignep), changeContenuLigne(Y,Lignep,Conf1,Conf2). init([ [j1,r1,ro,j1], [ja,ro,ro,ja], [ma,b1,bl,ma], [bo,n1,n1,bo], [vi,no,no,vi]]). /* final([ [_,_,_,_], [_,_,_,_], [_,_,_,_], [_,_,_,_], [_,b1,bl,_]]). */ final([ [_,_,_,_], [_,_,_,_], [_,_,_,_], [_,j1,_,_], [_,ja,_,_]]). /* final([ [j1,r1,ro,j1], [ja,ro,ro,ja], [n1,bo,b1,bl], [no,ma,vi,n1], [ma,vi,bo,no]]). */ /* direction */ directionh(d,1). directionh(g,-1). directionv(h,-1). directionv(b,1). /*glissement rouge*/ /* vers la droite */ glissement(r1,d,Conf1,Conf2):- case(Lig,Col,Conf1,r1), Ligp is Lig+1, Colp is Col+1, Colpp is Col+2, case(Lig,Colpp,Conf1,vi), case(Ligp,Colpp,Conf1,vi), changeContenu(Conf1,r1,Lig,Colp,Conf1a), changeContenu(Conf1a,ro,Lig,Colpp,Conf1b), changeContenu(Conf1b,vi,Lig,Col,Conf1c), changeContenu(Conf1c,ro,Ligp,Colpp,Conf1d), changeContenu(Conf1d,vi,Ligp,Col,Conf2). /*vers la gauche */ glissement(r1,g,Conf1,Conf2):- case(Lig,Col,Conf1,r1), Ligp is Lig+1, Colm is Col-1, Colp is Col+1, case(Lig,Colm,Conf1,vi), case(Ligp,Colm,Conf1,vi), changeContenu(Conf1,r1,Lig,Colm,Conf1a), changeContenu(Conf1a,ro,Lig,Col,Conf1b), changeContenu(Conf1b,vi,Lig,Colp,Conf1c), changeContenu(Conf1c,ro,Ligp,Colm,Conf1d), changeContenu(Conf1d,vi,Ligp,Colp,Conf2). /* vers le bas */ glissement(r1,b,Conf1,Conf2):- case(Lig,Col,Conf1,r1), Ligp is Lig+1, Colp is Col+1, Ligpp is Lig+2, case(Ligpp,Col,Conf1,vi), case(Ligpp,Colp,Conf1,vi), changeContenu(Conf1,r1,Ligp,Col,Conf1b), changeContenu(Conf1b,vi,Lig,Col,Conf1c), changeContenu(Conf1c,ro,Ligpp,Col,Conf1d), changeContenu(Conf1d,ro,Ligpp,Colp,Conf1e), changeContenu(Conf1e,vi,Lig,Colp,Conf2). /* vers le haut */ glissement(r1,h,Conf1,Conf2):- case(Lig,Col,Conf1,r1), Ligp is Lig+1, Colp is Col+1, Ligm is Lig-1, case(Ligm,Col,Conf1,vi), case(Ligm,Colp,Conf1,vi), changeContenu(Conf1,r1,Ligm,Col,Conf1a), changeContenu(Conf1a,ro,Ligm,Colp,Conf1b), changeContenu(Conf1b,vi,Ligp,Col,Conf1c), changeContenu(Conf1c,ro,Lig,Col,Conf1d), changeContenu(Conf1d,vi,Ligp,Colp,Conf2). /* glissement noire , jaune droite ou gauche */ glissement(Pc1,D,Conf1,Conf2):- case(Lig,Col,Conf1,Pc1), ((Pc1= n1, Pc2= no); (Pc1= j1, Pc2= ja)), directionh(D,Delta), Ligp is Lig+1, Colp is Col+Delta, case(Lig,Colp,Conf1,vi), case(Ligp,Colp,Conf1,vi), changeContenu(Conf1,Pc1,Lig,Colp,Conf1a), changeContenu(Conf1a,Pc2,Ligp,Colp,Conf1b), changeContenu(Conf1b,vi,Lig,Col,Conf1c), changeContenu(Conf1c,vi,Ligp,Col,Conf2). /* vers le bas */ glissement(Pc1,b,Conf1,Conf2):- case(Lig,Col,Conf1,Pc1), ((Pc1= n1, Pc2= no); (Pc1= j1, Pc2= ja)), Ligp is Lig+1, Ligpp is Lig+2, case(Ligpp,Col,Conf1,vi), changeContenu(Conf1,Pc1,Ligp,Col,Conf1a), changeContenu(Conf1a,Pc2,Ligpp,Col,Conf1b), changeContenu(Conf1b,vi,Lig,Col,Conf2). /* vers le haut */ glissement(Pc1,h,Conf1,Conf2):- case(Lig,Col,Conf1,Pc1), ((Pc1= n1, Pc2= no); (Pc1= j1, Pc2= ja)), Ligp is Lig+1, Ligm is Lig-1, case(Ligm,Col,Conf1,vi), changeContenu(Conf1,Pc1,Ligm,Col,Conf1a), changeContenu(Conf1a,Pc2,Lig,Col,Conf1b), changeContenu(Conf1b,vi,Ligp,Col,Conf2). /* blanc, à droite */ glissement(b1,d,Conf1,Conf2):- case(Lig,Col,Conf1,b1), Colpp is Col+2, Colp is Col+1, case(Lig,Colpp,Conf1,vi), changeContenu(Conf1,b1,Lig,Colp,Conf1a), changeContenu(Conf1a,bl,Lig,Colpp,Conf1b), changeContenu(Conf1b,vi,Lig,Col,Conf2). /* blanc, à gauche */ glissement(b1,g,Conf1,Conf2):- case(Lig,Col,Conf1,b1), Colm is Col-1, Colp is Col+1, case(Lig,Colm,Conf1,vi), changeContenu(Conf1,b1,Lig,Colm,Conf1a), changeContenu(Conf1a,bl,Lig,Col,Conf1b), changeContenu(Conf1b,vi,Lig,Colp,Conf2). /* blanc, haut ou bas */ glissement(b1,D,Conf1,Conf2):- case(Lig,Col,Conf1,b1), directionv(D,Delta), Ligp is Lig+Delta, Colp is Col+1, case(Ligp,Col,Conf1,vi), case(Ligp,Colp,Conf1,vi), changeContenu(Conf1,b1,Ligp,Col,Conf1a), changeContenu(Conf1a,bl,Ligp,Colp,Conf1b), changeContenu(Conf1b,vi,Lig,Col,Conf1c), changeContenu(Conf1c,vi,Lig,Colp,Conf2). /* bois ou marron, gauche ou droite*/ glissement(PC,D,Conf1,Conf2):- case(Lig,Col,Conf1,PC), (PC = ma; PC = bo), directionh(D,Delta), Colp is Col+Delta, case(Lig,Colp,Conf1,vi), changeContenu(Conf1,PC,Lig,Colp,Conf1a), changeContenu(Conf1a,vi,Lig,Col,Conf2). /* bois ou marron, haut ou bas*/ glissement(PC,D,Conf1,Conf2):- case(Lig,Col,Conf1,PC), (PC = ma; PC = bo), directionv(D,Delta), Ligp is Lig+Delta, case(Ligp,Col,Conf1,vi), changeContenu(Conf1,PC,Ligp,Col,Conf1a), changeContenu(Conf1a,vi,Lig,Col,Conf2). /* ajoute la nouvelle paire (Conf, deplacements) à la fin en s assurant que la conf n a pas encore été visitéé */ /*insert_fin((X,Y),[],[(X,Y)]). insert_fin((X,_),[(X,K)|R1],[(X,K)|R1]):-!. insert_fin(X,[T|R1],[T|R2]):- insert_fin(X,R1,R2). insert_fin_liste([],L,L). insert_fin_liste([X|R],L,Res):- insert_fin_liste(R,L,Resp), insert_fin(X,Resp,Res). */ fusion_confs([],L2,L2). fusion_confs(L1,[],L1). fusion_confs(L1,L2,Res):- list_to_assoc(L1,A), ajoute_liste_assoc(L2,A,B), assoc_to_list(B,Res). ajoute_liste_assoc([],A,A). ajoute_liste_assoc([K-V|L],A,B):- ajoute_liste_assoc(L,A,Ap), put_assoc(K,Ap,V,B). /* Tous les successeurs d une configuration */ successeurs((Confa,Chemins),L):- findall( (Confb,[(P,D)|Chemins]), glissement(P,D,Confa,Confb), L). successeurs_liste([],[]). successeurs_liste([Ca|Cs],ConfsSucc):- successeurs(Ca,L), successeurs_liste(Cs,ConfsSuccInter), fusion_confs(L,ConfsSuccInter,ConfsSucc). /*insert_fin_liste(L,ConfsSuccInter,ConfsSucc).*/ /* successeurs_liste([Ca|Cs],ConfsSucc):- successeurs(Ca,L), successeurs_liste(Cs,ConfsSuccInter), append(L,ConfsSuccInter,ConfsSucc). */ /* regarde si le premier parametre appartient à la liste donné en second parametre. Si c est le cas, retourne le chemin */ appartient((Conf1,_),[(Conf1,_)|_]):-!. appartient((Conf1,C),[_|L]):- appartient((Conf1,C),L). difference([],_,[]). difference([El|L1],L2,Res):- appartient(El,L2), !, difference(L1,L2,Res). difference([El|L1],L2,[El|Res]):- difference(L1,L2,Res). but([(Conf,Chemin)|_],Chemin):-final(Conf). but([_|L],Chemin):-but(L,Chemin). largeur(Atraiter,_,_,Res):- get_time(T0), but(Atraiter,Res), get_time(T1), DT is T1 - T0, write('but : '),writeln(DT), !. largeur(Atraiter,Visites,C,Res):- Cp is C+1, write('boucle'), writeln(C), get_time(T0), successeurs_liste(Atraiter,Succ), get_time(T1), DT1 is T1 - T0, write('successeur : '),writeln(DT1), get_time(T2), difference(Succ,Visites,Atraiter2), get_time(T3), DT3 is T3 - T2, write('difference : '),writeln(DT3), get_time(T4), insert_fin_liste(Atraiter,Visites,Visites2), get_time(T5), DT5 is T5 - T4, write('Visites2 : '),writeln(DT5), largeur(Atraiter2,Visites2,Cp,Res). resoud(Res):- init(X), largeur([(X,[])],[],0,Res). /* display_ligne([]). display_ligne([El|R]):- write(El), display_ligne(R). display_conf([]). display_conf([L|R]):- display_ligne(L), writeln(''), display_conf(R). display_chemin(L):- write(L). display_conf_chemin((Conf,Chemin)):- display_conf(Conf),display_chemin(Chemin). display_conf_chemin_liste([]). display_conf_chemin_liste([CL|R]):- display_conf_chemin(CL), writeln(''), display_conf_chemin_liste(R). */