Sudoku Killer, el reto del tablero vacío que las matemáticas pueden vencer

Imagen de Mohamed Marey extraída de Unsplash

El Sudoku Killer (o Sudoku Asesino) es una de las variantes más apasionantes y desafiantes del clásico Sudoku. Combina la lógica de ubicación espacial del Sudoku tradicional con la aritmética básica del Kakuro.

A simple vista, el tablero puede parecer intimidante porque no hay ningún número inicial rellenado en la cuadrícula. En su lugar, el tablero está dividido en agrupaciones de celdas o “jaulas”, marcadas con líneas de colores o punteadas, cada una con un pequeño número en su esquina superior izquierda.

El mito dice que se requiere ser un genio matemático para resolver los niveles más avanzados de cabeza, pero la realidad es que el Sudoku Killer no requiere habilidades sobrenaturales, sino razonamiento lógico deductivo, estructuración de datos y conocer la regla del 45 (la suma de los números del 1 al 9 siempre es 45).

Descripción formal del problema

El objetivo del Sudoku Killer es el mismo que en un Sudoku regular: rellenar cada fila, columna y región de 3x3 una vez con los números del 1 al 9. La diferencia radica en cómo se llega a deducir esos números.

Las reglas específicas del Sudoku Killer son las siguientes:

Debes rellenar todas las filas, columnas y regiones de 3x3 con números del 1 al 9, igual que en un Sudoku normal.
Cada celda es parte de una jaula (cage), que se indica mediante bordes de distintos colores o líneas punteadas.
La suma de los números dentro de cada jaula debe ser igual al valor indicado en la esquina superior de la misma.
Los números no se pueden repetir dentro de una misma jaula.
Los números no se pueden repetir dentro de una misma fila, columna o región de 3x3.

Para poder llegar a la solución correcta disponemos del siguiente tablero inicial:

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

Este problema se puede plantear como un modelo de optimización lineal binaria. ¿Te atreves a intentarlo?

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

Conjuntos de índices

\(\mathcal{I} = \{1, 2, \dots, 9\}\): Conjunto de filas.

\(\mathcal{J} = \{1, 2, \dots, 9\}\): Conjunto de columnas.

\(\mathcal{K} = \{1, 2, \dots, 9\}\): Conjunto de valores numéricos que puede tomar una celda.

\(\mathcal{B} = \{1, 2, \dots, 9\}\): Conjunto de bloques o regiones 3x3. Las celdas \((i,j)\) del bloque \(b\) pertenecen al subconjunto \(R_b\).

\(\mathcal{C}\): Conjunto de jaulas (cages).

\(\mathcal{S}_c\): Conjunto de celdas \((i,j)\) que pertenecen a la jaula \(c \in \mathcal{C}\).

\(V_c\): Valor objetivo (suma) de la jaula \(c \in \mathcal{C}\).

Variables de decisión

\(x_{ijk} = 1\) si la celda de la fila \(i \in \mathcal{I}\) y columna \(j \in \mathcal{J}\) toma el valor numérico \(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 simplemente una constante.

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

Ahora definimos las reglas del Sudoku Clásico y las propias de la variante Killer como restricciones lineales:

Cada celda debe contener exactamente un valor numérico:
\[\displaystyle \sum_{k \in \mathcal{K}} x_{ijk} = 1 \quad \forall i \in \mathcal{I}, \; j \in \mathcal{J}\]

Cada valor debe aparecer exactamente una vez por fila:
\[\displaystyle \sum_{j \in \mathcal{J}} x_{ijk} = 1 \quad \forall i \in \mathcal{I}, \; k \in \mathcal{K}\]

Cada valor debe aparecer exactamente una vez por columna:
\[\displaystyle \sum_{i \in \mathcal{I}} x_{ijk} = 1 \quad \forall j \in \mathcal{J}, \; k \in \mathcal{K}\]

Cada valor debe aparecer exactamente una vez por bloque 3x3:
\[\displaystyle \sum_{(i,j) \in R_b} x_{ijk} = 1 \quad \forall b \in \mathcal{B}, \; k \in \mathcal{K}\]

La suma de los valores de las celdas en cada jaula debe ser igual a su valor objetivo:
\[\displaystyle \sum_{(i,j) \in \mathcal{S}_c} \sum_{k \in \mathcal{K}} k \cdot x_{ijk} = V_c \quad \forall c \in \mathcal{C}\]

Los números no se pueden repetir dentro de una misma jaula (aunque esto muchas veces se deduce por las reglas del sudoku clásico si la jaula es pequeña, es estrictamente parte de las reglas del Killer):
\[\displaystyle \sum_{(i,j) \in \mathcal{S}_c} x_{ijk} \leqslant 1 \quad \forall c \in \mathcal{C}, \; k \in \mathcal{K}\]

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

Código fuente

La implementación en Python del modelo de optimización (utilizando librerías como Gurobipy o PuLP) para este post está disponible en el repositorio de GitHub.

Repositorio GitHub: fjmartincampo/SudokuKiller

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

Sudoku Killer, el reto del tablero vacío que las matemáticas pueden vencer

Descripción formal del problema

Solución del reto

Código fuente

Le gustó leer este artículo?