TP_IA/tp1/taquin.pl

/*
Doit contenir au moins 4 predicats qui seront utilises par A*
   etat_initial(I)                                         % definit l'etat initial
   etat_final(F)                                           % definit l'etat final  
   rule(Rule_Name, Rule_Cost, Before_State, After_State)   % règles applicables
   heuristique(Current_State, Hval)				           % calcul de l'heuristique 
*/

%********************
% ETAT INITIAL DU JEU
%********************   
% format :  initial_state(+State) ou State est une matrice (liste de listes)
   
/*
initial_state([ [b, h, c],       % C'EST L'EXEMPLE PRIS EN COURS
                [a, f, d],       % 
                [g,vide,e] ]).   % h1=4,   h2=5,   f*=5*/

/*

initial_state([ [ a, b, c],        
                [ g, h, d],
                [vide,f, e] ]). % h2=2, f*=2

initial_state([ [b, c, d],
                [a,vide,g],
                [f, h, e]  ]). % h2=10 f*=10
			
initial_state([ [f, g, a],
                [h,vide,b],
                [d, c, e]  ]). % h2=16, f*=20
initial_state([ [e, f, g],
                [d,vide,h],
                [c, b, a]  ]). % h2=24, f*=30 
*/
/*
initial_state([ [a, b, c],
                [g,vide,d],
                [h, f, e]]). % etat non connexe avec l'etat final (PAS DE SOLUTION)
  
*/
initial_state([[ d , l , n , g ],
               [ vide , b , a , c ],
               [ e , m , k , h ],
               [ j , f , i , o]]).

%******************
% ETAT FINAL DU JEU
%******************
% format :  final_state(+State) ou State est une matrice (liste de listes)

/*
final_state([ [a, b,  c],
			  [h,vide,d],
              [g, f,  e]]). % etat non connexe avec l'etat final (PAS DE SOLUTION)
*/
final_state([[ a , b , c , d ],
             [ e , f , g , h ],
             [ i , j , k , l ],
             [ m , n , o , vide]]).

%********************
% AFFICHAGE D'UN ETAT
%********************
% format : write_state(?State) ou State est une liste de lignes a afficher
write_state([]).
write_state([Line|Rest]) :-
   print(Line),
   nl,
   write_state(Rest).

%**********************************************
% REGLES DE DEPLACEMENT (up, down, left, right)             
%**********************************************
% format : rule(+Rule_Name, ?Rule_Cost, +Current_State, ?Next_State)
rule(down , 1, S1, S2) :-
   vertical_permutation(_X,vide,S1,S2).

rule(up   , 1, S1, S2) :-
   vertical_permutation(vide,_X,S1,S2).

rule(right, 1, S1, S2) :-
   horizontal_permutation(_X,vide,S1,S2).

rule(left , 1, S1, S2) :-
   horizontal_permutation(vide,_X,S1,S2).

%***********************
% Deplacement horizontal            
%***********************
% format : horizontal_permutation(?Piece1,?Piece2,+Current_State, ?Next_State)
horizontal_permutation(X,Y,S1,S2) :-
   append(Above,[Line1|Rest], S1),
   exchange(X,Y,Line1,Line2),
   append(Above,[Line2|Rest], S2).

%***********************************************
% Echange de 2 objets consecutifs dans une liste             
%***********************************************
exchange(X,Y,[X,Y|List], [Y,X|List]).
exchange(X,Y,[Z|List1],  [Z|List2] ):-
   exchange(X,Y,List1,List2).

%*********************
% Deplacement vertical            
%*********************
vertical_permutation(X,Y,S1,S2) :-
   append(Above, [Line1,Line2|Below], S1), % decompose S1
   delete(N,X,Line1,Rest1),    % enleve X en position N a Line1,   donne Rest1
   delete(N,Y,Line2,Rest2),    % enleve Y en position N a Line2,   donne Rest2
   delete(N,Y,Line3,Rest1),    % insere Y en position N dans Rest1 donne Line3
   delete(N,X,Line4,Rest2),    % insere X en position N dans Rest2 donne Line4
   append(Above, [Line3,Line4|Below], S2). % recompose S2 

%***********************************************************************
% Retrait d'une occurrence X en position N dans une liste L (resultat R) 
%***********************************************************************
% use case 1 :   delete(?N,?X,+L,?R)
% use case 2 :   delete(?N,?X,?L,+R)   
delete(1,X,[X|L], L).
delete(N,X,[Y|L], [Y|R]) :-
   delete(N1,X,L,R),
   N is N1 + 1.

%*******************************************************************
% Coordonnees X(colonne),Y(Ligne) d'une piece P dans une situation U
%*******************************************************************
% Associe un état State et une pièce P à ses coordonnées X et Y
coordonnees(State, P, X, Y) :-
        nth1(Y, State, Ligne),
        nth1(X, Ligne, P).
										 
%*************
% HEURISTIQUES
%*************
heuristique(U,H) :-
   heuristique2(U, H). 
   
%****************
%HEURISTIQUE 1
%****************
% Nombre de pieces mal placees dans l'etat courant U
% par rapport a l'etat final F
heuristique1(U, H) :- 
    final_state(F),
    findall([X, Y], meme_piece(U, F, X, Y), BienPlacees),
    length(BienPlacees, NbBienPlacees),
    length(U, N),
    H is N*N - NbBienPlacees.	% On considère que les taquins seront toujours carré

% Détermine si la pièce aux coord X,Y en S1 est la même que celle en S2
meme_piece(S1, S2, X, Y) :-
    coordonnees(S1, P, X, Y),
    coordonnees(S2, P, X, Y),
    P \= vide,
    !.

% Cas particulier : on ne compte pas 'vide'
meme_piece(S1, _, X, Y) :-
    coordonnees(S1, vide, X, Y).

%****************
%HEURISTIQUE no 2
%****************
% Somme des distances de Manhattan à parcourir par chaque piece
% entre sa position courante et sa positon dans l'etat final
heuristique2(U, H) :- 
    final_state(F),
    findall(Dist, manhattan(U, F, _, Dist), ListDist),
    sum_list(ListDist, H).

manhattan(S1, S2, P, Dist) :-
    coordonnees(S1, P, X1, Y1),
    coordonnees(S2, P, X2, Y2),
	P \= vide,
    Dist is abs(X1 - X2) + abs(Y1 - Y2).