El paseo perfecto del caballo, desafía al ajedrez con optimización lineal

Imagen de servet photograph extraída de Unsplash

El recorrido del caballo (Knight’s Tour) es un clásico problema matemático y de ajedrez que consiste en mover un caballo sobre un tablero de $n \times n$ casillas de forma que visite todas y cada una de las casillas exactamente una vez.

Existen dos variantes principales de este problema:

Recorrido cerrado: El caballo termina en una casilla que se encuentra a un movimiento de distancia de la casilla inicial, formando un ciclo completo que podría repetirse indefinidamente.
Recorrido abierto: El caballo visita todas las casillas pero la casilla final no permite regresar a la casilla de origen en un sólo movimiento.

Este problema ha fascinado a matemáticos durante siglos, desde el célebre Leonhard Euler en el siglo XVIII hasta la investigación moderna en teoría de grafos e Investigación Operativa.

¿Te atreves a encontrar un camino cerrado completo antes de consultar la solución y su modelización?

El recorrido del caballo se puede formular como un Problema del Viajante sobre un grafo dirigido, ¿te atreves a intentarlo?

Para resolver el recorrido del caballo de forma sistemática, podemos utilizar un modelo de optimización lineal entera basado en la formulación de eliminación de subtours de Miller-Tucker-Zemlin (Miller et al., 1960).

Conjuntos de índices

$\mathcal{V} = \{1, 2, \dots, N\}$: Conjunto de $N = n^2$ casillas del tablero ($N = 64$ para un tablero de $8 \times 8$).

$\mathcal{A} \subset \mathcal{V} \times \mathcal{V}$: Conjunto de arcos dirigidos $(i,j)$ que representan movimientos válidos de caballo entre la casilla $i$ y la casilla $j$.

Parámetros

$N$: Número total de casillas del tablero ($N = 64$).

Variables de decisión

$x_{ij} = 1$ si el caballo se desplaza directamente desde la casilla $i \in \mathcal{V}$ hasta la casilla $j \in \mathcal{V}$, y $0$ en caso contrario.

$u_i \in \{1, \dots, N\}$: Variable continua auxiliar que indica el orden de visita de la casilla $i \in \mathcal{V}$ en la secuencia del recorrido.

Dado que se trata de un problema de factibilidad (encontrar un ciclo hamiltoniano en el grafo de movimientos del caballo), la función objetivo es arbitraria:

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

Ahora definimos las restricciones del modelo:

Exactamente un movimiento de salida por cada casilla:
\[\displaystyle \sum_{j : (i,j) \in \mathcal{A}} x_{ij} = 1 \quad \forall i \in \mathcal{V}\]

Exactamente un movimiento de entrada por cada casilla:
\[\displaystyle \sum_{i : (i,j) \in \mathcal{A}} x_{ij} = 1 \quad \forall j \in \mathcal{V}\]

Eliminación de subtours (Formulación MTZ):
\[u_i - u_j + N x_{ij} \leqslant N - 1 \quad \forall (i,j) \in \mathcal{A}, \; i \neq 1, \; j \neq 1\]

Dominio de las variables:
\[u_1 = 1\] \[1 \leqslant u_i \leqslant N \quad \forall i \in \mathcal{V}\] \[x_{ij} \in \{0,1\} \quad \forall (i,j) \in \mathcal{A}\]

Código fuente

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

Repositorio GitHub: fjmartincampo/KnightsTour

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

El paseo perfecto del caballo, desafía al ajedrez con optimización lineal

Solución del reto

Código fuente

Referencias

Le gustó leer este artículo?