misioneros.pl

%estado(M,C,d) significa M canibales a la derecha, C canibales a la derecha, balsa a la Derecha
%estado(M,C,i) significa M canibales a la derecha, C canibales a la derecha, balsa a la Izquierda
%estado(3,3,d) es el estado inicial
%estado(0,0,i) es el estado final

%movimientos posibles: Mover 2 misioneros de lado, mover 2 canibales de lado, mover 1 misionero o 1 canibales
%estado correcto: 0 misioneros cualquier canibal o M >= C

unPaso([M,C,d],[M2,C,i]):-
    M2 is M - 2,
    M2 >= 0.
unPaso([M,C,d],[M,C2,i]):-
    C2 is C - 2,
    C2 >= 0.
unPaso([M,C,d],[M2,C,i]):-
    M2 is M - 1,
    M2 >= 0.
unPaso([M,C,d],[M,C2,i]):-
    C2 is C - 1,
    C2 >= 0.
unPaso([M,C,d],[M2,C2,i]):-
    M2 is M - 1,
    C2 is C - 1,
    M2 >= 0,
    C2 >= 0.

unPaso([M,C,i],[M2,C,d]):-
    M2 is M + 2,
    M2 < 4.
unPaso([M,C,i],[M,C2,d]):-
    C2 is C + 2,
    C2 < 4.
unPaso([M,C,i],[M2,C,d]):-
    M2 is M + 1,
    M2 < 4.
unPaso([M,C,i],[M,C2,d]):-
    C2 is C + 1,
    C2 < 4.
unPaso([M,C,i],[M2,C2,d]):-
    M2 is M + 1,
    C2 is C + 1,
    M2 < 4,
    C2 < 4.

estadoOK([0,_,_]).
estadoOK([M,C,_]):-
    M >= C.

nat(0).
nat(N):-
    nat(N1),
    N is N1 + 1.

camino( E,E, C,C ).
camino( EstadoActual, EstadoFinal, CaminoHastaAhora, CaminoTotal ):-
    unPaso( EstadoActual, EstSiguiente ),
    estadoOK(EstSiguiente),
    \+member(EstSiguiente,CaminoHastaAhora),
    camino( EstSiguiente, EstadoFinal, [EstSiguiente|CaminoHastaAhora], CaminoTotal ).
solucionOptima:-
    nat(N), % Buscamos solucion de "coste" 0; si no, de 1, etc.
    camino([3,3,d],[0,0,i],[[3,3,d]],C),
    length(C,N),
    reverse(C,S),
    write("Coste de la solucion: "), write(N), nl,
    prettyPrint(S,1).

prettyPrint([],_).
prettyPrint([X|S],N):-
    write("Estado "), write(N), write(": "), write(X), nl,
    N1 is N + 1,
    prettyPrint(S,N1).