Una formulación de optimización lineal del problema de las n-reinas

El ajedrez es uno de los juegos de mesa más antiguos y célebres de la historia, con orígenes que se remontan a hace más de mil años. Tradicionalmente se juega sobre un tablero de $8 \times 8$ casillas y combina estrategia, táctica y pensamiento profundo, ya que cada pieza se mueve siguiendo reglas bien definidas. Más allá del propio juego, el tablero de ajedrez y sus piezas han inspirado una gran variedad de rompecabezas lógicos y retos matemáticos.

Uno de los más conocidos es el problema de las ocho reinas, que consiste en colocar ocho reinas sobre un tablero estándar de ajedrez de manera que ninguna amenace a otra. Esto significa que no puede haber dos reinas en la misma fila, columna o diagonal. Este problema ha fascinado durante décadas a matemáticos y aficionados, ya que combina razonamiento combinatorio con una fuerte componente visual y espacial.

El problema también puede generalizarse para tableros de otras dimensiones, $m \times n$, dando lugar a toda una familia de desafíos lógicos de complejidad creciente. Por ejemplo, el tablero que se muestra a continuación representa una posible solución al problema de las ocho reinas. En un tablero estándar de ajedrez existen en total 92 soluciones distintas, lo que convierte a este rompecabezas en un ejercicio especialmente rico e interesante para quienes disfrutan de la lógica, las matemáticas y el ajedrez.

Para modelizar el problema de las reinas como un problema de optimización lineal binaria, es necesario definir primero los distintos elementos que componen el modelo.

Conjuntos de índices

• \(\mathcal{R}\): Filas del tablero.
• \(\mathcal{C}\): Columnas del tablero.

Parámetros

• No hay parámetros adicionales, ya que se considera que el tablero está inicialmente vacío.

Variables de decisión

• \(x_{rc}=1\) si hay una reina situada en la posición $(r,c)$ del tablero, y 0 en caso contrario.

El objetivo del modelo es colocar el máximo número posible de reinas en el tablero sin que se amenacen entre sí.

Función objetivo

• \[\max z = \displaystyle \sum_{r \in \mathcal{R}} \displaystyle \sum_{c \in \mathcal{C}} x_{rc}\]

A continuación, se enumeran las restricciones que garantizan que ninguna reina ataque a otra.

Cada fila puede contener como máximo una reina:

• \[\displaystyle \sum_{r \in \mathcal{R}} x_{rc} \leq 1 \quad \forall c \in \mathcal{C}\]

Cada columna puede contener como máximo una reina:

• \[\displaystyle \sum_{c \in \mathcal{C}} x_{rc} \leq 1 \quad \forall r \in \mathcal{R}\]

Cada diagonal puede contener como máximo una reina:

• \[\displaystyle \sum_{(r,c):\, r-c=k} x_{rc} \leq 1 \quad \forall k = -(|\mathcal{C}|-1),\ldots,(|\mathcal{R}|-1)\]
• \[\displaystyle \sum_{(r,c):\, r+c=k} x_{rc} \leq 1 \quad \forall k = 2,\ldots,|\mathcal{R}|+|\mathcal{C}|\]

Dominio de las variables

• \[x_{rc} \in \{0,1\} \quad \forall r \in \mathcal{R}, c \in \mathcal{C}\]

Notas para el lector:

• Este modelo permite resolver el problema de las $n$ reinas utilizando solvers de programación lineal binaria, como Gurobi.
• Aunque este enfoque es más matemático que la resolución manual del rompecabezas, muestra claramente cómo la modelización en optimización puede abordar de forma sistemática problemas clásicos de lógica y combinatoria.