El problema consistiría en colocar n reinas en un tablero de ajedrez de n×n de tal manera que ninguna de las reinas quede atacando a otras.
Utilizando algoritmos genéticos, se tiene una solución para un problema de n-reinas. El programa mostrará al individuo élite de cada generación en pantalla (aunque cambie muy frecuentemente) y trabaja con elitismo (el mejor de una población, debe de pasar a la siguiente).
El porcentaje de mutación estaría definido como 5%, pero puede ser menor a 5%. El tamaño de la población debe ser predefinido. El programa se detiene cuando encuentre un individuo en el que ninguna de las reinas ataque a otra.
El programa recibe como entrada el tamaño del tablero número entero mayor a 3.
$ python3 main.py [tamano_del_tablero] Resultado de Ejecución para tamaño de tablero = 5 (n)
tiempo de ejecución del programa < 1 segundo
Resultado de Ejecución para tamaño de tablero = 10 (n)
tiempo de ejecución del programa < 1 segundo
Resultado de Ejecución para tamaño de tablero = 20 (n)
tiempo de ejecución del programa 14.06 segundos aprox.
Resultado de Ejecución para tamaño de tablero = 40 (n)
tiempo de ejecución del programa 40.92 segundos aprox.
- Mayor tamaño de tablero probado n = 343, encontrando solución.
- Tiempos de ejecución según Core i7-6600U CPU 2.81 GHz.
El problema fue originalmente propuesto en 1848 por el ajedrecista Max Bezzel. Durante años, muchos matemáticos, incluyendo a Gauss y a Georg Cantor, han trabajado en él y lo han generalizado a n-reinas. Las primeras soluciones fueron ofrecidas por Franz Nauck en 1850. Nauck también se abocó a las n-reinas (en un tablero de nxn de tamaño arbitrario). En 1874, S. Günther propuso un método para hallar las soluciones usando determinantes, y J.W.L. Glaisher redefinió su aproximación.
Edsger Dijkstra usó este problema en 1972 para ilustrar el poder de la llamada programación estructurada. Publicó una descripción muy detallada del desarrollo del algoritmo de backtracking, "depth-first".
Este acertijo apareció en el popular juego de computadora de los '90 llamado "The 7th Guest". ("Eight queens puzzle", 2019)
La idea con el problema N-Reinas consiste en colocar en un tablero de tamaño n, una cantidad n de Reinas sin que se amenacen. La amenaza se condiciona según el movimiento que realiza la Reina en un juego de ajedrez, el cual abarca: diagonales, verticales y horizontales desde la posición que se encuentra.
Considerando los movimientos de la Reina, el n para las proporciones del tablero y el número de Reinas; tienen que colocarse de manera que no se amenacen.
Se tiene la solución, en lenguaje de programación Java: backtracking-n-all-solutions-java-code para encontrar todas las soluciones al problema N-Reinas dado un n, este es incremental e implementa Backtracking el cuál en ejecución muestra:
$ Soluciones: [#_soluciones_encontradas_para_n_actual]
$ Tiempo transcurrido de ejecución: [tiempo_transcurrido] + milisegundosEn el trascurso de la ejecución, es un buen ejemplo para notar el consumo de recurso computacional dado mayor incremento del n para el problema, el cual se puede se puede graficar:
