El problema del granjero mediante búsqueda en espacio de estado

Un granjero está parado en un lado del río y con él tiene un una cabra y una repollo. En el río hay un barco pequeño. El desea cruzar el río con sus tres posesiones. No hay puentes y en el barco hay solamente sitio para el granjero y un artículo. Si deja la cabra con la repollo sola en un lado del río la cabra comerá la repollo. Si deja el lobo y la cabra en un lado, el lobo se comerá a la cabra. ¿Cómo puede cruzar el granjero el río con los tres artículos, sin que ninguno se coma al otro?

Para representar el problema se definen los siguientes tipos de dato:

  • Orilla con dos constructores (I y D) que representan las orillas izquierda y derecha, respectivamente.
  • Estado que es una tupla que representa en qué orilla se encuentra cada uno de los elementos (granjero, lobo, cabra, repollo). Por ejemplo, (I,D,D,I) representa que el granjero está en la izquierda, que el lobo está en la derecha, que la cabra está en la derecha y el repollo está en la izquierda.

Usando el procedimiento de búsqueda en profundidad, definir la función

tal que granjero son las soluciones del problema del granjero mediante el patrón de búsqueda en espacio de estados. Por ejemplo,

Soluciones

A continuación se muestran las soluciones en Haskell y las soluciones en Python.


Soluciones en Haskell


Soluciones en Python

Escribe tu solución