Usando operaciones matriciales para resolver el acertijo de Einstein. Parte I.

Existen en Internet varios rompecabezas lógicos donde la información debe ser colocada en una rejilla de datos, pero indudablemente, uno de los más populares es el conocido acertijo de Einstein. Aunque se le atribuye a Einstein, no hay evidencia que respalde esta afirmación. Se dice que solo el 2% de la población mundial puede resolverlo, pero en realidad no es tan difícil, todo lo que se necesita es lógica y deducción. En este artículo presentaremos un método basado completamente en operaciones matriciales para resolver este acertijo y cualquier otro similar.

El acertijo

Tenemos 5 casas de 5 colores diferentes alineadas 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. La pregunta es: ¿Quién es el dueño del pececito?

Pistas:

1. El británico vive en la casa roja.
2. El sueco tiene un perro.
3. El danés toma té.
4. El noruego vive en la primera casa.
5. El alemán fuma Prince.
6. La casa verde está a la izquierda de la blanca.
7. El dueño de la casa verde toma café.
8. La persona que fuma Pall Mall tiene un pájaro.
9. El dueño de la casa amarilla fuma Dunhill.
10. El que vive en la casa del centro toma leche.
11. La persona que fuma Blend vive junto a la que tiene un gato.
12. La persona que tiene un caballo vive junto a la que fuma Dunhill.
13. El que fuma Bluemaster bebe cerveza.
14. El que fuma Blend tiene un vecino que toma agua.
15. El noruego vive junto a la casa azul.

Formulación matricial

Este problema puede ser formulado en términos de matrices, donde el objetivo es completar una matriz utilizando las pistas que se proveen.

Para este problema en particular la matriz inicial es la siguiente:

Donde la posición de las casas se puede fijar.

Cada pista puede ser también expresada por medio de una matriz, donde la cantidad de columnas es igual a la cantidad de columnas de la matriz inicial. Los valores que no conocen se dejan en blanco. Por ejemplo, las pistas 1 y 2 pueden ser expresadas como:

1

2

La pista 6 involucra dos filas:

6

Y la pista 11 es más compleja, porque involucra dos opciones. Como la pista expresa que la persona que fuma Blend vive junto a la que tiene un gato, no se define si la persona que fuma Blend vive antes o después de la persona que tiene un gato, por lo tanto necesitamos considerar ambas opciones.

11

Operaciones matriciales

Como estamos tratando con matrices cuyos valores son cadenas de caracteres, no tiene sentido hablar de operaciones numéricas, sino algún tipo de operaciones que permitan operar con cualquier tipo de valor. La solución que proponemos necesita definir tres operaciones, donde los operandos son matrices con igual cantidad de columnas, y el resultado es, en dos casos un valor booleano (verdadero o falso), y en el tercer caso una matriz con igual cantidad de columnas que los operandos.

1. Tiene un valor común: Este es un operador sencillo que chequea si dos matrices tienen un valor común (distinto del valor en blanco) en la misma posición de la columna, sin importar la fila.

2. Pueden ser fusionadas: Este es un operador booleano que devuelve verdadero, si ambas matrices pueden ser fusionadas, utilizando el valor común encontrado mediante el uso del operador anterior como punto de fusión. Este operador debe retornar falso si existen dos celdas no vacías con diferentes valores que se solapan, o el proceso de fusión requiere que se adicionen nuevas filas cuando no tiene sentido que la matriz crezca.

3. Fusionar: Este operador simplemente fusiona dos matrices utilizando una celda común como punto de fusión, adicionado nuevas filas de ser necesario.

En la próxima parte, hablaremos sobre el algoritmo para resolver este acertijo utilizando estas operaciones matriciales, y presentaremos una implementación en JavaScript para resolver este acertijo y cualquier otro similar.