Construyendo puentes con optimización lineal, el rompecabezas Hashi

Imagen de Kjell-Jostein Sivertsen extraída de Unsplash

El Hashi (abreviación de Hashiwokakero, que significa construir puentes) es un pasatiempo popular de lógica sobre una cuadrícula rectangular con islas representadas por círculos numerados. El objetivo del juego consiste en conectar todas las islas mediante puentes respetando una serie de restricciones formales:

Alineación: Los puentes sólo se pueden trazar de forma horizontal o vertical entre islas alineadas en la misma fila o columna, sin que haya otras islas en el camino.
Capacidad de conexión: Como máximo se pueden construir dos puentes entre cualquier par de islas vecinas.
No intersección: Los puentes no se pueden cruzar entre sí.
Grado fijo: Cada isla debe tener un número total de puentes conectados exactamente igual al número que figura en su interior.
Red única conectada: Todas las islas deben terminar unidas dentro de una única componente conexa (red de transporte continua).

A continuación se muestra un ejemplo de tablero de Hashi compuesto por $52$ islas:

¿Te animas a conectar las islas de forma lógica antes de consultar la solución y la formulación del modelo de optimización?

El pasatiempo Hashi se puede formular como un modelo de optimización lineal entera mixta utilizando un enfoque de flujo de red para asegurar la conectividad completa.

Para estructurar el modelo matemáticamente, representamos las islas como un conjunto de vértices y las conexiones potenciales entre islas adyacentes como aristas.

Conjuntos de índices

$\mathcal{V} = \{1, \dots, N\}$: Conjunto de islas del tablero.

$\mathcal{E} = \{(i,j) : i < j\}$: Conjunto de segmentos válidos (sin islas intermedias) entre islas alineadas horizontal o verticalmente.

$\mathcal{C}$: Conjunto de pares de segmentos perpendiculares que se cruzan en el espacio de la cuadrícula, es decir, $((i,j), (k,l)) \in \mathcal{C}$.

Parámetros

$d_i$: Grado numérico fijado dentro de la isla $i \in \mathcal{V}$.

$N$: Número total de islas ($N = \vert{}\mathcal{V}\vert{}$).

Variables de decisión

$x_{ij} \in \{0, 1, 2\}$: Número de puentes construidos en el segmento $(i,j) \in \mathcal{E}$.

$y_{ij} \in \{0, 1\}$: Variable binaria que vale $1$ si existe al menos un puente entre $i$ y $j$, y $0$ en caso contrario.

$f_{ij} \geqslant 0, \; f_{ji} \geqslant 0$: Flujo auxiliar dirigido que circula entre $i$ y $j$ para garantizar la conectividad de la red.

Al tratarse de un problema de factibilidad matemática, la función de coste es arbitraria:

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

Definimos a continuación las restricciones formales del modelo:

Grado numérico de cada isla:
\[\displaystyle \sum_{j : (i,j) \in \mathcal{E}} x_{ij} + \sum_{j : (j,i) \in \mathcal{E}} x_{ji} = d_i \quad \forall i \in \mathcal{V}\]

Relación entre puentes ($x_{ij}$) e indicador binario de conexión ($y_{ij}$):
\[y_{ij} \leqslant x_{ij} \leqslant 2 y_{ij} \quad \forall (i,j) \in \mathcal{E}\]

Prohibición de cruce entre puentes ortogonales:
\[y_{ij} + y_{kl} \leqslant 1 \quad \forall ((i,j), (k,l)) \in \mathcal{C}\]

Conectividad global de la red (Modelo de Flujo Único):

Fijamos una isla raíz (por ejemplo, la isla $1$). La isla raíz actúa como fuente demandando $N - 1$ unidades de flujo que distribuye hacia las restantes $N - 1$ islas del tablero:
\[\displaystyle \sum_{j : (i,j) \in \mathcal{E}} (f_{ij} - f_{ji}) + \sum_{j : (j,i) \in \mathcal{E}} (f_{ji} - f_{ij}) = \begin{cases} N - 1 & \text{si } i = 1 \\ -1 & \text{si } i \neq 1 \end{cases} \quad \forall i \in \mathcal{V}\] \[f_{ij} + f_{ji} \leqslant (N - 1) y_{ij} \quad \forall (i,j) \in \mathcal{E}\]

Dominio de las variables:
\[x_{ij} \in \{0, 1, 2\} \quad \forall (i,j) \in \mathcal{E}\] \[y_{ij} \in \{0, 1\} \quad \forall (i,j) \in \mathcal{E}\] \[f_{ij}, f_{ji} \geqslant 0 \quad \forall (i,j) \in \mathcal{E}\]

Código fuente

La implementación en Python del modelo de optimización presentado en este post está disponible en el repositorio de GitHub.

Repositorio GitHub: fjmartincampo/Hashi

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

Construyendo puentes con optimización lineal, el rompecabezas Hashi

Solución del reto

Código fuente

Le gustó leer este artículo?