/*[]======================================================================[]
  []									  []
  []      		Busca Uniforme (ou Branch and Bound)              []
  []   									  []
  []      		Alunas: Cristiane Y. Imamura			  []
  []		  		Teresinha Arnauts			  []
  []									  []
  []======================================================================[]*/ 	  



/*--------------------------------------------------------------------------

	Declaracao dos operadores

 --------------------------------------------------------------------------*/

:- op(35, xf, [e_uma_meta, atinge_uma_meta]).
:- op(35,xfx,[transforma,nao_produz_circulos_em]).
:- op(30,xfx,[a,em]).



/*[]======================================================================[]
  []									  []
  []      Base de Conhecimento para o problema das 7 fichas               []
  []   									  []
  []      Alunas: Cristiane Y. Imamura					  []
  []		  Teresinha Arnauts					  []
  []									  []
  []======================================================================[]*/ 	  


/*-------------------------------------------------------------------------

			Formalizacao do problema
	*	indicam fichas pretas
	o	indicam fichas brancas
	i	indica espaco vazio
	
  -----------------------------------------------------------------------*/

estado_inicial([*,*,*,o,o,o,i]).



[o,o,o,*,*,*,i] e_uma_meta.
[o,o,o,*,*,i,*] e_uma_meta.
[o,o,o,*,i,*,*] e_uma_meta.
[o,o,o,i,*,*,*] e_uma_meta.
[o,o,i,o,*,*,*] e_uma_meta.
[o,i,o,o,*,*,*] e_uma_meta.
[i,o,o,o,*,*,*] e_uma_meta.


/*-------------------------------------------------------------------------
 Declaracao dos predicados que definem as acoes de deslizar e saltar
   
	* desliza :	move uma ficha para o espaco vazio adjacente.

	* salta   :	desloca a ficha duas posicoes ocupando um
			lugar vazio.
			Equivale a saltar uma ficha.

	* salta2  :     desloca a ficha tres posicoes ocupando um 
			lugar vazio.
			Equivale a saltar duas fichas.

	predicado operacao(acao, custo) transforma estado1 em estado2
  ------------------------------------------------------------------------*/	


operacao(desliza,1) transforma [A,B,C,D,E,F,i] em [A,B,C,D,E,i,F].
operacao(salta,1) transforma [A,B,C,D,E,F,i] em [A,B,C,D,i,F,E].
operacao(salta,2) transforma [A,B,C,D,E,F,i] em [A,B,C,i,E,F,D].

operacao(desliza,1) transforma [A,B,C,D,E,i,F] em [A,B,C,D,i,E,F].
operacao(desliza,1) transforma [A,B,C,D,E,i,F] em [A,B,C,D,E,F,i].
operacao(salta,1) transforma [A,B,C,D,E,i,F] em [A,B,C,i,E,D,F].
operacao(salta,2) transforma [A,B,C,D,E,i,F] em [A,B,i,D,E,C,F].

operacao(desliza,1) transforma [A,B,C,D,i,E,F] em [A,B,C,i,D,E,F].
operacao(desliza,1) transforma [A,B,C,D,i,E,F] em [A,B,C,D,E,i,F].
operacao(salta,1) transforma [A,B,C,D,i,E,F] em [A,B,i,D,C,E,F].
operacao(salta,1) transforma [A,B,C,D,i,E,F] em [A,B,C,D,F,E,i].
operacao(salta,2) transforma [A,B,C,D,i,E,F] em [A,i,C,D,B,E,F].

operacao(desliza,1) transforma [A,B,C,i,D,E,F] em [A,B,i,C,D,E,F].
operacao(desliza,1) transforma [A,B,C,i,D,E,F] em [A,B,C,D,i,E,F].
operacao(salta,1) transforma [A,B,C,i,D,E,F] em [A,i,C,B,D,E,F].
operacao(salta,1) transforma [A,B,C,i,D,E,F] em [A,B,C,E,D,i,F].
operacao(salta,2) transforma [A,B,C,i,D,E,F] em [i,B,C,A,D,E,F].
operacao(salta,2) transforma [A,B,C,i,D,E,F] em [A,B,C,F,D,E,i].

operacao(desliza,1) transforma [A,B,i,C,D,E,F] em [A,i,B,C,D,E,F].
operacao(desliza,1) transforma [A,B,i,C,D,E,F] em [A,B,C,i,D,E,F].
operacao(salta,1) transforma [A,B,i,C,D,E,F] em [i,B,A,C,D,E,F].
operacao(salta,1) transforma [A,B,i,C,D,E,F] em [A,B,D,C,i,E,F].
operacao(salta,2) transforma [A,B,i,C,D,E,F] em [A,B,E,C,D,i,F].

operacao(desliza,1) transforma [A,i,B,C,D,E,F] em [i,A,B,C,D,E,F].
operacao(desliza,1) transforma [A,i,B,C,D,E,F] em [A,B,i,C,D,E,F].
operacao(salta,1) transforma [A,i,B,C,D,E,F] em [A,C,B,i,D,E,F].
operacao(salta,2) transforma [A,i,B,C,D,E,F] em [A,D,B,C,i,E,F].

operacao(desliza,1) transforma [i,A,B,C,D,E,F] em [A,i,B,C,D,E,F].
operacao(salta,1) transforma [i,A,B,C,D,E,F] em [B,A,i,C,D,E,F].
operacao(salta,2) transforma [i,A,B,C,D,E,F] em [C,A,B,i,D,E,F].

/*--------------------------------------------------------------------------

	Programas auxiliares

 --------------------------------------------------------------------------*/

%--------------------------------------------------------------------------
% 		ap : concatena duas listas.
%--------------------------------------------------------------------------

ap([],X,X):- !.
ap([X|Y],Z,[X|W]):- ap(Y,Z,W).


%--------------------------------------------------------------------------		
% 	membro : verifica se um elemento esta em uma lista
%--------------------------------------------------------------------------

membro(X,[X|_]):- !.
membro(X,[_|Y]):- membro(X,Y).


%--------------------------------------------------------------------------

%--------------------------------------------------------------------------

ache_todos(X,Y,Z):- findall(X,Y,Z), !.
ache_todos(_,_,[]).

%--------------------------------------------------------------------------
% 	imprima :  serve para imprimir uma trazetoria.
%   	A trajetoria e representada por uma lista de estruturas do tipo
%   	r(R,Nodo), onde R e o ramo que liga Nodo ao pai dele.
%--------------------------------------------------------------------------

imprima(t(GN,T)) :- imprima_trajet(T).

imprima_trajet([r(raiz,Raiz)]):- !,
	write('Estado Incial: '), write(Raiz), write('.').

imprima_trajet([r(Ramo,Nodo)|R]):- 
	imprima_trajet(R), nl,
	write(Ramo), write(' e, portanto, temos: '), nl,
	write(Nodo), write('.').
	
%--------------------------------------------------------------------------
%	resolva: chama o programa que faz a busca uniforme
%--------------------------------------------------------------------------

resolva:- estado_inicial(E), 
	  busca([t(0,[r(raiz,E)])], Solucao), 
	  imprima(Solucao), nl.
	
	

%--------------------------------------------------------------------------
%	busca:	realiza a busca uniforme, procurando o caminho q o leva
%		a uma das metas.
%--------------------------------------------------------------------------


busca([T|_],Solucao):- T atinge_uma_meta, !, Solucao = T.


busca([T|Fila],Solucao):-
	ache_todos(ExtensaoAteUmFilho, estende_ate_filho(T,ExtensaoAteUmFilho),Extensoes),
	ap(Fila,Extensoes,FilaEstendida),
	sort(FilaEstendida,FilaComMelhorNaFrente),
	busca(FilaComMelhorNaFrente,Solucao).

estende_ate_filho(t(G,[r(Ramo,Nodo)| Trajetoria]),
	t(G1,[r(Op,NodoFilho),r(Ramo,Nodo) | Trajetoria])) :-
	operacao(Op,Custo) transforma Nodo em NodoFilho,
	not( NodoFilho nao_produz_circulos_em Trajetoria),
	G1 is G + Custo.


Estado nao_produz_circulos_em Trajetoria:- 
	membro(r(Operacao,Estado),Trajetoria).

t(_,[r(Ramo,M)|_]) atinge_uma_meta :- M e_uma_meta.

