Cómo resolver Sudokus con optimización lineal

Para explicar cómo resolver Sudoku de forma sistemática, podemos usar un modelo de optimización lineal binaria. Primero definimos los elementos del modelo:

Conjuntos de índices

• \(\mathcal{R}\): Filas del tablero.
• \(\mathcal{C}\): Columnas del tablero.
• \(\mathcal{N}\): Números que usamos en el puzzle.

Parámetros

• \(A_{rc}\): Matriz con el tablero inicial (las casillas vacías se ponen iguales a 0).

Variables de decisión

• \(x_{rcn} = 1\) si el número $n$ se coloca en la fila $r$ y columna $c$, y $0$ en caso contrario.

Cada puzzle de Sudoku normalmente tiene una única solución. Por eso, la función objetivo no es importante, basta con minimizar una constante ($L$):

Función objetivo

\[\min z = L\]

Ahora definimos las reglas del Sudoku como restricciones:

Cada casilla debe contener exactamente un número:

\[\displaystyle \sum_{n \in \mathcal{N}} x_{rcn} = 1 \quad \forall r \in \mathcal{R}, c \in \mathcal{C}\]

Cada número aparece una vez por fila:

\[\displaystyle \sum_{r \in \mathcal{R}} x_{rcn} = 1 \quad \forall c \in \mathcal{C}, n \in \mathcal{N}\]

Cada número aparece una vez por columna:

\[\displaystyle \sum_{c \in \mathcal{C}} x_{rcn} = 1 \quad \forall r \in \mathcal{R}, n \in \mathcal{N}\]

Cada número aparece una vez por bloque $3 \times 3$:

\[\displaystyle \sum_{r=3p-2}^{3p} \sum_{c=3q-2}^{3q} x_{rcn} = 1 \quad \forall n \in \mathcal{N}, \; p,q \in \{1,2,3\}\]

Por último, definimos el dominio de las variables:

Dominio de las variables

\[x_{rcn} \in \{0,1\} \quad \forall r \in \mathcal{R}, c \in \mathcal{C}, n \in \mathcal{N}\]

Notas para el lector:

• Con esta formulación, podemos resolver un Sudoku usando optimizadores de programación lineal binaria como Gurobi.
• Aunque es más matemático que los métodos tradicionales, este enfoque muestra cómo el modelado de optimización puede ayudarnos a resolver problemas de lógica de manera sistemática.