Cómo resolver Sudokus con optimización lineal

El Sudoku es un juego de lógica con números que se juega en un tablero de $9 \times 9$, dividido en nueve bloques de $3 \times 3$. El objetivo consiste en rellenar el tablero con los números del $1$ al $9$ de manera que cada número aparezca una sola vez en cada fila, columna y bloque.

La versión moderna del Sudoku se popularizó en los años 80 gracias a la empresa japonesa Nikoli, aunque su origen se remonta a un juego llamado “Number Place”, publicado en Estados Unidos en 1979. Curiosamente, “Sudoku” viene de la frase japonesa “Sūji wa dokushin ni kagiru”, que significa “los números deben ser únicos”. Desde entonces, el Sudoku se ha convertido en un fenómeno mundial, apareciendo en periódicos, libros y aplicaciones de dispositivos móviles, y es disfrutado por millones por su combinación de lógica, reconocimiento de patrones y resolución de problemas.

Un puzzle de Sudoku empieza con algunas casillas ya rellenas. El jugador debe deducir los números restantes usando razonamiento lógico, no adivinando. Por ejemplo, mira este Sudoku:

Podría ser resuelto de este modo:

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.