Razonando un enigma simple
El enigma de los Misioneros y los caníbales al descubierto
| Autor: | Fernando J. Pereda <ferdy at gentoo dot org> |
|---|---|
| Licencia: | http://creativecommons.org/licenses/by-nc-sa/2.5/es/ |
Comentario inicial
Hace unos días, como cuento un poco más adelante, surgió la idea de implementar una solución a un enigma lógico usando un lenguaje de programación. La explicación de cómo resolver el problema le gustó a algunas personas y KarlanKas me invitó a escribir un artículo al respecto.
A lo largo del artículo intentaré no usar código muy complicado; sin embargo en algunos casos el código ayudará a entender la explicación. En esos casos el código será en lenguaje Haskell dado que mi solución la implementé usando este lenguaje.
En algunos casos se requerirán algunos conceptos matemáticos. No es necesario entenderlos a fondo para seguir la explicación; además en estos casos se darán referencias para entenderlos y más a fondo en caso de que el lector así lo desee.
Introducción
Hace unos días leía en blackshell Juanjo proponía un interesante reto. Se trataba de resolver el enigma de Misioneros y caníbales. En ese post además de explicar el enigma, da pistas de cómo implementó una solución en Ruby, y el código de la misma.
Estaba claro que en un lenguaje funcional como Haskell la solución tendría que ser más intuitiva y simple. A la hora de implementar la solución del problema en Haskell me di cuenta de que el planteamiento del problema requería revisar algunos apuntes de matemáticas. El hecho de que Haskell se defina como un λ-cálculo [1] extendido hace que para resolver problemas tengamos que pensar de una forma distinta.
Repaso del enigma
La idea es conseguir que tres misioneros y tres caníbales crucen de un lado a otro del río usando una pequeña canoa. Las reglas son simples:
- Nunca puede haber más caníbales que misioneros en ninguna de las orillas del río, o los caníbales se comerán a los misioneros.
- La canoa puede ser usada por una o dos personas. Tanto los caníbales como los misioneros saben llevar la canoa.
La idea es simple. Sin embargo si nunca se ha resuelto el enigma lo normal es que a la primera no salga nunca, y haya que darle vueltas al coco. Esto es porque pensamos de forma 'lineal'.
Modelado del problema
Resolver un problema de este estilo requiere ir probando todos los caminos posibles y ver si los estados a los que llegamos son válidos. Incluso si los estados son válidos no sabemos si llevarán a posibles soluciones o solo a estados no válidos.
Uno de los problemas al plantearse el enigma es que es posible hacer un bucle entre varios estados sin llegar nunca a la solución; así que resolverlo 'de cabeza' requerirá un trabajo adicional.
Para representar cada uno de los estados de este problema tendremos que representar el número de caníbales y de misioneros que hay en cada orilla del río y la orilla en la que se encuentra la canoa. Para hacer esto podemos empezar por representar una orilla:
type Orilla = (Int,Int)
Y para definir la posición de la canoa podemos usar algo como:
type PosCanoa = Inicio | Final
Ahora podemos definir un estado del problema fácilmente diciendo que un estado del problema se compone de dos orillas y además contiene una posición de la canoa:
type ProbEstado = (Orilla,Orilla,PosCanoa)
¿ Cómo llegar a una solución ?
Apunte inicial
Para llegar a una solución podemos plantear el problema como un grafo simple. Si lo hacemos así encontrar la solución simplemente será seguir los caminos del grafo desde el estado inicial al estado final.
Antes de seguir con el razonamiento voy a presentar una breve descripción (nada rigurosa) de lo que es un grafo. Los grafos suelen estudiarse en una rama de las matemáticas llamada Matemática Discreta [2].
¿ Qué es un grafo simple ?
Llamamos grafo simple a un conjunto de elementos relacionados entre sí. Por ejemplo si tenemos los elementos A B C y D, y decimos que B se relaciona con A, C y D, y además C se relaciona con D; el grafo resultante es el siguiente:
Es lo mismo decir que 'A se relaciona con B' a decir que 'B se relaciona con A'; de forma que unimos con una línea los elementos que se relacionan entre sí.
En ese grafo si queremos ir desde A hasta D podemos tomar dos caminos: ABD y ABCD. Ambos caminos son válidos sin embargo el primero es más corto y que el segundo; entonces diremos que el primer camino es óptimo.
Un ejemplo un poco más complejo de un grafo simple puede ser el siguiente:
Ahora para ir desde A hasta D hay más caminos: ABD, ABFECBD y ABCEFBD. Una peculiaridad de los dos caminos más largos es que contienen un bucle. En nuestro caso evitaremos los bucles para evitar soluciones infinitas; ya que un camino válido para ir de A a D también sería ABFECBFECBD pasando dos veces por el bucle y pasando tres veces y cuatro, así como infinitas veces.
El problema como un grafo simple
Para poder definir nuestro problema como un grafo simple tenemos que definir una función que dado un estado del problema nos devuelva una lista de 'sucesores' de ese estado; es decir, los estados relacionados con este. De forma que podríamos representar el grafo correspondiente al problema completo.
Una vez tenemos el grafo, como hemos visto, llegar a la solución del problema es muy sencillo.
Conclusión
Nos cuesta resolver el puzzle a la primera porque no somos capaces de pensar en grafos si no que pensamos de una forma más 'lineal'. El hecho de presentar el problema como un grafo nos permite solucionarlo muy fácilmente.
Dado el número de estados distintos del problema representar el grafo a mano puede ser muy tedioso y largo. Sin embargo con la ayuda de un lenguaje como Haskell se pueden implementar algoritmos que nos den todas las posibles soluciones del problema.
Como referencia, la implementación que hice en Haskell puede encontrarse aquí: MisCan.hs.
| [1] | El λ-cálculo es una rama de las matemáticas. Para más información: En inglés http://en.wikipedia.org/wiki/Lambda_calculus. Y en español: http://es.wikipedia.org/wiki/Cálculo_Lambda. |
| [2] | La Matemática Discreta es una rama de las matemáticas que trata con temas como Teoría de Conjuntos, Teoría de Grafos, Lógica y otras cosas. Para más información , ver http://es.wikipedia.org/wiki/Matemática_discreta para más información. |