%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
%     Algoritmo A*
%
%
%     Os nos da arvore de solucoes sao da forma S#D#F#A
%            onde  S e' o estado
%                  D e' a profundidade (depth) do no'
%                  F e' o valor da funcao de avaliacao
%                  A e' a lista que antecede o no'

:- op(400,yfx,'#').    /* Notacao do construtor do no' */

resolve(Estado, Solucao):-
		f_func(Estado,0,F),	   % Calcula a f(n)=g(n)+h(n)
		busca([Estado#0#F#[]], S), % Busca solucao
		inverte(S, [], Solucao).   % Inverte a lista temporaria
					   %  para apresentar a solucao

f_func(Estado,D,F):- 		 % f(n)=g(n)+h(n)
		h_fnc(Estado,H), % h(n) - Funcao Heuristica
		F is D + H.	 % g(n) e' dada por D que e' a profundidade
				 %  do no'.


busca([Estado#_#_#Soln|_], Soln):-   % Se Estado for a solucao
		goal(Estado).

busca([No|Resto], S) :- 
	% Expande os filhos no no'
	expande(No,Filhos),
	% Insere os filhos na lista de nos a serem percorridos (EmAberto)
	insere_todos(Filhos, Resto, EmAberto), 
	% Repete a busca entre os nos nao explorados
	busca(EmAberto, S).

insere_todos([Primeiro|Resto], EmAberto1, EmAberto3) :- 
	insere(Primeiro, EmAberto1, EmAberto2),
	insere_todos(Resto, EmAberto2, EmAberto3).

insere_todos([], EmAberto, EmAberto).

insere(No, EmAberto, EmAberto) :- 
	repetido(No, EmAberto), !.

insere(No, [OutroNo | Resto], [No, OutroNo | Resto]) :- 
	mais_barato(No, OutroNo), !.

insere(No, [No1 | Resto], [No1 | S]) :- 
	insere(No, Resto, S), !.

insere(No, [], [No]).

repetido(P#_#_#_, [P#_#_#_|_]).		% Verifica se o no' ja' nao foi inserido

mais_barato(_#_#F1#_, _#_#F2#_) :- 	% Verifica se o no' tem o valor da funcao
	F1 < F2.			%  de custo inferior ao do outro no'

expande(Estado#D#_#S, TodosOsFilhos) :-
		bagof(Filho#D1#F#[Movimento|S],
			(
			  D1 is D + 1,
			  move(Estado, Filho, Movimento),
			  f_func(Filho, D1, F)
			),
			TodosOsFilhos).

inverte([X|Y],Tmp,Saida) :- 
	inverte(Y,[X|Tmp],Saida).
inverte([],X,X).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
%     TRY ME
%
%     Estados sao da forma T/R/Y/M/E/Z
%     onde {T,R,Y,M,E,Z} = {1,2,3,4,5,0}
%     e 0 representa o espaco vazio
%
%     Abaixo sao ilustrados os movimentos permitidos.
%             
% O objetivo e' representado por:
goal(4/5/0/1/2/3).

esquerda( 0/R/Y/M/E/T , R/0/Y/M/E/T ).
esquerda( R/0/Y/M/E/T , R/Y/0/M/E/T ).
esquerda( T/R/Y/0/M/E , T/R/Y/M/0/E ).
esquerda( T/R/Y/M/0/E , T/R/Y/M/E/0 ).

frente( T/R/0/M/E/Y , T/R/Y/M/E/0 ).
frente( T/0/R/M/E/Y , T/E/R/M/0/Y ).
frente( 0/R/Y/M/E/T , M/R/Y/0/E/T ).

direita( T/R/0/M/E/Y , T/0/R/M/E/Y ).
direita( T/0/R/M/E/Y , 0/T/R/M/E/Y ).
direita( T/R/Y/M/E/0 , T/R/Y/M/0/E ).
direita( T/R/Y/M/0/E , T/R/Y/0/M/E ).

tras( T/R/Y/M/E/0 , T/R/0/M/E/Y ).
tras( T/R/Y/M/0/E , T/0/Y/M/R/E ).
tras( T/R/Y/0/M/E , 0/R/Y/T/M/E ).

move(P,C,esquerda) :-
	esquerda(P,C).
move(P,C,frente) :-
	frente(P,C).
move(P,C,direita) :-
	direita(P,C).
move(P,C,tras) :-
	tras(P,C).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
% Funcao heuristica. E' a combinacao de dois estimadores
% utilizados na resolucao de problemas de sliding blocks:
% a funcao de distancia Manhattan,
% e a funcao de fora-de-ciclo.
%

h_fnc(Puzz,H) :- 
	p_fcn(Puzz,P),
	s_fcn(Puzz,S),
	H is P + 3*S.

   
% A funcao de distancia Manhattan
p_fcn(T/R/Y/M/E/Z, P) :-
     t(T,Pt), r(R,Pr), y(Y,Py),
     m(M,Pm), e(E,Pe), z(Z,Pz),
     P is Pt+Pr+Py+Pm+Pe+Pz.

t(0,0). t(1,0). t(2,1). t(3,2). t(4,3). t(5,4).
r(0,0). r(1,1). r(2,0). r(3,1). r(4,2). r(5,3).
y(0,0). y(1,2). y(2,1). y(3,0). y(4,1). y(5,2).
m(0,0). m(1,1). m(2,2). m(3,3). m(4,2). m(5,3).
e(0,0). e(1,2). e(2,1). e(3,2). e(4,1). e(5,2).
z(0,0). z(1,3). z(2,2). z(3,1). z(4,0). z(5,1).

% A funcao de fora-de-ciclo
s_fcn(T/R/Y/M/E/Z, S) :-
     s_aux(T,R,S1), s_aux(R,Y,S2), s_aux(Y,Z,S3),
     s_aux(Z,E,S4), s_aux(E,D,S5), s_aux(D,T,S6),
     S is S1+S2+S3+S4+S5+S6.

s_aux(0,0) :- !.
s_aux(_,1).

s_aux(X,Y,0) :- 
	Y is X+1, !.
s_aux(5,1,0) :- !.
s_aux(_,_,2).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
% Solucao do problema:
% Estado inicial: T/R/Y/M/E/Z = 1/2/3/4/5/0
% Objetivo(goal): M/E/Z/T/R/Y = 4/5/0/1/2/3
%

go:-
	nl, write('Estado inicial:'),
	nl, write('T R Y'),
	nl, write('M E  '),
	nl, write('Solucao:'),
	resolve(1/2/3/4/5/0, S),
	nl, write(S),nl.
