Este acertijo es un forma parte de los denominados “puzzles de cruzar el río”, en los que el objetivo es mover una serie de objetos al otro lado del río siguiendo una serie de normas.
La aparición más temprana de este problema es en el manuscrito medieval Propositiones ad Acuendos Juvenes, los tres objetos son un lobo, una cabra y una col. Existen variaciones de este acertijo siendo los objetos una cabra, una oveja y un repollo; un zorro, una gallina y unas semillas; Un zorro, un ganso y una mazorca de maíz y una pantera, un cerdo y unas gachas.La lógica del acertijo sigue siendo la misma.
Este acertijo era uno de los favoritos de Lewis Carroll, y ha sido incluido en varios libros de matemática recreativa.
Planteamiento del problema:
Un granjero fue al mercado y compró un zorro una gallina y un maíz. 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. Además, si el lobo se queda solo con la gallina se la come y si la gallina se queda sola con el maíz 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?
Solución Teórica:
El primer paso el llevar la gallina a través del río, ya que de otro modo la gallina o el maíz serían devoradas. Cuando el granjero vuelve a la orilla original, puede elegir entre llevar al zorro o al maíz al otro lado. Si lleva al lobo, deben volver luego para llevar la al maíz, entonces el lobo se comería a la gallina. Si lleva al maíz al otro lado, necesitará volver para coger al zorro, entonces la gallina sería comida. Aquí se encuentra el dilema, se resuelve llevando el zorro (o el maíz) en la barca y trayendo de vuelta a la gallina. Ahora podemos llevar la el maíz (o el zorro), dejando la gallina y, finalmente, volver a buscar la gallina.- La solución se resume de la siguiente manera:
- Deja a la gallina al otro lado
- Vuelve
- Deja al zorro en el otro lado
- Regresa con la gallina
- Deja el maíz en el otro lado
- Vuelve
- Deja la gallina al otro lado
Implementación:
%accion(estado(Gra,Zorro,Gall,Maiz),estado(1,Z,1,M)).
estadoMalo(estado(0,1,1,_)).
estadoMalo(estado(0,_,1,1)).
estadoMalo(estado(1,0,0,_)).
estadoMalo(estado(1,_,0,0)).
accion(estado(0,0,G,M), estado(1,1,G,M), 'Llevar al zorro').
accion(estado(1,1,G,M), estado(0,0,G,M), 'Traer al zorro').
accion(estado(0,Z,0,M), estado(1,Z,1,M), 'Llevar la gallina').
accion(estado(1,Z,1,M), estado(0,Z,0,M), 'Traer la gallina').
accion(estado(0,Z,G,0), estado(1,Z,G,1), 'Llevar el maiz').
accion(estado(1,Z,G,1), estado(0,Z,G,0), 'Traer el maiz').
accion(estado(1,Z,G,M), estado(0,Z,G,M), 'Regresa solo').
accion(estado(0,Z,G,M), estado(1,Z,G,M), 'Ir solo').
pertenece(X,[X|_]):-!.
pertenece(X,[_|L]):-pertenece(X,L).
camino(estado(1,1,1,1),V,V).
camino(Estado,Visitado,R):-accion(Estado,NuevoEstado,A), not(estadoMalo(NuevoEstado)),
not(pertenece(NuevoEstado,Visitado)),
writeln(A),
camino(NuevoEstado,[NuevoEstado|Visitado],R).
solucion(L):-camino(estado(0,0,0,0),[estado(0,0,0,0)],L).
Este comentario ha sido eliminado por un administrador del blog.
ResponderEliminar