Termómetros lógicos, más allá de la temperatura

Imagen de Markus Winkler extraída de Unsplash

El Thermometer Puzzle es un original rompecabezas lógico donde el frío cálculo se encuentra con el diseño espacial. Aquí entran en juego las restricciones de capacidad y continuidad física de los fluidos.

El objetivo consiste en determinar qué celdas de una cuadrícula de $m \times n$ contienen mercurio. La cuadrícula está completamente recubierta por termómetros de distintas formas y longitudes. Cada termómetro ocupa una secuencia de celdas adyacentes (en horizontal o vertical) y tiene una base o “bulbo” claramente identificable.

Descripción formal del problema

Dada una cuadrícula de $m \times n$ celdas agrupadas en distintos termómetros, debemos decidir el nivel de llenado de cada uno respetando las siguientes reglas físicas y lógicas:

Requisitos de fila y columna: Los márgenes de la cuadrícula indican exactamente cuántas celdas deben estar llenas de mercurio en cada fila y en cada columna.
Llenado continuo (Gravedad/Física del termómetro): Los termómetros siempre se llenan desde el bulbo (inicio) hacia el extremo final. Esto implica una condición estricta: si una celda contiene mercurio, todas las celdas anteriores de ese mismo termómetro (más cercanas al bulbo) también deben estar llenas. Del mismo modo, si una celda está vacía, todas las celdas posteriores en ese termómetro deben estar vacías.

Puedes considerar el siguiente ejemplo de un tablero de $8 \times 8$:

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

La magia de este pasatiempo reside en cruzar la información de los totales marginales con la rigidez direccional de los termómetros. ¿Cómo modelamos esta aparente “física de fluidos” matemáticamente? Utilizando la elegancia de la Optimización Lineal binaria.

Para modelar este problema, la clave está en cómo representamos la continuidad del mercurio. En lugar de crear complejas variables numéricas para el nivel de llenado de cada termómetro, podemos simplemente establecer una relación de dependencia lógica entre celdas adyacentes dentro del mismo instrumento.

Conjuntos de índices

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

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

$\mathcal{A} = \{ ((i,j), (r,c)) \in (\mathcal{I} \times \mathcal{J})^2 \}$: Conjunto de pares de celdas ordenadas donde la celda $(i,j)$ es la predecesora inmediata de la celda $(r,c)$ dentro de un mismo termómetro (es decir, $(i,j)$ está un paso más cerca del bulbo que $(r,c)$).

Parámetros

$R_i$: Número exacto de celdas que deben estar llenas en la fila $i \in \mathcal{I}$.

$C_j$: Número exacto de celdas que deben estar llenas en la columna $j \in \mathcal{J}$.

Variables de decisión

$x_{ij} = 1$ si la celda $(i,j)$ se llena de mercurio, y $0$ si se deja vacía.

Este es un problema de factibilidad pura:

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

Las reglas físicas del juego se traducen en las siguientes restricciones lineales:

Totales de fila y columna:

La suma de las celdas llenas en cada fila y en cada columna debe coincidir con los valores dados en los márgenes:
\[\sum_{j \in \mathcal{J}} x_{ij} = R_i \quad \forall i \in \mathcal{I}\] \[\sum_{i \in \mathcal{I}} x_{ij} = C_j \quad \forall j \in \mathcal{J}\]

Continuidad del mercurio (Precedencia):

Si una celda $(r,c)$ tiene mercurio ($x_{rc} = 1$), su celda predecesora $(i,j)$ en el termómetro debe estar obligatoriamente llena ($x_{ij} = 1$). Si la celda predecesora está vacía ($x_{ij} = 0$), la sucesora debe estar vacía ($x_{rc} = 0$). Esta lógica bidireccional se modela con una simple inecuación:
\[x_{rc} \leqslant x_{ij} \quad \forall ((i,j), (r,c)) \in \mathcal{A}\]

Dominio de las variables
\[x_{ij} \in \{0, 1\} \quad \forall i \in \mathcal{I}, \; \forall j \in \mathcal{J}\]

Código fuente

La implementación en Python para resolver este problema (junto con la formulación equivalente en GAMS propuesta como ejercicio) se encuentra disponible en el repositorio de GitHub.

Repositorio GitHub: fjmartincampo/ThermometerPuzzle

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

Termómetros lógicos, más allá de la temperatura

Descripción formal del problema

Solución del reto

Código fuente

Le gustó leer este artículo?