Dominosa, más allá del dominó

Imagen de Mick Haupt extraída de Unsplash

Dominosa es un fascinante juego de lógica ideado por O.S. Adler a finales del siglo XIX. Aunque la idea de colocar fichas de dominó sobre un tablero puede parecer sencilla a primera vista, reconstruir la disposición original de un conjunto completo de dominós a partir de una cuadrícula de números al descubierto supone un auténtico desafío combinatorio.

El objetivo consiste en cubrir un tablero rectangular compuesto por $R \times C$ casillas numeradas utilizando un juego completo de fichas de dominó (desde el doble cero $[0,0]$ hasta el doble $M$, $[M,M]$), de forma que cada casilla quede cubierta por exactamente la mitad de una ficha cuyos valores coincidan con los números del tablero.

Descripción formal del problema

Dado un conjunto completo de fichas de dominó hasta un valor máximo $M$ (que contiene $N_d = \frac{(M+1)(M+2)}{2}$ fichas) y una cuadrícula de números $R \times C$ con $R \times C = 2 \cdot N_d = (M+1)(M+2)$ casillas, debemos colocar todas las fichas respetando las siguientes reglas:

Uso de fichas únicas: Cada ficha del conjunto completo $[u, v]$ (con $0 \leqslant u \leqslant v \leqslant M$) debe emplearse exactamente una vez.
Cobertura completa y sin solapamientos: Cada casilla del tablero debe estar cubierta por la mitad de una única ficha de dominó, sin dejar huecos ni sobreponer fichas.
Adyacencia física: Una ficha de dominó ocupa exactamente dos casillas adyacentes en el tablero, ya sea en orientación horizontal o vertical.
Coincidencia de valores: Los dos números de la ficha de dominó colocada sobre un par de celdas adyacentes deben ser idénticos a los valores impresos en dichas casillas.

La pregunta decisiva que debemos responder es: ¿Existe una colocación válida del conjunto completo de dominós que cubra perfectamente el tablero y cómo podemos encontrarla automáticamente?

Puedes considerar el siguiente ejemplo (con fichas del 0 al 9 en un tablero de $10 \times 11$):

¿Te animas a resolverlo de forma lógica antes de enfrentarte a su modelización?

Este juego de lógica se puede formular de manera elegante y sistemática como un problema de Optimización Lineal binaria. ¿Te atreves a intentarlo?

Para modelar Dominosa como un problema de optimización lineal binaria, identificamos todas las posibles posiciones donde se podría colocar una ficha (aristas adyacentes del tablero) y relacionamos cada posición con la ficha de dominó correspondiente según los valores de sus casillas.

Conjuntos de índices

$\mathcal{I} = \{1, 2, \dots, R\}$: Filas del tablero.

$\mathcal{J} = \{1, 2, \dots, C\}$: Columnas del tablero.

$\mathcal{M} = \{0, 1, \dots, M\}$: Valores numéricos posibles de las fichas de dominó.

$\mathcal{D} = \{[u, v] \in \mathcal{M} \times \mathcal{M} : u \leqslant v\}$: Conjunto de fichas del juego completo de dominó (evitando duplicados por simetría).

$\mathcal{E} = \{ ((i,j), (r,c)) \in (\mathcal{I} \times \mathcal{J})^2 : |i-r| + |j-c| = 1, \; (i,j) < (r,c) \}$: Conjunto de pares ordenados de celdas adyacentes en el tablero, con orden lexicográfico $(i,j) < (r,c) \iff i < r \lor (i = r \land j < c)$.

$\mathcal{E}_{uv} = \{ ((i,j), (r,c)) \in \mathcal{E} : \{V_{ij}, V_{rc}\} = \{u, v\} \}$: Conjunto de posiciones del tablero cuyos valores numéricos coinciden con la ficha $[u,v]$.

Parámetros

$V_{ij} \in \mathcal{M}$: Número impreso en la casilla $(i,j)$ del tablero.

$R, C$: Número de filas y columnas del tablero, donde $R \times C = 2 \cdot N_d = (M+1)(M+2)$.

Variables de decisión

$x_{ijrc} = 1$ si se coloca una ficha de dominó en la arista adyacente $((i,j), (r,c)) \in \mathcal{E}$, y $0$ en caso contrario.

Dado que se trata de un problema de factibilidad (encontrar cualquier configuración que cumpla todas las reglas del juego), la función objetivo es arbitraria:

Función objetivo
\[\min z = 0\]

Definimos las reglas de Dominosa como restricciones lineales:

Cobertura exacta por casilla:

Cada casilla $(i,j)$ del tablero debe ser cubierta por exactamente una ficha de dominó (sumando las aristas donde la casilla es el primer o el segundo extremo del par ordenado):
\[\sum_{(r,c) : ((i,j),(r,c)) \in \mathcal{E}} x_{ijrc} + \sum_{(r,c) : ((r,c),(i,j)) \in \mathcal{E}} x_{rcij} = 1 \quad \forall i \in \mathcal{I}, \; \forall j \in \mathcal{J}\]

Uso único de cada ficha de dominó:

Cada ficha del conjunto completo $[u,v] \in \mathcal{D}$ debe colocarse en exactamente una de las posiciones válidas del tablero donde coinciden sus números:
\[\sum_{((i,j), (r,c)) \in \mathcal{E}_{uv}} x_{ijrc} = 1 \quad \forall [u,v] \in \mathcal{D}\]

Dominio de las variables
\[x_{ijrc} \in \{0, 1\} \quad \forall ((i,j), (r,c)) \in \mathcal{E}\]

Código fuente

La implementación en Python utilizando la librería Gurobipy para resolver este problema de optimización se encuentra disponible en el repositorio de GitHub.

Repositorio GitHub: fjmartincampo/Dominosa

¿Quieres seguir explorando el mundo de la Investigación Operativa? Descubre más posts sobre el tema aquí.

Descripción formal del problema

Solución del reto

Código fuente

Le gustó leer este artículo?