%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
%     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, Percurso, Solucao):-
		f_func(Estado,0,F),		     % Calcula a f(n)=g(n)+h(n)
		busca([Estado#0#F#[]], Percurso, S), % Busca solucao lembrando os
						     %  pontos percorridos
		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|_], Percurso, Soln):-   % Se Estado for a solucao
		goal(Estado).

busca([Estado#D#F#Soln|Resto], Percurso, S) :- 
	% Insere as coordenadas visitada na lista auxiliar
	insere2(Estado, Percurso, Result),
	% Expande os filhos no no'
	expande(Estado#D#F#Soln,Filhos,Result),
	% Insere ordenadamente 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, Result, 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#_) :- 	% Verivica se o no' tem o valor da funcao
	F1 < F2.			%  de custo inferior ao do outro no'

expande(Estado#D#_#S, TodosOsFilhos, Percurso) :-
		setof(Filho#D1#F#[Movimento|S],
			(
			  D1 is D + 1,
			  move(Estado, Filho, Movimento),
			 %Verifica se as coordenadas do Filho ja'
			 % nao foram percorridas
			  nao_percorrido(Filho,Percurso),
			  f_func(Filho, D1, F)
			),
			TodosOsFilhos).

nao_percorrido(Estado,[Estado1|Resto]):-
	Estado =\= Estado1,
	nao_percorrido(Estado,Resto).
nao_percorrido(Estado,[]). 

percorrido(Estado,[Estado|_]).
percorrido(Estado,[_|Resto]):-
	percorrido(Estado,Resto).

insere2(Estado, [Estado1|Resto], R):-
	insere2([Estado,Estado1|Resto], R).
insere2(Estado,[], R):-
	insere2([Estado], R).
insere2(Percurso, Percurso).

inverte([X|Y],Tmp,Saida) :- 
	inverte(Y,[X|Tmp],Saida).
inverte([],X,X).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
% Movimentos permitidos representados pelas direcoes cardinais,
% dadas as coordenadas do ponto atual e considerando um
% tabuleiro 8x8.
%

n(X1/Y1,X1/Y2):-
	Y1 < 8,		%Limite superior do tabuleiro
	Y2 is Y1 + 1.
s(X1/Y1,X1/Y2):-
	Y1 > 1,		%Limite inferior do tabuleiro
	Y2 is Y1 - 1.
l(X1/Y1,X2/Y1):-
	X1 < 8,
	X2 is X1 + 1.
o(X1/Y1,X2/Y1):-
	X1 > 1,
	X2 is X1 - 1.
ne(X1/Y1,X2/Y2):-
	X1 < 8,
	Y1 < 8,
	X2 is X1 + 1,
	Y2 is Y1 + 1.
no(X1/Y1,X2/Y2):-
	X1 > 1,
	Y1 < 8,
	X2 is X1 - 1,
	Y2 is Y1 + 1.
se(X1/Y1,X2/Y2):-
	X1 < 8,
	Y1 > 1,
	X2 is X1 + 1,
	Y2 is Y1 - 1.
so(X1/Y1,X2/Y2):-
	X1 > 1,
	Y1 > 1,
	X2 is X1 - 1,
	Y2 is Y1 - 1.

move(P1,P2,n) :- n(P1,P2).
move(P1,P2,s) :- s(P1,P2).
move(P1,P2,l) :- l(P1,P2).
move(P1,P2,o) :- o(P1,P2).
move(P1,P2,ne):- ne(P1,P2).
move(P1,P2,no):- no(P1,P2).
move(P1,P2,se):- se(P1,P2).
move(P1,P2,so):- so(P1,P2).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
% Funcao heuristica. Determina qual e' no numero de movimentos
% para se alcancar o objetivo.
%

h_fnc(X/Y, H):-
	goal(Gx/Gy),
	distancia(X,Y,Gx,Gy,H).

distancia(A,B,C,D, R) :-
	mod(A,C, X),	%Modulo de A-C
	mod(B,D, Y),	%Modulo de B-D
	max(X,Y, R),!.	%Maximo dos valores calculados acima

mod(A,B, X):-
	Z1 is A - B,
	Z2 is B - A,
	max(Z1,Z2, X).

max(X,Y, R):-
	X =< Y,
	R is Y.
max(X,Y, R):-
	X > Y,
	R is X.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
%     Rato no Tabuleiro
%
%
%     Estados sao da forma X/Y,
%     onde X e Y sao as coordenadas do rato ou do
%     queijo no tabuleiro.
%     Tabuleiro inicialmente com 8x8 posicoes
%             

go:-
	nl, write('Rato no Tabuleiro'),
	nl, write('Entre com a posicao do queijo(X/Y): '),
	read(EstadoQ),
	setgoal(EstadoQ),
	nl, write('Entre com a posicao do rato(X/Y): '),
	read(EstadoM),
	resolve(EstadoM, [], S),!,
	nl, write('Solucao: '),
	write(S),nl,
	retract(goal(EstadoQ)).
	
setgoal(X/Y):-
	assert(goal(X/Y)).


