La armonía de los dígitos resolviendo el Kakuro

Imagen de Mohamed Marey extraída de Unsplash

El Kakuro (conocido popularmente como el crucigrama numérico) es uno de los pasatiempos lógicos más populares del mundo. Combina la colocación espacial propia del Sudoku con la combinatoria aritmética del Kakuro clásico.

A diferencia del Sudoku convencional, donde el objetivo se centra en permutaciones de dígitos, el Kakuro requiere analizar combinaciones numéricas que sumen una cantidad exacta sin repetir ningún dígito en la misma fila o columna.

A pesar de su aparente complejidad matemática, el juego no requiere habilidades sobrehumanas, sino razonamiento lógico deductivo, estructuración de datos y combinatoria básica.

Descripción formal del problema

El juego se desarrolla en una cuadrícula compuesta por celdas blancas (vacías), celdas negras (bloqueadas) y celdas de color (con pistas):

Debes rellenar cada celda blanca con un único dígito del 1 al 9 inclusive.
Cada bloque continuado de celdas blancas (horizontal o vertical) tiene asociada una pista de suma ubicada en la celda de color inmediatamente a su izquierda o superior.
La suma de los números de cada bloque debe ser exactamente igual a la pista asignada.
No se puede repetir ningún dígito dentro del mismo bloque continuado de celdas blancas.

Para determinar la asignación correcta, disponemos del siguiente tablero inicial:

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

El acertijo se puede plantear como un modelo de optimización lineal binaria, ¿te atreves a intentarlo?

Para resolver el Kakuro de forma sistemática y automática, podemos formularlo como un modelo de optimización lineal binaria.

Conjuntos de índices

\(\mathcal{R}\): Conjunto de filas.

\(\mathcal{C}\): Conjunto de columnas.

\(\mathcal{W} \subset \mathcal{R} \times \mathcal{C}\): Conjunto de celdas blancas.

\(\mathcal{K} = \{1, 2, \dots, 9\}\): Conjunto de valores numéricos posibles.

\(\mathcal{H}\): Conjunto de bloques horizontales. Para cada \(h \in \mathcal{H}\), \(\mathcal{S}_h \subset \mathcal{W}\) es el conjunto de sus celdas.

\(\mathcal{V}\): Conjunto de bloques verticales. Para cada \(v \in \mathcal{V}\), \(\mathcal{S}_v \subset \mathcal{W}\) es el conjunto de sus celdas.

Parámetros

\(V_h\) suma de los valores de las celdas en la fila \(h \in \mathcal{H}\).

\(V_v\) suma de los valores de las celdas en la columna \(v \in \mathcal{V}\).

Variables de decisión

\(x_{rck} = 1\) si la celda blanca \((r,c) \in \mathcal{W}\) toma el dígito \(k \in \mathcal{K}\), y \(0\) en caso contrario.

Dado que estamos resolviendo un problema de factibilidad lógica, la función objetivo puede ser una constante.

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

Ahora definimos las reglas del Kakuro como restricciones lineales:

Cada celda blanca debe contener exactamente un dígito:
\[\displaystyle \sum_{k \in \mathcal{K}} x_{rck} = 1 \quad \forall (r,c) \in \mathcal{W}\]

Cumplimiento de las sumas en bloques horizontales:
\[\displaystyle \sum_{(r,c) \in \mathcal{S}_h} \sum_{k \in \mathcal{K}} k x_{rck} = V_h \quad \forall h \in \mathcal{H}\]

Unicidad de dígitos en bloques horizontales:
\[\displaystyle \sum_{(r,c) \in \mathcal{S}_h} x_{rck} \leqslant 1 \quad \forall h \in \mathcal{H}, \; k \in \mathcal{K}\]

Cumplimiento de las sumas en bloques verticales:
\[\displaystyle \sum_{(r,c) \in \mathcal{S}_v} \sum_{k \in \mathcal{K}} k x_{rck} = V_v \quad \forall v \in \mathcal{V}\]

Unicidad de dígitos en bloques verticales:
\[\displaystyle \sum_{(r,c) \in \mathcal{S}_v} x_{rck} \leqslant 1 \quad \forall v \in \mathcal{V}, \; k \in \mathcal{K}\]

Dominio de las variables
\[x_{rck} \in \{0, 1\} \quad \forall (r,c) \in \mathcal{W}, \; \forall k \in \mathcal{K}\]

Código fuente

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

Repositorio GitHub: fjmartincampo/Kakuro

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

La armonía de los dígitos resolviendo el Kakuro

Descripción formal del problema

Solución del reto

Código fuente

Le gustó leer este artículo?