/* Problema do pastor
===> quanto a correspondência dos functores...
Repolho ----------------------------------|
Ovelha --------------------------| |
Lobo -----------------| | |
Pastor --------| | | |
V V V V
move(estado(esquerda,esquerda,esquerda,esquerda),
estado(direita,direita,direita,direita) ).
^ ^
| |
| |
Corrente Novo
objetivo interno ===> travessia.
*******************************************/
/* melhora a busca_profundidade ===> já informa qual estado que
os 04 objetos já se encontraram ... */
travessia :- busca_profundidade(estado(esquerda,esquerda,esquerda,esquerda),
[estado(esquerda,esquerda,esquerda,esquerda)]).
travessia.
todas_travessias :- travessia, fail.
/* início do programa :: condição inicial e parada ... definidas */
/* condição de parada no estado final */
busca_profundidade( X , L) :-
X == estado(direita,direita,direita,direita), nl,
write('=============================================='),
qtd_move(L,N),
write('\n Uma solução com '), write(N),
write(' movimentos é dada por:: \n'),
reverse(L,L_invertida),
imprima_caminho(L_invertida).
/* compara... há casamento entre o estado corrente e o final ? */
/* aqui é o núcleo do processo de busca_profundidade */
busca_profundidade(Estado_inicial, Visitados):-
/* ache um movimento */
move(Estado_inicial,Proximo_estado),
/* Verifique se é valido */
not( inseguro(Proximo_estado) ),
/* Verifique se já não esteve em uma tentativa anteriores */
not( eh_membro(Proximo_estado,Visitados) ),
/* encontre recursivamente outro movimento */
busca_profundidade( Proximo_estado, [Proximo_estado|Visitados]).
/* Definindo os movimentos possiveis */
/* Move Pastor + Lobo */
move(estado(X,X,O,R),estado(Y,Y,O,R)):-oposto(X,Y).
/*Move Pastor + Ovelha */
move(estado(X,L,X,R),estado(Y,L,Y,R)):-oposto(X,Y).
/* Move Pastor + Repolho */
move(estado(X,L,O,X),estado(Y,L,O,Y)):-oposto(X,Y).
/* Move Pastor sozinho */
move(estado(X,L,O,R),estado(Y,L,O,R)):-oposto(X,Y).
/* Declarando o conceito de oposto */
oposto(esquerda,direita).
oposto(direita,esquerda).
/* O lobo come a ovelha */
inseguro( estado(P,X,X,_) ):- oposto(P,X),!.
/* A ovelha come o repolho */
inseguro( estado(P,_,X,X) ):- oposto(P,X),!.
qtd_move([],0).
qtd_move([_|L],N) :- qtd_move(L,N1), N is N1 + 1.
eh_membro(X,[X|_]):-!.
eh_membro(X,[_|L]):-eh_membro(X,L).
imprima_caminho( [H1,H2|T] ) :-
imprima_movimento(H1,H2),
imprima_caminho([H2|T]).
imprima_caminho( _ ).
/* as travessias */
imprima_movimento( estado(X,W,G,C), estado(Y,W,G,C) ) :-!,
write('O Pastor atravessa o rio da margem '),
write(X), write(' para a margem '), write(Y), nl.
imprima_movimento( estado(X,X,G,C), estado(Y,Y,G,C) ) :-!,
write('O Pastor leva o Lobo da margem '),
write(X), write(' do rio para a margem '), write(Y),nl.
imprima_movimento( estado(X,W,X,C), estado(Y,W,Y,C) ) :-!,
write('O Pastor leva a Ovelha da margem '),
write(X), write(' do rio para a margem '), write(Y),nl.
imprima_movimento( estado(X,W,G,X), estado(Y,W,G,Y) ) :-!,
write('O Pastor leva o Repolho da margem '),
write(X), write(' do rio para a margem '), write(Y), nl.