En un blog anterior se resolvió, el problema de razonamiento denominado jarras de agua; con el lenguaje de programación Prolog, en este blog se sige con esa misma línea y se explica sobre la resolución de un popular juego de lógica llamado el acertijo del granjero, el lobo, la cabra y la col (hay un capítulo de los simpsons donde Homero resuelve un acertijo similar, para aquellos curiosos); el cual menciona lo siguiente:
"Hace mucho tiempo un granjero fue al mercado y compró un lobo, una cabra y una col. Para volver a su casa tenía que cruzar un río. El granjero dispone de una barca para cruzar a la otra orilla, pero en la barca solo caben él y una de sus compras. Si el lobo se queda solo con la cabra se la come, si la cabra se queda sola con la col se la come. El reto del granjero era cruzar él mismo y dejar sus compras a la otra orilla del río, dejando cada compra intacta." ¿Cómo lo hizo?
Como se mencionó en el blog anterior es necesario entender el problema, en este aspecto particular, basta con la descripción y el gráfico realizado en la parte de arriba, sin embargo lo que aún no está claro es cómo el granjero logró resolver el problema, por tanto a continuación se describe detalladamente la solución.
El primer paso es llevar la cabra a través del río, evitando que la cabra o la col sean devoradas. Cuando el granjero vuelve a la orilla de partida, debe elegir entre llevar la col o al lobo. Si lleva al lobo, debe volver para llevar la col, entonces el lobo se comería a la cabra. Si lleva la col al otro lado, debe volver para llevar al lobo, entonces la col sería comida. He aquí el problema, el cuál se resuelve con los siguientes 7 pasos:
1. Deja a la cabra al otro lado
2. Regresa al punto de partida (sólo el granjero)
3. Deja al lobo al otro lado
4. Regresa con la cabra
5. Deja la col al otro lado
6. Regresa al punto de partida (sólo el granjero)
7. Deja la cabra al otro lado
Se realizan cuatro viajes hacia la derecha y tres hacia la izquierda.
Cabe mencionar que esta no es la única solución, dado que existe una segunda alternativa, por ejemplo, en el tercer paso se puede dejar la col al otro lado y regresar con la cabra, luego dejar al lobo al otro lado y regresar solo, y finalmente regresar por la cabra.
Una vez claro el dilema, es momento de implementar dicha solución en Prolog.
Solución en Prolog
Para empezar con el código, antes es necesario definir las variables con las que se va a trabajar.
I= Izquierda, D= Derecha
GR= Granjero, CB= Cabra
LB= Lobo, CL= Col
Definido las variables, se parte de tres hechos, el primero es que el estado deseado final del granjero, la cabra, el lobo y la col terminen en la orilla izquierda asumiendo que todos parten del lado derecho , para lo cual en Prolog se representa de la siguiete manera:
meta(estado(izq, izq, izq, izq)).
La notación anterior indica que el estado final (meta) es que los cuatro actores de este acertijo terminen en la orilla izquierda, sin importar la posición inicial. La estructura estado recibe 4 argumentos que representan la posición en la que se encuentran cada uno de los actores del problema en el siguiente orden; en el primer argumento el granjero, en el segudo la cabra, el tercero el lobo y en el cuarto la col.
Nota 1: Es importante mencionar que para hacer uso del predicado estado se respetará el orden mencionado anteriormente (estado(GR, CB, LB, CL)).
El segundo y tercer hecho son la dirección de los movimientos que pueden realizar, en este caso solo hay dos posibilidades desde la derecha hacia la izquierda o vicerversa, por tanto definiré mi predicado con el nombre de "direccion" como se muestra a continuación.
direccion(izq, der).
direccion(der, izq).
Los hechos anteriores describen la siguiente relación, la dirección en la que puede moverse es desde la izquierda hacia la derecha y desde la derecha hacia la izquierda.
A continuación se definen varias reglas dado que un hecho puede depender de la verdad de otro hecho o conjunto de hechos, esto es que se va a definir los predicados para los posibles movimientos que puede hacer el granjero.
1.- Un movimiento a realizar es que el granjero cruce el río solo, en cualquier dirección, lo que en prolog se traduce en la siguiente regla:
movimiento(estado(M, CB, LB, CL), estado(M1, CB, LB, CL)):- direccion(M, M1).
La regla anterior menciona que el granjero se mueve de una orilla hacia la otra, si éste se mueve de deracha a izquierda o viceversa (direccion(M, M1).), además se puede apreciar claramente que los argumentos del "movimiento" son 2 estados, el primer estado que toma es estado(M, CB, LB, CL), que quiere decir que en el punto origen se encuentran el Granjero (M), la cabra (CB), el lobo (LB) y la col (CL); el segundo argumento es el estado en el punto destino estado(M1, CB, LB, CL); en donde el argumento del estado M1, indica que cambia solo el estado del granjero (sé que cambia el estado del granjero ya que el primer argumento del estado es utilizado para él, por ejemplo si quisiera que además cambie de estado la cabra, también debería cambiar el segundo argumento que toma el estado a M y M1, ver nota 1).
Nota 2: En el primer y segundo predicado en la posición del granjero, "estado" toma en el primero argumento el valor M y M1 respectivamente, ya que este me indetificará la dirección del movimiento a realizar. El cuerpo de la regla (direccion(M, M1)) indica que el movimiento se realiza si cumple la dirección indicada, es decir, si se mueve de derecha hacia la izquierda o lo contrario; por eso se indica en el argumento de dirección, que cambia M a M1 (los nombre de variables M y M1, pueden tomar cualquier otro nombre).
2.- El siguiente movimiento que puede hacer el granjero, es cruzar el río con el lobo, de nuevo en cualquier dirección:
movimiento(estado(M, CB, M, CL), estado(M1, CB, M1, CL)):- direccion(M, M1).
La regla anterior describe que el granjero y el lobo cruzan el río en una dirección determinada, por eso el cambio de nombre de variabe de GR y LB a M y M1; el análisis de la regla es similar al punto anterior.
3.- Un tercer movimiento del granjero es que cruce el río con la cabra.
movimiento(estado(M, M, LB, CL), estado(M1, M1, LB, CL)):- direccion(M, M1).
4.- El último movimiento que puede hacer el granjero es cruzar el río con la col.
movimiento(estado(M, CB, LB, M), estado(M1, CB, LB, M1)):- direccion(M, M1).
Bien, hasta este punto le hemos dicho a Prolog los movimientos que puede realizar el granjero, sin embargo hace falta especificar los movimiento que no debe hacer el granjero para cruzar el río con todas sus compras a salvo.
5.- Un estado prohibido una vez realizado el movimiento es que el granjero no puede estar al lado contrario del lobo y la cabra.
prohibido(estado(M, M1, M1, _)):- direccion(M, M1).
He creado un predicado denominado "prohibido", que recibe como argumento un "estado", para especificar que el el granjero esta al otro lado de la orilla de donde están el lobo y la cabra, he pasado en el primer argumento del estado, la posición M del granjero, y en el segundo y tercer argumento la misma posición M1 del lobo y la cabra, el símbolo "_", es una variable anónima que significa en este caso que no me interesa la posición en la que se encuentre la col, el cuerpo de la regla (direccion(M, M1)),indica la dirección en la que están.
6.- Otro estado prohibido es que la cabra y la col esten al otro lado del granjero.
prohibido(estado(M, M1, _, M1)):- direccion(M, M1).
Lista de estados
La solución al acertijo es una lista de estados (los que fueron analizados anteriormente) y es conveniente determinar que no existan estados repetidos, por tanto hay que verificar si un elemento pertenece a una lista, en Prolog se define de la siguiente manera:
miembro(X, [X|_]).
miembro(X, [_|L]):- miembro(X, L).
Solución
A continuación, se define la solución a este acertijo:
E = cabeza de la lista L = cola de la lista
solucion([E | L], [E | L]) :- meta(E).
Esta regla anterior permite determinar la solución base (definida con el mismo nombre sin acento) recibe 2 listas como parámetros, que deben ser iguales para ser la solución ([E | L], [E | L]), mismas que se dividen en cabeza y cola ([E | L]). La meta recibe la cabeza de la lista el cual es un estado que anteriormente ya se definió para que sea solución meta(estado(izq, izq, izq, izq)), en el caso que no sea la solución base se define la siguiente regla:
solucion([E | L], LS):- movimiento(E, EP), not(prohibido(EP)), not(miembro(EP, L)), solucion([EP, E | L], LS).
Esta regla permite añadir a la lista de soluciones un nuevo estado (EP) si cumple las siguientes condiciones:
- Es un movimiento permitido (movimiento(E, EP))
- No es un estado prohibido (not(prohibido(EP)))
- No se encuentra un estado igual en la lista de solucioines (not(miembro(EP, L)))
Nota 3: La variable LS, almacena el resultado, es decir la lista de estados que permiten llegar a la solución, el cual prolog mostrará como salida.
Si cumple con las condiciones anteriores, el nuevo estado posible es añadida a la lista de soluciones ([EP, E | L]), esto se repite recursivamente hasta encontrar el caso base (solucion([EP, E | L], LS)), y listo!.
Para ejecutar el programa en Prolog, se lo hace de la siguiente manera:
solucion([estado(der, der, der, der)], L).
La solución recibe una lista de estados, en este caso he puesto solo un elemento en la lista (estado(der, der, der, der)), y en este estado todos los actores del problema están en la parte derecha de la orilla del río, en la variable L se almacenara la lista de estados. Al ejecutar en prolog me muestra dos soluciones que son las siguientes:
L = [estado(izq, izq, izq, izq), estado(der, der, izq, izq), estado(izq, der, izq, izq), estado(der, der, izq, der), estado(izq, izq, izq, der), estado(der, izq, der, der), estado(izq, izq, der, der), estado(der, der, der, der)]
L = [estado(izq, izq, izq, izq), estado(der, der, izq, izq), estado(izq, der, izq, izq), estado(der, der, der, izq), estado(izq, izq, der, izq), estado(der, izq, der, der), estado(izq, izq, der, der), estado(der, der, der, der)]
A continuación se muestra todo el código:
meta(estado(izq, izq, izq, izq)).
direccion(izq, der).
direccion(der, izq).
/* Movimientos permitidos */
movimiento(estado(M, CB, LB, CL), estado(M1, CB, LB, CL)):- direccion(M, M1).
movimiento(estado(M, CB, M, CL), estado(M1, CB, M1, CL)):- direccion(M, M1).
movimiento(estado(M, M, LB, CL), estado(M1, M1, LB, CL)):- direccion(M, M1).
movimiento(estado(M, CB, LB, M), estado(M1, CB, LB, M1)):- direccion(M, M1).
/* Movimientos prohibidos */
prohibido(estado(M, M1, M1, _)):- direccion(M, M1).
prohibido(estado(M, M1, _, M1)):- direccion(M, M1).
/* Verifica si un elemento pertenece a una lista */
miembro(X, [X|_]).
miembro(X, [_|L]):- miembro(X, L).
/* Solución */
solucion([E | L], [E | L]) :- meta(E).
solucion([E | L], LS):- movimiento(E, EP), not(prohibido(EP)), not(miembro(EP, L)), solucion([EP, E | L], LS).
También pueden encontrar el mismo código en GitHub.
Con esto concluimos, en casos de dudas pueden contactarme a fabianq44@gmail.com.
¡Gracias por su lectura!