De pequeño me encantaban los pasatiempos de lógica. Creo que la «culpa» es de mi abuelo, que fue quien me introdujo en el mundo de los pasatiempos. Él era un gran aficionado a los autodefinidos, pero mis favoritos siempre fueron los típicos juegos de lógica:

Por eso cuando Luis Souto enlazó en twitter el Acertijo de Einstein me pareció una buena oportunidad para pasar un rato entretenido, pero sobre todo, para jugar un poco con programación basada en restricciones.

Hace unas semanas escribí sobre la Programación Basada en Restricciones (Constraint Programming), que es un paradigma que nos permite resolver un problema de forma declarativa, definiendo las variables que lo componen y las restricciones entre las mismas, y dejando que sea el sistema el que halle soluciones que cumplan esas restricciones.

Una de las partes complicadas de todo esto es encontrar la forma de modelar el problema, así que vamos a aprovechar el Acertijo de Einstein para practicar un poco y ver un ejemplo algo más complejo que el de las 8 reinas que vimos en el post anterior.

El Acertijo de Einstein

El puzzle que vamos a resolver se conoce como Puzzle de la Cebra o Acertijo de Einstein y la versión que usaremos es la siguiente:

1. Hay 5 casas colocadas una al lado de la otra.
2. La casa del inglés es roja.
3. El español tiene un perro.
4. El japonés es detective.
5. El francés bebe té.
6. La casa blanca está inmediatamente a la derecha de la casa verde.
7. En la casa del medio se bebe leche.
8. La casa del noruego es la primera de la izquierda.
9. La casa vecina al noruego es azul.
10. La casa amarilla es del médico.
11. El vecino del médico tiene un caballo.
12. El vecino del inglés es arquitecto.
13. El vecino del arquitecto tiene un zorro.
14. El abogado bebe zumo de tomate.
15. El ingeniero tiene un gato.
16. En la casa verde se bebe café.

El objetivo, como os podéis imaginar, es averiguar de qué color es cada casa, de qué nacionalidad es su propietario, qué bebe y qué animal es su mascota.

Modelando el problema

Para modelar el problema voy a utilizar loco, una librería para utilizar programación basada en restricciones con clojure, pero en realidad las ideas serían aplicables a cualquier otro lenguaje o librería.

Lo primero es definir las variables sobre las que vamos a trabajar.

Para cada casa tendremos que definir el color, el país del dueño, la bebida y el animal. Pero además, viendo el enunciado, queda claro que la posición de las casas importa porque tenemos pistas de la forma el vecino del…. Por tanto, numeraremos las casas de la 0 a la 4, considerando que la 0 es la casa de la izquierda y la 4 la de la derecha.

Para crear las restricciones necesitamos trabajar con valores numéricos (al menos en loco, no sé en otras librerías), por lo que habrá que traducir los datos del puzzle (rojo, té, noruego, etc.) a valores numéricos para crear las restricciones. Eso nos lleva a que una vez hecha la traducción cada variable podrá tomar valores entre 0 y 4.

Si no queremos volvernos locos, podemos definir una estructura que nos permita traducir entre nombres y valores numéricos:

(def domain
  {:color [:red :blue :green :yellow :white]
   :country [:england :spain :france :norway :japan]
   :beverage [:tea :milk :tomato :coffee :beer]
   :animal [:dog :horse :fox :cat :zebra]
   :job [:detective :doctor :architect :lawyer :engineer]})

;; Convierte algo como [:job :lawyer] en su valor numérico (3)
(defn to-val [prop name]
  (.indexOf (domain prop) name))

;; Convierte un valor numérico en su nombre [:job 1] => :doctor
(defn to-name [[prop value]]
  (get-in domain [prop value]))

Con todas esas piezas ya podemos definir las variables en loco:

(def vars (for [prop (keys domain)
                idx (range 5)]
            ($in [prop idx] (range 5)))

;; ([:color 0] [:color 1] ... [:color 4]
;;  [:country 0] ...       [:country 4]
;;  ...
;;  [:job 0]                [:job 4])

Como todas las casas deben tener valores distintos para cada propiedad (color, país, etc.), resulta útil definir una función que nos ayude a expresarlo:

(defn all-distinct [prop]
  ($distinct (map (partial vector prop) (range 5))))

;; Para indicar que todos los colores son distintos:
;; (all-distinct :color)

Hasta aquí hemos visto una forma relativamente sencilla de modelar variables, datos y restricciones básicas (que sean todos distintos), pero nos queda la parte divertida: modelar las restricciones más complicadas.

Si analizamos las pistas del enunciado del problema, vemos que en realidad podemos clasificarlas en 4 tipos.

El primer tipo son las pistas que fijan una variable a un valor concreto, por ejemplo la casa del noruego es la primera de la izquierda o en la casa del medio se bebe leche. Traducido al DSL de loco, habría que escribir algo así:

;; [:country 0] es el país de la casa de la izquierda y 3 es el valor de noruega
($= [:country 0] 3)

Eso es completamente ilegible. Preferiría poder escribir algo así:

;; La casa del noruego es la primera de la izquierda
(fact [:country 0 :normay])

;; En la casa del medio se bebe leche
(fact [:beverage 2 :milk])

Para ello, vamos a crear una función que nos permita definir ese tipo de restricciones de una forma más agradable:

(defn fact [[prop idx name]]
   ($= [prop idx] (to-val prop name)))

El siguiente tipo de pista liga dos propiedades de una misma casa, como la casa roja es del inglés. Hay varias formas de expresar esto con loco, pero la que más me gusta es verlo como que alguna de las casas cumple que es roja y el país del dueño es inglaterra. Es decir:

∃ i : countryi = england ∧ colori = red

Escrito de forma legible, me gustaría poder expresarlo así:

;; La casa del inglés es roja
(fact [:country :england] [:color :red])

;; La casa amarilla es del médico
(fact [:color :yellow] [:job :doctor])

Para lo que podemos emplear un $or entre todas las casas:

(defn fact [[prop1 name1] [prop2 name2]]
   (apply $or (map #($and ($= [prop1 %] (to-val prop1 name1))
                       ($= [prop2 %] (to-val prop2 name2)))
                   (range 5))))

Otro tipo de pista liga dos propiedades pero no de la misma casa, sino de una casa con alguno de sus vecinos, por ejemplo el vecino del inglés es arquitecto. Esto podemos verlo como la mezcla de dos restricciones, o bien se cumple entre una casa y su vecino de la derecha, o bien se cumple entre una casa y su vecino de la izquierda:

∃ i : countryi = england ∧ jobi+1 = architect ∨ countryi = england ∧ jobi-1 = architect

Siguiendo el estilo del mini DSL que nos estamos creado, esto podríamos definirlo así:

;; El vecino del inglés es arquitecto
(side-fact [:country :england] [:job :architect])
   
;; El vecino del arquitecto tiene un zorro
(side-fact [:job :architect] [:animal :fox])

Y la función para hacerlo funcionar sería la siguiente:

(defn side-fact 
  [[prop1 name1] [prop2 name2]]
  (apply $or
         (concat
          (map #($and (fact [prop1 % name1]) (fact [prop2 (inc %) name2])) (range 4))
          (map #($and (fact [prop1 % name1]) (fact [prop2 (dec %) name2])) (range 1 5)))))

Falta un último tipo de pista, la relación entre una propiedad de una casa y la de su vecino de la derecha que aparece en La casa blanca está inmediatamente a la derecha de la casa verde. Es un caso particular del tipo anterior y se resuelve de forma muy parecida por lo que os ahorro la explicación y el código.

Usando las funciones que hemos ido creando, definir y resolver el problema es muy sencillo y hasta legible:

(def model

  (conj

   ;; Variables [:country i] [:animal i] [:color i] [:beverage i] [:job i] con i = [0..4]
   (for [prop (keys domain)
         idx (range 5)]
     ($in [prop idx] (range 5)))

   ;; Todas las variables de cada propiedad deben ser diferentes
   (all-distinct :color)
   (all-distinct :animal)
   (all-distinct :beverage)
   (all-distinct :country)
   (all-distinct :job)

   ;; La casa del inglés es roja
   (fact [:country :england] [:color :red])
   
   ;; El español tiene un perro
   (fact [:country :spain] [:animal :dog])
   
   ;; El japonés es detective
   (fact [:job :detective] [:country :japan])
   
   ;; El francés bebe té
   (fact [:country :france] [:beverage :tea])
   
   ;; La casa blanca está inmediatamente a la derecha de la casa verde
   (right-fact [:color :green] [:color :white])
   
   ;; En la casa del medio se bebe leche
   (fact [:beverage 2 :milk])
   
   ;; La casa del noruego es la primera a la izquierda
   (fact [:country 0 :norway])
   
   ;; La casa vecina al noruego es azul
   (side-fact [:country :norway] [:color :blue])
   
   ;; La casa amarilla es del médico
   (fact [:color :yellow] [:job :doctor])
   
   ;; El vecino del médico tiene un caballo
   (side-fact [:job :doctor] [:animal :horse])
   
   ;; El vecino del inglés es arquitecto
   (side-fact [:country :england] [:job :architect])
   
   ;; El vecino del arquitecto tiene un zorro
   (side-fact [:job :architect] [:animal :fox])
   
   ;; El abogado bebe zumo de tomate
   (fact [:job :lawyer] [:beverage :tomato])
   
   ;; El ingeniero tiene un gato
   (fact [:job :engineer] [:animal :cat])
   
   ;; En la casa verde se bebe café
   (fact [:color :green] [:beverage :coffee])))

(def sol (solution (model))

El código completo incluye algun detalle para formatear la solución, pero básicamente es lo que hemos visto en este post.

Resumen

Además de como divertimento, me ha gustado resolver el problema para intentar entender mejor cómo modelar problemas con programación basada en restricciones.

Aunque no sea algo que vaya a usar a diario, me parece una forma de resolver problemas muy interesante donde la complejidad reside en ser capaz de especificar el problema a base de restricciones y ver que, pensando un poco, es posible modelar cosas a priori bastante alejadas de los típicos ejemplos de álgebra lineal que he encontrado por ahí me ha parecido curioso.