stringtranslate.com

Rompecabezas de ocho reinas

La única solución simétrica al rompecabezas de las ocho reinas ( hasta rotación y reflexión)

El rompecabezas de las ocho reinas es el problema de colocar ocho reinas de ajedrez en un tablero de ajedrez de 8 × 8 para que ninguna reina se amenace entre sí; por tanto, una solución requiere que no haya dos reinas que compartan la misma fila, columna o diagonal. Hay 92 soluciones. El problema se planteó por primera vez a mediados del siglo XIX. En la era moderna, se utiliza a menudo como problema de ejemplo para diversas técnicas de programación informática .

El rompecabezas de las ocho reinas es un caso especial del problema más general de las n reinas , consistente en colocar n reinas no atacantes en un tablero de ajedrez de n × n . Existen soluciones para todos los números naturales n con la excepción de n = 2 y n = 3. Aunque el número exacto de soluciones solo se conoce para n ≤ 27, la tasa de crecimiento asintótica del número de soluciones es aproximadamente (0,143 n ) n .

Historia

El compositor de ajedrez Max Bezzel publicó el rompecabezas de las ocho reinas en 1848. Franz Nauck publicó las primeras soluciones en 1850. [1] Nauck también amplió el rompecabezas al problema de las n reinas, con n reinas en un tablero de ajedrez de n × n cuadrados.

Desde entonces, muchos matemáticos , incluido Carl Friedrich Gauss , han trabajado tanto en el rompecabezas de las ocho reinas como en su versión generalizada de las n reinas. En 1874, S. Günther propuso un método que utiliza determinantes para encontrar soluciones. [1] JWL Glaisher perfeccionó el enfoque de Gunther.

En 1972, Edsger Dijkstra utilizó este problema para ilustrar el poder de lo que llamó programación estructurada . Publicó una descripción muy detallada de un algoritmo de retroceso en profundidad . [2]

Construir y contar soluciones cuando n = 8

El problema de encontrar todas las soluciones al problema de las 8 reinas puede ser bastante costoso desde el punto de vista computacional, ya que hay 4.426.165.368 posibles disposiciones de ocho reinas en un tablero de 8 × 8, [a] pero sólo 92 soluciones. Es posible utilizar atajos que reduzcan los requisitos computacionales o reglas generales que eviten técnicas computacionales de fuerza bruta . Por ejemplo, aplicando una regla sencilla que elige una reina de cada columna, es posible reducir el número de posibilidades a 16.777.216 (es decir, 8 8 ) combinaciones posibles. Generar permutaciones reduce aún más las posibilidades a sólo 40.320 (es decir, ¡ 8! ), que luego se pueden comprobar en busca de ataques diagonales.

El rompecabezas de las ocho reinas tiene 92 soluciones distintas. Si las soluciones que difieren sólo por las operaciones de simetría de rotación y reflexión del tablero se cuentan como una, el rompecabezas tiene 12 soluciones. Éstas se denominan soluciones fundamentales ; A continuación se muestran representantes de cada uno.

Una solución fundamental suele tener ocho variantes (incluida su forma original) que se obtienen girando 90, 180 o 270° y luego reflejando cada una de las cuatro variantes de rotación en un espejo en una posición fija. Sin embargo, una de las 12 soluciones fundamentales (la solución 12 a continuación) es idéntica a su propia rotación de 180°, por lo que solo tiene cuatro variantes (él mismo y su reflexión, su rotación de 90° y su reflexión). [b] Por tanto, el número total de soluciones distintas es 11×8 + 1×4 = 92.

Todas las soluciones fundamentales se presentan a continuación:

La solución 10 tiene la propiedad adicional de que no hay tres reinas en línea recta .

Existencia de soluciones

Los algoritmos de fuerza bruta para contar el número de soluciones son computacionalmente manejables para n  = 8 , pero serían intratables para problemas de n  ≥ 20 , ¡como 20! = 2,433 × 10 18 . Si el objetivo es encontrar una solución única, se puede demostrar que existen soluciones para todo n ≥ 4 sin búsqueda alguna. [3] [4] Estas soluciones exhiben patrones escalonados, como en los siguientes ejemplos para n = 8, 9 y 10:

Los ejemplos anteriores se pueden obtener con las siguientes fórmulas. [3] Sea ( i , j ) el cuadrado de la columna i y la fila j del tablero de ajedrez n × n , k un número entero.

Un enfoque [3] es

  1. Si el resto de dividir n entre 6 no es 2 o 3, entonces la lista es simplemente todos los números pares seguidos de todos los números impares no mayores que n .
  2. De lo contrario, escriba listas separadas de números pares e impares (2, 4, 6, 8 – 1, 3, 5, 7).
  3. Si el resto es 2, intercambie 1 y 3 en la lista impar y mueva 5 hasta el final ( 3, 1 , 7, 5 ).
  4. Si el resto es 3, mueva 2 al final de la lista par y 1,3 al final de la lista impar (4, 6, 8, 2 – 5, 7, 9, 1, 3 ).
  5. Agregue la lista impar a la lista par y coloque las reinas en las filas dadas por estos números, de izquierda a derecha (a2, b4, c6, d8, e3, f1, g7, h5).

Para n  = 8 , esto da como resultado la solución fundamental 1 anterior. A continuación se presentan algunos ejemplos más.

Soluciones de conteo para otros tamaños n

enumeración exacta

No existe una fórmula conocida para el número exacto de soluciones para colocar n reinas en un tablero de n × n , es decir, el número de conjuntos independientes de tamaño n en un gráfico de reinas de n × n . El tablero de 27 × 27 es el tablero de mayor orden que se ha enumerado por completo. [5] Las siguientes tablas dan el número de soluciones al problema de las n reinas, tanto fundamentales (secuencia A002562 en la OEIS ) como todas (secuencia A000170 en la OEIS ), para todos los casos conocidos.

Se conoce el número de ubicaciones en las que, además, no se alinean tres reinas en ninguna línea recta (secuencia A365437 en la OEIS ).

Enumeración asintótica

En 2021, Michael Simkin demostró que para números grandes n , el número de soluciones del problema de n reinas es aproximadamente . [6] Más precisamente, el número de soluciones tiene un crecimiento asintótico.

[7]opoca notación o

Si, en cambio, se considera un tablero de ajedrez toroidal (donde las diagonales se "envuelven" desde el borde superior hacia abajo y desde el borde izquierdo hacia la derecha), sólo es posible colocar n reinas en un tablero si en este caso, el número asintótico de soluciones es [8] [9]

Problemas relacionados

Dimensiones superiores
Encuentre el número de reinas no atacantes que se pueden colocar en un espacio de ajedrez d -dimensional de tamaño n . Se pueden colocar más de n reinas en algunas dimensiones superiores (el ejemplo más pequeño es cuatro reinas no atacantes en un espacio de ajedrez de 3×3×3), y de hecho se sabe que para cualquier k , hay dimensiones superiores donde n k Las reinas no son suficientes para atacar todos los espacios. [10] [11]
Usar piezas distintas a las reinas
En un tablero de 8×8 se pueden colocar 32 caballos , o 14 alfiles , 16 reyes u ocho torres , de modo que no haya dos piezas que se ataquen entre sí. En el caso de los caballeros, una solución fácil es colocar uno en cada casilla de un color determinado, ya que sólo se mueven al color opuesto. La solución también es fácil para torres y reyes. Se pueden colocar dieciséis reyes en el tablero dividiéndolo en cuadrados de 2 por 2 y colocando los reyes en puntos equivalentes en cada cuadrado. Las ubicaciones de n torres en un tablero de n × n están en correspondencia directa con matrices de permutación de orden n .
Variaciones de ajedrez
Se pueden plantear problemas relacionados con variaciones del ajedrez como el shogi . Por ejemplo, el problema de n + k reyes dragón requiere colocar k peones de shogi y n + k reyes dragón que no se ataquen entre sí en un tablero de shogi de n × n . [12]
Tableros no estándar
Pólya estudió el problema de las n reinas en un tablero toroidal ("en forma de rosquilla") y demostró que hay una solución en un tablero de n × n si y sólo si n no es divisible por 2 o 3. [13]
Dominación
Dado un tablero de n × n , el número de dominación es el número mínimo de reinas (u otras piezas) necesarias para atacar u ocupar cada casilla. Para n = 8, el número de dominación de la reina es 5. [14] [15]
Reinas y otras piezas
Las variantes incluyen mezclar reinas con otras piezas; por ejemplo, colocar m reinas y m caballeros en un tablero de n × n para que ninguna pieza ataque a otra [16] o colocar reinas y peones para que no haya dos reinas que se ataquen entre sí. [17]
cuadrados magicos
En 1992, Demirörs, Rafraf y Tanik publicaron un método para convertir algunos cuadrados mágicos en soluciones de n -reinas y viceversa. [18]
cuadrados latinos
En una matriz de n × n , coloque cada dígito del 1 al n en n ubicaciones de la matriz de modo que no haya dos instancias del mismo dígito en la misma fila o columna.
Cobertura exacta
Considere una matriz con una columna primaria para cada uno de los n rangos del tablero, una columna primaria para cada uno de los n archivos y una columna secundaria para cada una de las 4 n − 6 diagonales no triviales del tablero. La matriz tiene n 2 filas: una para cada posible ubicación de la reina, y cada fila tiene un 1 en las columnas correspondientes a la fila, fila y diagonales de esa casilla y un 0 en todas las demás columnas. Entonces el problema de las n reinas equivale a elegir un subconjunto de las filas de esta matriz tal que cada columna primaria tenga un 1 precisamente en una de las filas elegidas y cada columna secundaria tenga un 1 en como máximo una de las filas elegidas; Este es un ejemplo de un problema de cobertura exacta generalizado , del cual el sudoku es otro ejemplo.
finalización de n -reinas
El problema de finalización pregunta si, dado un tablero de ajedrez de n × n en el que ya se han colocado algunas reinas, es posible colocar una reina en cada fila restante de modo que no haya dos reinas que se ataquen entre sí. Esta y otras preguntas relacionadas son NP-completa y #P-completa . [19] Se puede completar cualquier colocación de como máximo n /60 reinas, mientras que hay configuraciones parciales de aproximadamente n /4 reinas que no se pueden completar. [20]

Ejercicio de diseño de algoritmos.

Encontrar todas las soluciones al rompecabezas de las ocho reinas es un buen ejemplo de un problema simple pero no trivial. Por esta razón, suele utilizarse como problema de ejemplo para diversas técnicas de programación, incluidos enfoques no tradicionales como la programación de restricciones , la programación lógica o los algoritmos genéticos . Con mayor frecuencia, se utiliza como ejemplo de un problema que puede resolverse con un algoritmo recursivo , formulando el problema de las n reinas de manera inductiva en términos de agregar una sola reina a cualquier solución al problema de colocar n −1 reinas en una n × n tablero de ajedrez. La inducción toca fondo con la solución al 'problema' de colocar 0 reinas en el tablero, que es el tablero vacío.

Esta técnica se puede utilizar de una manera que es mucho más eficiente que el ingenuo algoritmo de búsqueda de fuerza bruta , que considera las 64 8  = 2 48  = 281,474,976,710,656 posibles ubicaciones ciegas de ocho reinas, y luego las filtra para eliminar todas las ubicaciones que colocan dos reinas ya sea en la misma casilla (¡dejando sólo 64!/56! = 178.462.987.637.760 ubicaciones posibles) o en posiciones de ataque mutuo. Este algoritmo tan pobre producirá, entre otras cosas, los mismos resultados una y otra vez en todas las diferentes permutaciones de las asignaciones de las ocho reinas, además de repetir los mismos cálculos una y otra vez para los diferentes subconjuntos de cada una. solución. Un mejor algoritmo de fuerza bruta coloca una sola reina en cada fila, lo que lleva a sólo 8 8  = 2 24  = 16,777,216 colocaciones ciegas.

Es posible hacerlo mucho mejor que esto. Un algoritmo resuelve el rompecabezas de las ocho torres generando las permutaciones de los números del 1 al 8 (¡de los cuales hay 8! = 40,320) y utiliza los elementos de cada permutación como índices para colocar una reina en cada fila. Luego rechaza aquellos tableros con posiciones de ataque diagonales.

Esta animación ilustra cómo retroceder para resolver el problema. Una reina se coloca en una columna que se sabe que no causa conflicto. Si no se encuentra una columna, el programa vuelve al último estado correcto y luego intenta con una columna diferente.

El programa de búsqueda en profundidad de retroceso , una ligera mejora del método de permutación, construye el árbol de búsqueda considerando una fila del tablero a la vez, eliminando la mayoría de las posiciones del tablero que no son solución en una etapa muy temprana de su construcción. Debido a que rechaza ataques de torres y diagonales incluso en tableros incompletos, examina sólo 15.720 posibles ubicaciones de reinas. Una mejora adicional, que examina sólo 5.508 posibles ubicaciones de reinas, es combinar el método basado en permutaciones con el método de poda temprana: las permutaciones se generan primero en profundidad y el espacio de búsqueda se poda si la permutación parcial produce un ataque diagonal.La programación de restricciones también puede ser muy eficaz en este problema.

solución de conflictos mínimos para 8 reinas

Una alternativa a la búsqueda exhaustiva es un algoritmo de "reparación iterativa", que normalmente comienza con todas las reinas del tablero, por ejemplo con una reina por columna. [21] Luego cuenta el número de conflictos (ataques) y utiliza una heurística para determinar cómo mejorar la ubicación de las reinas. La heurística de ' conflictos mínimos ' (mover la pieza con el mayor número de conflictos a la casilla de la misma columna donde el número de conflictos es menor) es particularmente efectiva: encuentra fácilmente una solución incluso para el problema de 1.000.000 de reinas. [22] [23]

A diferencia de la búsqueda retrospectiva descrita anteriormente, la reparación iterativa no garantiza una solución: como todos los procedimientos codiciosos , puede quedarse estancada en un óptimo local. (En tal caso, el algoritmo puede reiniciarse con una configuración inicial diferente). Por otro lado, puede resolver tamaños de problemas que están varios órdenes de magnitud más allá del alcance de una búsqueda en profundidad.

Como alternativa al retroceso, las soluciones se pueden contar enumerando recursivamente soluciones parciales válidas, una fila a la vez. En lugar de construir posiciones completas del tablero, las diagonales y columnas bloqueadas se rastrean con operaciones bit a bit. Esto no permite la recuperación de soluciones individuales. [24] [25]

Programa de muestra

El siguiente programa es una traducción de la solución de Niklaus Wirth al lenguaje de programación Python , pero prescinde de la aritmética de índices que se encuentra en el original y en su lugar utiliza listas para mantener el código del programa lo más simple posible. Al utilizar una corrutina en forma de función generadora , ambas versiones del original se pueden unificar para calcular una o todas las soluciones. Sólo se examinan 15.720 posibles ubicaciones de reinas. [26] [27]

def  reinas ( n ,  i ,  a ,  b ,  c ):  si  i  <  n :  para  j  en  el rango ( n ):  si  j  no  está en  a  y  i + j  no  está en  b  y  i - j  no  está en  c :  rendimiento de  reinas ( n ,  i + 1 ,  a + [ j ],  b + [ i + j ],  c + [ i - j ])  más :  produce  apara  solución  en  reinas ( 8 ,  0 ,  [],  [],  []):  imprimir ( solución )

En la cultura popular

Ver también

Notas

  1. ^ El número de combinaciones de 8 cuadrados de 64 es el coeficiente binomial 64 C 8 .
  2. ^ Otras simetrías son posibles para otros valores de n . Por ejemplo, hay una ubicación de cinco reinas no atacantes en un tablero de 5×5 que es idéntica a su propia rotación de 90°. Estas soluciones tienen sólo dos variantes (él mismo y su reflejo). Si n > 1, no es posible que una solución sea igual a su propio reflejo porque eso requeriría que dos reinas estuvieran enfrentadas.

Referencias

  1. ^ ab WW Rouse Ball (1960) "El problema de las ocho reinas", en Ensayos y recreaciones matemáticas , Macmillan, Nueva York, págs.
  2. ^ O.-J. Dahl , EW Dijkstra , Programación estructurada CAR Hoare , Academic Press, Londres, 1972 ISBN 0-12-200550-3 , págs. 
  3. ^ a b C Bo Bernhardsson (1991). "Soluciones explícitas al problema de las N-Reinas para todos los N". Toro SIGART . 2 (2): 7. doi :10.1145/122319.122322. S2CID  10644706.
  4. ^ EJ Hoffman et al., "Construcción para las soluciones del problema de m Queens". Revista Matemáticas , vol. XX (1969), págs. 66 a 72. [1] Archivado el 8 de noviembre de 2016 en Wayback Machine.
  5. ^ El proyecto Q27
  6. ^ Sloman, Leila (21 de septiembre de 2021). "Un matemático responde al problema de ajedrez sobre atacar a las reinas". Revista Quanta . Consultado el 22 de septiembre de 2021 .
  7. ^ Simkin, Michael (28 de julio de 2021). "El número de configuraciones de $n$ -reinas". arXiv : 2107.13460v2 [math.CO].
  8. ^ Luria, Zur (15 de mayo de 2017). "Nuevos límites en el número de configuraciones de n reinas". arXiv : 1705.05225v2 [math.CO].
  9. ^ Bowtell, Candida; Keevash, Peter (16 de septiembre de 2021). "El problema de las $ n $ -reinas". arXiv : 2109.08083v1 [math.CO].
  10. ^ J. Barr y S. Rao (2006), El problema de las n-reinas en dimensiones superiores, Elemente der Mathematik, vol 61 (4), págs.
  11. ^ Martín S. Pearson. "Reinas en un tablero de ajedrez: más allá de la segunda dimensión" (php) . Consultado el 27 de enero de 2020 .
  12. ^ Chatham, Doug (1 de diciembre de 2018). "Reflexiones sobre el problema de los reyes dragones n + k". Revista Matemática Recreativa . 5 (10): 39–55. doi : 10.2478/rmm-2018-0007 .
  13. ^ G. Pólya, Uber die "doppelt-periodischen" Losungen des n-Damen-Problems, George Pólya: artículos recopilados, vol. IV, GC. Rota, ed., MIT Press, Cambridge, Londres, 1984, págs. 237–247
  14. ^ Hamburguesa, AP; Cockayne, EJ; Mynhardt, CM (1997), "Dominación e irredundancia en el gráfico de reinas", Matemáticas discretas , 163 (1–3): 47–66, doi :10.1016/0012-365X(95)00327-S, hdl : 1828/ 2670 , señor  1428557
  15. ^ Weakley, William D. (2018), "Reinas de todo el mundo en veinticinco años", en Gera, Ralucca ; Haynes, Teresa W .; Hedetniemi, Stephen T. (eds.), Teoría de grafos: conjeturas favoritas y problemas abiertos - 2 , Libros de problemas de matemáticas, Cham: Springer, págs. 43–54, doi :10.1007/978-3-319-97686-0_5, Señor  3889146
  16. ^ "Problema de reinas y caballeros". Archivado desde el original el 16 de octubre de 2005 . Consultado el 20 de septiembre de 2005 .
  17. ^ Bell, Jordania; Stevens, Brett (2009). "Una encuesta de resultados conocidos y áreas de investigación para n-reinas". Matemáticas discretas . 309 (1): 1–31. doi : 10.1016/j.disc.2007.12.043 .
  18. ^ O. Demirörs, N. Rafraf y MM Tanik. Obtener soluciones de n reinas a partir de cuadrados mágicos y construir cuadrados mágicos a partir de soluciones de n reinas. Revista de Matemáticas Recreativas, 24:272–280, 1992
  19. ^ Caballero, Ian P.; Jefferson, Cristóbal; Nightingale, Peter (agosto de 2017). "Complejidad de la finalización de n-Queens". Revista de investigación en inteligencia artificial . 59 : 815–848. doi : 10.1613/jair.5512 . hdl : 10023/11627 . ISSN  1076-9757 . Consultado el 7 de septiembre de 2017 .
  20. ^ Glock, Stefan; Correia, David Munhá; Sudakov, Benny (6 de julio de 2022). "El problema de finalización de las n reinas". Investigación en Ciencias Matemáticas . 9 (41): 41. doi : 10.1007/s40687-022-00335-1 . PMC 9259550 . PMID  35815227. S2CID  244478527. 
  21. ^ Un algoritmo de tiempo polinomial para el problema de N-Queen por Rok Sosic y Jun Gu, 1990. Describe el tiempo de ejecución de hasta 500.000 reinas, que era el máximo que podían ejecutar debido a limitaciones de memoria.
  22. ^ Minton, Steven; Johnston, Mark D.; Philips, Andrés B.; Laird, Philip (1 de diciembre de 1992). "Minimizar conflictos: un método de reparación heurístico para la satisfacción de restricciones y problemas de programación". Inteligencia artificial . 58 (1): 161–205. doi :10.1016/0004-3702(92)90007-K. hdl : 2060/19930006097 . ISSN  0004-3702. S2CID  14830518.
  23. ^ Sosic, R.; Gu, Jun (octubre de 1994). "Búsqueda local eficiente con minimización de conflictos: un estudio de caso del problema de las n-reinas". Transacciones IEEE sobre conocimiento e ingeniería de datos . 6 (5): 661–668. doi : 10.1109/69.317698. ISSN  1558-2191.
  24. ^ Qiu, Zongyan (febrero de 2002). "Codificación de vector de bits del problema de n-reinas". Avisos ACM SIGPLAN . 37 (2): 68–70. doi :10.1145/568600.568613.
  25. ^ Richards, Martín (1997). Algoritmos de retroceso en MCPL utilizando patrones de bits y recursividad (PDF) (Reporte técnico). Laboratorio de Computación de la Universidad de Cambridge. UCAM-CL-TR-433.
  26. ^ Wirth, Niklaus (1976). "Algoritmos + Estructuras de datos = Programas" . Serie Prentice-Hall en Computación Automática . Prentice Hall. Código bibliográfico : 1976adsp.book.....W. ISBN 978-0-13-022418-7.pag. 145
  27. ^ Wirth, Niklaus (2012) [orig. 2004]. "El problema de las ocho reinas". Algoritmos y estructuras de datos (PDF) . Versión Oberon con correcciones y modificaciones autorizadas. págs. 114-118.
  28. ^ DeMaria, Rusel (15 de noviembre de 1993). El séptimo invitado: la guía de estrategia oficial (PDF) . Juegos Primarios. ISBN 978-1-5595-8468-5. Consultado el 22 de abril de 2021 .
  29. ^ "ナゾ130 クイーンの問題5".ゲームの匠(en japonés) . Consultado el 17 de septiembre de 2021 .

Otras lecturas

enlaces externos

La implementación del algoritmo de Wikibook tiene una página sobre el tema: Problema de N-reinas