Misioneros y caníbales

Se trata de un problema que tuve que resolver en Prolog para una de las prácticas de lógica de primer orden. Como siempre se me han dado muy mal ese tipo de acertijos lógicos (y no me refiero a Prolog), me impresionaba que mi programa diera el resultado, porque yo no sabía resolverlo a mano.

Además pasa que Prolog es un lenguaje que sigue el paradigma declarativo, mientras que yo ya estaba malformado casi irremediablemente por el uso de lenguajes imperativos. En este lenguaje se define un universo limitado, principalmente mediante asociaciones y declaraciones tipo A → B (A implica B). Una vez hemos aportado suficientes datos, indicamos un estado inicial y un estado objetivo. Y entonces Prolog mágicamente da con el resultado, sin que nosotros le indiquemos explícitamente cómo hacerlo.

Ya lo dice la tercera ley de Clarke: Toda tecnología lo suficientemente avanzada es indistinguible de la magia, y además yo añadiría un corolario: La capacidad de distinción entre magia y tecnología depende del individuo. Es que ahora sé que Prolog no hace magia :D.

Prolog emplea una técnica en la toma de decisiones que se conoce como backtracking, y consiste en poder volver atrás al punto anterior cuando se toma una decisión que rompe alguna de las condiciones que hemos impuesto al problema, por ejemplo: el problema de los misioneros y los caníbales.

Tres misioneros y tres caníbales quieren cruzar un río. Solo hay una canoa que puede ser usada por una o dos personas, ya sean misioneros o caníbales.

Hay que tener cuidado en que en ningún momento el número de caníbales supere al de misioneros en ninguna de las dos orillas, o se los comerán.

Además está implícito en la descripción que mientras queden individuos en la primera orilla, alguien tendrá que llevar la canoa de vuelta.

Voy a plantear una solución en Ruby, que sigo practicando. Tampoco me he querido calentar la cabeza demasiado, así que voy a dar una solución, sin plantearme si es la mejor o no. De esta forma simplificamos sin tener que calcular todas las soluciones, y acabamos cuando damos con todo el personal y la canoa en la orilla adecuada.

Para implementar mi backtracking voy a emplear las funciones push y pop los objetos Array (vector) para almacenar el estado en cada decisión (individuos a cada lado, posición de la canoa, posibles viajes probados), y así si llegamos a un punto sin solución, podremos volver atrás y probar con otro posible viaje.

Me ha venido bien, porque me he dado de bruces con una característica de Ruby que no esperaba. En este lenguaje todo es una referencia, así que explícitamente tenemos que pedir que nos hagan una copia de un vector (con dup o clone, no vale una asignación normal), pero sorpresa: no se duplica recursivamente, así que si un vector contiene a otro, tendremos que preocuparnos nosotros de duplicar a esos dos niveles. En el código indico los casos, que se verá más claro.

He empleado vectores para manejar los estados y los viajes posibles, con constantes para los índices. Llamemos a los misioneros M y a los caníbales C:

• Estado_ini: 3M y 3C en la izquierda, 0M y 0C en la derecha, y la canoa en la izquierda. Aquí es donde empezamos.
• Estado_fin: 0M y 0C en la izquierda, 3M y 3C en la derecha, y la canoa en la derecha. Aquí es a donde queremos llegar.
• Viajes: 1M y 0C, 0M y 1C, 1M y 1C, 2M y 0C, 0M y 2C. Son las posibilidades de personal que puede ir en la canoa. Como no busco todas las soluciones, el resultado dependerá del orden en el que se prueben estas posibilidades.

He definido 3 funciones auxiliares, para simplificar el algoritmo:

• valido?(estado): devuelve cierto si un estado es válido. Comprueba que el número de individuos sea correcto, porque probamos todos los viajes, aunque sean imposibles. Además verifica las condiciones del problema (que no se coman a la gente).
• canoa(estado, viaje): modifica el estado según el viaje indicado.
• muestraEstado(estado): muestra el estado de una forma más o menos bonita.

Y finalmente, el código:

#!/usr/bin/ruby
=begin
 
Tres misioneros y tres caníbales quieren cruzar un río. Solo hay una canoa
que puede ser usada por una o dos personas, ya sean misioneros o caníbales.
 
Hay que tener cuidado en que en ningún momento el número de caníbales supere
al de misioneros en ninguna de las dos orillas, o se los comerán.
 
Juan J. Martínez <reidrac*en*blackshell.usebox.net>
 
=end
 
# algunas constantes útiles para facilitar el trabajo con el vector
Izq = 0
Der = 1
Canoa = 2
M = 0
C = 1
 
# todos a la izquierda, y la posición de la canoa
Estado_ini = [ [ 3, 3 ], [ 0, 0 ], Izq ]
# todos a la derecha, y la posición de la canoa
Estado_fin = [ [ 0, 0 ], [ 3, 3 ], Der ]
 
# viajes posibles (misionero, caníbal)
Viajes = [ [ 1, 0], [0, 1], [1, 1], [2, 0], [0, 2] ]
 
# devuelve si un estado es válido para las reglas del juego
def valido?(estado)
	# logico, que no hayan de más o de menos
	if estado[Izq][M] > 3 || estado[Izq][M] < 0 ||
		estado[Der][M] > 3 || estado[Der][M] < 0 ||
		estado[Izq][C] > 3 || estado[Izq][C] < 0 ||
		estado[Der][C] > 3 || estado[Der][C] < 0
		return false
	# que no haya mas C que M a la Izq
	elsif estado[Izq][M] != 0 &&
		estado[Izq][M] < estado[Izq][C]
		return false
	# que no haya mas C que M a la Der
	elsif estado[Der][M] != 0 &&
		estado[Der][M] < estado[Der][C]
		return false
	end
 
	# es OK
	true
end
 
# cambia el estado según indica el viaje
def canoa(estado, viaje)
	estado[estado[Canoa]][M] -= viaje[M]
	estado[estado[Canoa]][C] -= viaje[C]
 
	if estado[Canoa] == Izq
		estado[Canoa] = Der
	else
		estado[Canoa] = Izq
	end
 
	estado[estado[Canoa]][M] += viaje[M]
	estado[estado[Canoa]][C] += viaje[C]
end
 
# una forma cómoda de mostrar el estado
def muestraEstado(estado)
	printf("M:%d C:%d", estado[Izq][M], estado[Izq][C])
 
	printf(" \\___/") if estado[Canoa] == Izq
 
	printf(" ~~~~~~~~ ")
 
	printf("\\___/ ") if estado[Canoa] == Der
 
	printf("M:%d C:%d", estado[Der][M], estado[Der][C])
	
	printf("\n")
end
 
# para poder volver atrás
viajes = Array.new
anterior = Array.new
# empezamos por el principio
estado = Estado_ini
# no duplicamos los vectores internos porque nos los mnodificamos
posibles = Viajes.dup
 
# hasta que no acabemos, pega vueltas
while estado != Estado_fin
	if posibles == nil
		STDOUT.puts "NO he encontrado solucion!"
		exit
	end
 
	# probamos viajes hasta que se nos acaben o uno sea válido
	while ! posibles.empty?
		viaje = posibles.shift
 
		# duplicamos los vectores internos
		posibleEstado =  [ estado[Izq].dup, estado[Der].dup,
			estado[Canoa] ]
		canoa(posibleEstado, viaje)
 
		# salimos si es válido y no se ha repetido
		break if valido?(posibleEstado) &&
			anterior.index(posibleEstado) == nil
 
		# no es válido
		posibleEstado = nil
	end
 
	# tenemos uno válido?
	if posibleEstado != nil
		# nos acordamos del estado actual
		anterior.push estado
		viajes.push posibles
 
		# aceptamos el viaje como bueno (por ahora)
		estado = posibleEstado
		posibles = Viajes.dup
	else
		# el viaje no nos ha llevado a un resultado
		# asi que recuperamos el estado anterior
		estado = anterior.pop
		posibles = viajes.pop
 
		posibleEstado = nil
	end
end
 
puts "Tenemos una solución!"
 
# muestra la solucion
while (resultado = anterior.shift) != nil
	muestraEstado(resultado)
end
 
muestraEstado(estado)
 
# EOF 

He puesto muchos comentarios, pero el mecanismo es bastante sencillo.

Realizamos un bucle que da vueltas mientras el estado no sea el que deseamos. En una primera fase vamos probando viajes hasta que uno sea válido y además no nos lleve a un estado anterior (para evitar bucles, que sabemos que el resultado no los tiene). Si encontramos un estado válido, almacenamos el estado actual y tomamos en nuevo como bueno. En caso de que no se haya encontrado un estado, pues empleamos el backtracking y volvemos al estado anterior para probar otra posibilidad.

El resultado que da con ese vector de Viajes es:

$ ./enigma.rb
Tenemos una solución!
M:3 C:3 \___/ ~~~~~~~~ M:0 C:0
M:2 C:2 ~~~~~~~~ \___/ M:1 C:1
M:3 C:2 \___/ ~~~~~~~~ M:0 C:1
M:3 C:0 ~~~~~~~~ \___/ M:0 C:3
M:3 C:1 \___/ ~~~~~~~~ M:0 C:2
M:1 C:1 ~~~~~~~~ \___/ M:2 C:2
M:2 C:2 \___/ ~~~~~~~~ M:1 C:1
M:0 C:2 ~~~~~~~~ \___/ M:3 C:1
M:0 C:3 \___/ ~~~~~~~~ M:3 C:0
M:0 C:1 ~~~~~~~~ \___/ M:3 C:2
M:1 C:1 \___/ ~~~~~~~~ M:2 C:2
M:0 C:0 ~~~~~~~~ \___/ M:3 C:3

Si quisiéramos todas las soluciones, tampoco sería mucho más complicado, aunque no sé si hay una que se pueda calificar de mejor. ¿Alguien se anima? :). Los comentarios no es el lugar más indicado, así que me podéis mandar un correo con vuestra propuesta.

Así que Prolog no era tan mágico después de todo, aunque si buscamos soluciones en lenguajes más orientados a este tipo de problema, veremos como como sí hay algo de magia ;). Algunos ejemplos:

• Misioneros y caníbales en Prolog, por Antonio Santiago Pérez.
• Misioneros y caníbales en Lisp, por Shantanu.