Retos fantásticos de ajedrez y matemáticas

El problema de las 8 damas

Este bello problema que les compartiré está basado en los movimientos de la reina en el tablero de ajedrez y es conocido como «problema de las 8 damas». Consiste en ubicar 8 reinas en el tablero de ajedrez sin que se ataquen, siguiendo las reglas del juego, es decir respetando que la reina solo se puede desplazar vertical, horizontal o diagonalmente, tantas casillas como se desee.

El problema fue propuesto por el alemán Max Bezzel y publicado por primera vez en 1848 en la revista alemana especializada en ajedrez «Berliner Schachzeitung».

En realidad, el problema es equivalente al reto de situar 8 fichas en el tablero de 64 casillas (8 filas y 8 columnas), de tal manera que no haya dos en la misma columna, fila o diagonal. A manera de ejemplo, una solución es la siguiente:

Obsérvese que cuando se encuentra una solución, se pueden reconocer otras tres, rotanto el tablero 90, 180 y 270 grados.

El número total de soluciones que tiene este problema, es 92, pero en realidad solo hay 12 soluciones básicas porque las restantes se obtienen a partir de ellas con giros y simetrías. Hay 12 soluciones que dan origen, cada una, a 3 más, usando rotaciones, como ya indicamos, así que por cada solución básica se revelan 4 mediante rotaciones para un total de

12 x 4 = 48.

Ahora bien, solo hay 11 de las 12 soluciones básicas que dan origen a otras 3 mediante simetría o reflexión porque hay una solución básica con simetría central que no origina nuevas soluciones; esa solución es la que muestra la imagen siguiente:

así que, mediante simetría tenemos

11 x 4 = 44,

y el número total de soluciones es entonces

(12 x 4) + (11 x 4) = 48 + 44 = 92.

El problema de las ocho damas fue un reto con el que se entretuvieron los matemáticos a mediados del siglo XIX, el mismo Gauss encontró en una tarde 76 de las 92 soluciones; pero el primero en encontrar todas las soluciones, en 1850, fue el matemático Franz Nauck.

Actualmente el problema de las 8 damas sigue despertando gran interés, ya no solo como entretenimiento para encontrar alguna solución de forma manual. El problema se ha vuelto bastante popular porque resulta ser un excelente referente para enseñar algoritmos y optimización ya que puede resolverse de múltiples maneras y la tarea de encontrar una solución, donde se exploran diferentes combinaciones y se descartan las que no cumplen con las reglas, de manera rápida y sistemática, es una forma muy didáctica y da origen a una técnica computacional de frecuente uso y múltiples aplicaciones, conocida como «backtracking», que se basa en probar y retroceder cuando algo no funciona.

El reto de encontrar todas las soluciones exige además importantes modificaciones y extensiones de un primer algoritmo para la búsqueda de una sola solución; por lo tanto el ejercicio lógico y computacional brinda un ejemplo que obliga a seguir una buena receta que contemple todas las posibilidades y vaya haciendo barridos en todas las casillas. Pero encontrar todas las soluciones al problema puede ser bastante costoso computacionalmente, ya que hay 4.426.165.368 posibles arreglos y solo 92 soluciones, como ya se indicó.

También se ha formulado el problema general para tableros de nxn siendo n un número que representa más de 8 filas y columnas; esta generalización o «problema de las n reinas» se ha convertido en un desafío computacional. Así por ejemplo, para un tablero de 12×12 hay exactamente 1787 soluciones básicas y un total de 14.200 soluciones.

Sea esta la oportunidad para invitarles a entretenerse un rato con este bello problema intentando dar con una solución y creando su propio algoritmo en forma recursiva.

@MantillaIgnacio