N reinas

El rompecabezas N Queens desafía al jugador a colocar reinas de ajedrez en un tablero de ajedrez NxN para que ninguna dos reinas se amenazan. Ya que una reina puede atacar a lo largo de su fila, columna, y ambas diagonales, no dos reinas pueden compartir la misma fila, columna o diagonal. La versión clásica utiliza una tabla de 8x8 con 8 reinas, pero el rompecabezas se puede jugar en cualquier tablero de tamaño desde 4x4 hacia arriba (no hay solución para 2x2 o 3x3). El número de soluciones diferenciadas crece rápidamente con el tamaño de la junta: el problema de 8 pestañas tiene 92 soluciones (12 únicas al considerar la simetría).

Reglas

1. Lugar N reinas en un tablero de ajedrez NxN.
2. Ninguna dos reinas puede estar en la misma fila.
3. No hay dos reinas en la misma columna.
4. Ninguna dos reinas puede estar en la misma diagonal (ambos direcciones).
5. Todas las reinas N deben ser colocadas simultáneamente a bordo.

Estrategias

• ¿Qué? Coloque una reina por fila, comenzando desde arriba. Esto satisface automáticamente el límite de fila y reduce el problema de elegir una columna para cada fila.
• Seguimiento de Columnos: Realizar un seguimiento de qué columnas ya están ocupadas. Cada nueva reina debe ir en una columna sin usar.
• Rastreo Diagonal: Para las dos direcciones diagonales, las células en el mismo diagonal comparten un valor constante de (row - columna) o (row + columna). Rastrea estos valores para identificar rápidamente cuadrados seguros.
• ¿Qué? Si llegas a una fila donde ninguna columna es segura, vuelve a la fila anterior y prueba la siguiente columna disponible. Este enfoque sistemático garantiza encontrar una solución.
• Explotación de simetría: Las soluciones pueden girarse 90°, 180°, 270° y reflejarse. Encontrar una solución le da hasta 8 soluciones relacionadas de forma gratuita.
• Empieza desde Corners. Colocar una reina en un rincón elimina inmediatamente muchos cuadrados, lo que paradójicamente puede hacer que la colocación restante sea más fácil reduciendo las opciones.

El rompecabezas N Queens se originó como el "Eight Queens Puzzle", propuesto en 1848 por el jugador de ajedrez Max Bezzel en la revista alemana de ajedrez Schachzeitung. El desafío de colocar ocho reinas en un tablero de ajedrez estándar para que ninguno se ataque capturó la imaginación de matemáticos y entusiastas del ajedrez por igual.

Las primeras soluciones fueron publicadas en 1850 por Franz Nauck, quien también generalizó el problema a N queens en una junta NxN. El gran matemático Carl Friedrich Gauss se interesó en el problema y correspondió con su amigo Heinrich Schumacher, aunque Gauss encontró inicialmente sólo 72 de las 92 soluciones para el caso de 8-queen y creía equivocadamente que era el conjunto completo.

El rompecabezas se convirtió en un problema fundamental en la ciencia informática. En 1972, Edsger Dijkstra utilizó el problema de 8 Queens para ilustrar el poder de la programación estructurada y el algoritmo de retroceso. Sigue siendo uno de los ejercicios de programación más asignados en los cursos universitarios de informática, utilizados para enseñar recursión, satisfacción limitada y diseño de algoritmos. También sirve de referencia para comparar la eficiencia de diferentes algoritmos de búsqueda y técnicas de propagación de restricciones.

El problema N Queens tiene conexiones a muchas áreas de matemáticas, incluyendo combinatoria, teoría de grupo (a través de sus simetrías), y álgebra lineal. En 2021, se hizo un avance significativo cuando Michael Simkin demostró una fórmula asintotica para el número de soluciones, confirmando una conjetura de larga data. El problema también tiene aplicaciones prácticas en almacenamiento paralelo de memoria, pruebas de circuito VLSI y control de tráfico. A pesar de su declaración aparentemente simple, el problema N Queens sigue revelando nueva profundidad matemática.