jueves, 27 de junio de 2013

Resolución de problemas con restricciones: el acertijo de Einstein

En esta entrada del blog nos proponemos resolver un acertijo atribuido a Alfred Einstein, quien afirmaba que 98% de la población mundial no sería capaz de resolverlo.  El acertijo reza así:

Tenemos 5 casas de cinco colores diferentes y en cada una de ellas vive una persona de una nacionalidad diferente. Cada uno de los dueños bebe una bebida diferente, fuma una marca de cigarrillos diferente y tiene una mascota diferente.

Tenemos las siguientes condiciones:

  • El británico vive en la casa roja.
  • El sueco tiene un perro.
  • El danés toma té.
  • La casa verde esta a la izquierda de la blanca.
  • El dueño de la casa verde toma café.
  • La persona que fuma Pall Mall tiene un pájaro.
  • El dueño de la casa amarilla fuma Dunhill.
  • El que vive en la casa del centro toma leche.
  • El noruego vive en la primera casa.
  • La persona que fuma Blends vive junto a la que tiene un gato.
  • La persona que tiene un caballo vive junto a la que fuma Dunhill.
  • El que fuma Bluemasters bebe cerveza.
  • El alemán fuma prince.
  • El noruego vive junto a la casa azul.
  • El que fuma Blends tiene un vecino que toma agua.

Y por ultimo la pregunta:

¿Quién es el dueño del pez?
Podemos abordar este problema planteando un sistema de 25 variables (los 5 colores de casa, las 5 nacionalidades, las 5 bebidas, etc.).  Cada variable asume un valor entero entre 1 y 5, indicando el número de casa con ese color, ocupante de determinada nacionalidad, etc.  Si no hay restricciones, se tienen 5^25=2,980232239×10¹⁷ soluciones posibles.  Bajo las condiciones según las cuales cada casa tiene un ocupante de nacionalidad distinta, con un color distinto, que toma una bebida distinta, con una mascota distinta y que fuma una marca de cigarrillo distinta se reduce el universo de posibles soluciones a (5!)^5=24.883.200.000, lo cual sigue siendo un tamaño de espacio de búsqueda considerable.  El resto de las restricciones presuntamente reducen el universo de posibles soluciones a una única solución. Se trata pues de un problema de búsqueda combinatoria.

Solución del acertijo de Einstein en Python


En mis intentos por resolver esto "a mano" y a fuerza de lógica, me preguntaba si sería posible escribir un programa para resolver esto de forma automática, mediante el computador.  Me acordé del lenguaje Prolog, el cual está específicamente diseñado para realizar cómputos con símbolos y relaciones entre símbolos. Sin embargo, pensaba que sin duda sería posible realizar este trabajo en Python.  Fue así como me enteré de un módulo llamado "constraints" para resolver problemas con restricciones en Python.  Seguidamente les expongo el código fuente del script que resuelve el acertijo de Einstein:

from constraint import *

acertijo = Problem()

#Funciones relacionales

def a_la_izquierda_de(a,b):
    return a < b
def a_la_derecha_de(a,b):
    return not left_of(a,b)
def vecino_de(a,b):
    return abs(a - b) == 1

#Variables

color = ["blanca","roja","verde","amarilla","azul"]
nacionalidad = ["Danes","Sueco","Britanico","Noruego","Aleman"]
bebida = ["te","cafe","cerveza","agua","leche"]
fuma = ["Dunhill","Pall_mall","Bluemaster","Blends","Prince"]
mascota = ["caballo","pez","pajaro","perro","gato"]
variables = color+nacionalidad+bebida+fuma+mascota
#Dominio de las variables
casa = [1,2,3,4,5]
#Agregar las variables al objeto "acertijo"
acertijo.addVariables(variables, casa)

#Cada vecino tiene casas de colores distintos, toma una bebida distinta,
#fuma una marca de cirgarrillo distinto, tiene mascotas diferentes y
#es de nacionalidad distinta.

for i in (color, nacionalidad, bebida, fuma, mascota):
    acertijo.addConstraint(AllDifferentConstraint(),i)
#El britanico vive en la casa roja
acertijo.addConstraint(lambda Britanico, roja: Britanico == roja,\
    ("Britanico", "roja"))
#El sueco tiene el perro
acertijo.addConstraint(lambda Sueco, perro: Sueco == perro,\
    ("Sueco", "perro"))
#El danés bebe té
acertijo.addConstraint(lambda Danes, te: Danes == te, ("Danes", "te"))
#La casa verde está a la izquierda de la casa blanca
acertijo.addConstraint(lambda verde, blanca: vecino_de(verde, blanca) \
    and a_la_izquierda_de(verde, blanca),("verde", "blanca"))
#El dueño de la casa verde toma café
acertijo.addConstraint(lambda verde, cafe: verde == cafe, \
    ("verde", "cafe"))
#La persona que fuma Pall Mall tiene un pájaro
acertijo.addConstraint(lambda Pall_mall, pajaro: Pall_mall == pajaro, \
    ("Pall_mall", "pajaro"))
#El dueño de la casa amarilla fuma Dunhill                  
acertijo.addConstraint(lambda amarillo, Dunhill: amarillo == Dunhill, \
    ("amarilla", "Dunhill"))
#El de la casa del centro (casa N° 3) toma leche
acertijo.addConstraint(InSetConstraint([3]), ["leche"])
#El Noruego vive en la primera casa
acertijo.addConstraint(InSetConstraint([1]), ["Noruego"])
#La persona que fuma Blends vive junto a la que tiene un gato
acertijo.addConstraint(lambda Blends, gato: vecino_de(Blends, gato),\
    ("Blends", "gato"))
#La persona que tiene un caballo vive junto a la que fuma Dunhill
acertijo.addConstraint(lambda caballo, Dunhill: \
    vecino_de(caballo, Dunhill), ("caballo", "Dunhill"))
#El que fuma Bluemasters bebe cerveza
acertijo.addConstraint(lambda Bluemaster, cerveza: \
    Bluemaster == cerveza, ("Bluemaster", "cerveza"))
#El Aleman fuma Prince
acertijo.addConstraint(lambda Aleman, Prince: Aleman == Prince, \
    ("Aleman","Prince"))
#EL Noruego vive junto a la casa azul
acertijo.addConstraint(lambda Noruego, azul: \
    vecino_de(Noruego, azul), ("Noruego", "azul"))
#El que fuma Blends tiene un vecino que toma agua
acertijo.addConstraint(lambda Blends, agua: \
    vecino_de(Blends, agua), ("Blends", "agua"))

#La respuesta
respuesta = acertijo.getSolution()
print respuesta

#Imprime la solución de una forma más legible
ver_respuesta = {}
for i in casa:
    ver_respuesta[i] = {}

for k,v in respuesta.items():
    if k in color:
        tmp = k
        if k.__len__()<7:
            tmp=tmp+"\t"
        ver_respuesta[v]['color'] = tmp
    elif k in nacionalidad:
        tmp = k
        if k.__len__()<8:
            tmp=tmp+"\t"
        ver_respuesta[v]['nacionalidad'] = tmp
    elif k in bebida:
        ver_respuesta[v]['bebida'] = k
    elif k in fuma:
        tmp = k
        if k.__len__()<9:
            tmp=tmp+"\t"
        ver_respuesta[v]['fuma'] = tmp
    elif k in mascota:
        ver_respuesta[v]['mascota'] = k


print "Respuesta:\n"
print "Casa\tColor\t\tNacionalidad\tBebida\t\tFuma\t\tMascota"
print "="*80
for i in casa:
    print str(i)+"\t"+ver_respuesta[i]['color']+"\t"+\
        ver_respuesta[i]['nacionalidad']+"\t"+ \
        ver_respuesta[i]['bebida']+"\t\t"+ver_respuesta[i]['fuma']+"\t"+\
        ver_respuesta[i]['mascota']


El script produce la solución al acertijo, como se manifiesta en su salida:

{'amarilla': 1, 'Noruego': 1, 'Dunhill': 1, 'Sueco': 5, 'agua': 1, 'Britanico': 3, 'azul': 2, 'verde': 4, 'Bluemaster': 5, 'cerveza': 5, 'leche': 3, 'cafe': 4, 'Pall_mall': 3, 'caballo': 2, 'roja': 3, 'blanca': 5, 'Danes': 2, 'pajaro': 3, 'pez': 4, 'Aleman': 4, 'gato': 1, 'perro': 5, 'te': 2, 'Prince': 4, 'Blends': 2}


Respuesta:

Casa    Color       Nacionalidad    Bebida        Fuma            Mascota
================================================================================
1       amarilla    Noruego         agua          Dunhill         gato
2       azul        Danes           te            Blends          caballo
3       roja        Britanico       leche         Pall_mall       pajaro
4       verde       Aleman          cafe          Prince          pez
5       blanca      Sueco           cerveza       Bluemaster      perro


Donde se puede ver que el alemán, quien vive en una casa verde, toma café y fuma cigarrillos de marca "Prince", es quien tiene al pez como mascota.  Ahora que tengo su atención, permítanme comentarles algo sobre este super-genial módulo de Python.


Primeramente, para su instalación deben descargar el archivo .tar, descomprimirlo y ejecutar el script de setup, para lo cual debe ejecutar lo siguiente en la consola de Linux:

wget http://labix.org/download/python-constraint/python-constraint-1.1.tar.bz2
bzip2 -cd python-constraint-1.1.tar.bz2 | tar xvf -
cd python-constraint-1.1
python setup.py install


Como se puede ver en el script de arriba, este módulo trabaja con una clase llamada "Problem" (problema), que contiene una definición de las variables del problema (en este caso, 25 variables), junto con el dominio (conjunto finito de valores posibles) para cada variable y las restricciones, que se agregan mediante el método addConstraint.  Existen algunas restricciones de uso común definidas en el módulo (consulte la documentación en http://labix.org/doc/constraint/).  Las restricciones del problema también se pueden definir mediante expresiones de cálculo lambda, tal como se especifican en la mayoría de las restricciones del acertijo.

El método getSolution() devuelve un diccionario en el cual las claves son las variables y estan apuntan al número de la casa (1 al 5) asociada a esta variable.  De esta forma, a cada casa se le asocia un color, una nacionalidad del ocupante, una bebida, una marca de cigarrillo y una mascota diferente.  Sin embargo, el diccionario que se devuelve no permite visualizar esto fácilmente, por lo cual seguidamente se recorre para organizar la información por número de casa.  Si un problema tiene más de una solución, el método getSolutions() (con s al final por el plural de soluciones) devuelve una lista de diccionarios, en donde cada diccionario es una de las posibles soluciones.


Posibles aplicaciones del módulo constraints

Si lo examinamos bien, este problema es muy parecido al problema de resolver un Sudoku.  En Sudoku también existen restricciones con respecto a la forma de rellenar cada casilla con un dígito del 1 al 9.  No se pueden repetir dígitos en una fila, columna o subcuadro.  Como reto les planteo escribir un script en Python (usando el módulo constraints)  que resuelva crucigramas de Sudoku.

Si se nos presenta un problema en la vida real en el cual se manejan elementos finitos (discretos) (unidades de transporte, manejo de personal, etc.) que se deben distribuir o alocar de una manera óptima, este módulo podría sernos de utilidad.  Otra posible aplicación de este módulo es en los problemas de programación entera.







No hay comentarios:

Publicar un comentario