El problema de las ocho reinas
La versión actual de la página aún no ha sido revisada por colaboradores experimentados y puede diferir significativamente de la versión revisada el 26 de enero de 2022; las comprobaciones requieren 2 ediciones .El problema de las ocho reinas es un problema combinatorio muy conocido para ordenar piezas en un tablero de ajedrez . Redacción inicial: "Disponga 8 reinas en un tablero de ajedrez estándar de 64 celdas para que ninguna de ellas sea atacada por otra " . Se entiende que la dama vence a todas las celdas ubicadas a lo largo de las verticales, horizontales y ambas diagonales.
Una generalización del problema es colocar las reinas de la misma manera en un campo rectangular arbitrario, en particular, uno cuadrado de lado .
Redacción
Estrictamente matemáticamente, el problema se puede formular de varias maneras, por ejemplo, de la siguiente manera: “Llena la matriz con ceros y unos de tal manera que la suma de todos los elementos de la matriz sea igual a 8, mientras que la suma de los elementos de cualquier columna, fila o fila diagonal de la matriz no exceda de uno.”
El objetivo final fijado para el solucionador del problema se puede formular de varias maneras:
- Construya cualquier solución al problema.
- Demostrar analíticamente que existe una solución .
- Determinar el número de soluciones.
- Construya todas las soluciones posibles.
- Escribir un programa de computadora que encuentre todas las posibles soluciones a un problema. Una de las tareas típicas para programar algoritmos de enumeración .
A veces, el planteamiento del problema requiere encontrar formas de colocar las reinas en el tablero de celdas (nótese que para el problema no tiene solución).
Características de la solución
El número total de arreglos posibles de 8 reinas en un tablero de 64 celdas es ( fórmula de combinación ). El número total de arreglos posibles que satisfacen las condiciones del problema es 92. El conjunto de estos 92 arreglos se divide en 12 subconjuntos (11 subconjuntos de 8 arreglos cada uno y uno de los cuatro restantes), en cada uno de los cuales todos los arreglos son obtenidos entre sí por transformaciones de simetría: reflejos de los ejes vertical y horizontal, reflejos de las diagonales del tablero y rotaciones de 90, 180 y 270 grados.
Las computadoras modernas ya permiten resolver el problema (encontrar alguna o todas las soluciones) al enumerar exhaustivamente todas las opciones de arreglo posibles, pero tal solución generalmente se considera incorrecta: el solucionador del problema debe encontrar un algoritmo que reduzca significativamente la cantidad de enumeración. . Por ejemplo, es obvio que no puede haber más de una reina en un tablero horizontal o vertical, por lo que el algoritmo de solución no debe incluir inicialmente en la búsqueda las posiciones donde dos reinas están en el mismo tablero horizontal o vertical. Incluso una regla tan simple puede reducir significativamente la cantidad de ubicaciones posibles: en lugar de 4 426 165 368 . Al generar permutaciones que son soluciones al problema de las ocho torres y luego verificar los ataques a lo largo de las diagonales, podemos reducir el número de arreglos posibles a solo . Si, al generar posiciones, también se tiene en cuenta la condición de ataque diagonal, entonces la velocidad de conteo aumenta en un orden de magnitud y el número de ciclos para resolver el problema será 4022.
Uno de los algoritmos típicos para resolver el problema es el uso del retroceso : la primera reina se coloca en la primera horizontal, luego cada siguiente se coloca en la siguiente para que no sea superada por las reinas previamente establecidas. Si en la siguiente etapa de configuración no hay campos libres, se produce un paso atrás: la reina establecida anteriormente se reorganiza.
Notas
Enlaces
- Solución fractal del problema para tableros si N=(a1)•(a2)•…•(an), donde a1 ≥ 4 y a2,…,an > 4 (A. Ermakov, 2011)
- Método genérico n queens con implementación java