Hispanopedia Wiki
Articulo de referencia

Rompecabezas de las ocho reinas

La única solución simétrica al rompecabezas de las ocho reinas ( salvo rotación y reflexión ). El problema de las ocho reinas consiste en colocar ocho reinas de ajedrez en un ta...

Hispanopedia WikiContenido en espanolLectura gratuita

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

El problema de las ocho reinas consiste en colocar ocho reinas de ajedrez en un tablero de 8x8 de manera que ninguna reina amenace a otra; por lo tanto, una solución requiere que ninguna reina comparta la misma fila, columna o diagonal. Existen 92 soluciones. El problema se planteó por primera vez a mediados del siglo XIX. En la actualidad, se utiliza con frecuencia como ejemplo para diversas técnicas de programación informática .

El problema de las ocho reinas es un caso especial del problema más general de las n reinas , que consiste en colocar n reinas que no ataquen entre sí 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ótico del número de soluciones es aproximadamente(0,143norte)norte{\displaystyle (0.143n)^{n}}.

Historia

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

Desde entonces, muchos matemáticos , entre ellos Carl Friedrich Gauss , han trabajado tanto en el problema 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 Günther.

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

Construcción y conteo de soluciones cuando n = 8

El problema de encontrar todas las soluciones al problema de las 8 reinas puede ser bastante costoso computacionalmente, ya que hay 4.426.165.368 posibles arreglos de ocho reinas en un tablero de 8×8, [ a ] pero solo 92 soluciones. Es posible usar atajos que reducen los requisitos computacionales o reglas empíricas que evitan técnicas computacionales de fuerza bruta . Por ejemplo, al aplicar una regla simple 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 solo 40.320 (es decir, 8! ), que luego se pueden verificar para ataques diagonales.

El rompecabezas de las ocho reinas tiene 92 soluciones distintas. Si se consideran como una sola las soluciones que difieren únicamente en las operaciones de simetría de rotación y reflexión del tablero, el rompecabezas tiene 12 soluciones. Estas se denominan soluciones fundamentales ; a continuación se muestran ejemplos de cada una.

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

A continuación se presentan todas las soluciones fundamentales:

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 paranorte=8{\displaystyle n=8}, pero sería intratable para problemas denorte≥20{\displaystyle n\geq 20}, como 20! = 2,433 × 10 18 . Si el objetivo es encontrar una única solución, se puede demostrar que existen soluciones para todo n ≥ 4 sin necesidad de búsqueda alguna. [ 3 ] [ 4 ] Estas soluciones presentan 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 ) la casilla en la columna i y la fila j en el 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, intercambia 1 y 3 en la lista impar y mueve 5 al final ( 3, 1 , 7, 5 ).
  4. Si el resto es 3, mueve 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. Añade la lista impar a la lista par y coloca las reinas en las filas indicadas 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 mencionada anteriormente. A continuación se presentan algunos ejemplos más.

  • 14 reinas (resto 2): 2, 4, 6, 8, 10, 12, 14, 3, 1, 7, 9, 11, 13, 5.
  • 15 reinas (resto 3): 4, 6, 8, 10, 12, 14, 2, 5, 7, 9, 11, 13, 15, 1, 3.
  • 20 reinas (resto 2): 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 3, 1, 7, 9, 11, 13, 15, 17, 19, 5.

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 n × n , es decir, el número de conjuntos independientes de tamaño n en un grafo de reinas n × n . El tablero 27×27 es el tablero de orden más alto que se ha enumerado completamente. [ 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 colocaciones en las que además no hay tres reinas en ninguna línea recta.norte≤25{\displaystyle n\leq 25}(secuencia A365437 en el OEIS ) .

Enumeración asintótica

En 2021, Michael Simkin demostró que para números grandes n , el número de soluciones del problema de las n reinas es aproximadamente(0,143norte)norte{\displaystyle (0.143n)^{n}}. [ 6 ] Más precisamente, el númeroQ(norte){\displaystyle {\mathcal {Q}}(n)}de soluciones tiene crecimiento asintóticoQ(norte)=((1±o(1))nortemi−α)norte{\displaystyle {\mathcal {Q}}(n)=((1\pm o(1))ne^{-\alpha })^{n}} dóndeα{\displaystyle \alpha }es una constante que se encuentra entre 1,939 y 1,945. [ 7 ] (Aquí o (1) representa la notación o minúscula ).

Si en cambio se considera un tablero de ajedrez toroidal (donde las diagonales "envuelven" desde el borde superior hasta el inferior y desde el borde izquierdo hasta el derecho), solo es posible colocar n reinas en unnorte×norte{\displaystyle n\times n}tablero sinorte≡1,5mod6.{\displaystyle n\equiv 1,5\mod 6.} En este caso, el número asintótico de soluciones es [ 8 ] [ 9 ]T(norte)=((1+o(1))nortemi−3)norte.{\displaystyle T(n)=((1+o(1))ne^{-3})^{n}.}

50 reinas que no se amenazan entre sí en un tablero de 8×8×8
Dimensiones superiores
Encuentra 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 son cuatro reinas no atacantes en un espacio de ajedrez de 3×3×3), y de hecho se sabe que para cualquier k , existen dimensiones superiores donde n k reinas no son suficientes para atacar todos los espacios. [ 10 ] [ 11 ]
Utilizar piezas distintas a las reinas
En un tablero de 8×8 se pueden colocar 32 caballos , o 14 alfiles , 16 reyes u 8 torres , de manera que ninguna pieza ataque a otra. En el caso de los caballos, una solución sencilla es colocar uno en cada casilla de un color determinado, ya que solo se mueven al color opuesto. La solución también es sencilla para las torres y los reyes. Se pueden colocar dieciséis reyes en el tablero dividiéndolo en cuadrados de 2×2 y colocando los reyes en puntos equivalentes en cada casilla. Las colocaciones de n torres en un tablero de n × n se corresponden directamente con matrices de permutación de orden n .
Variaciones del ajedrez
Se pueden plantear problemas similares para variantes del ajedrez como el shogi . Por ejemplo, el problema de los n + k reyes dragón consiste en colocar k peones de shogi y n + k reyes dragón que no se atacan mutuamente en un tablero de shogi de n × n . [ 12 ]
placas no estándar
Pólya estudió el problema de las n reinas en un tablero toroidal ("en forma de rosquilla") y demostró que existe una solución en un tablero n × n si y solo 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
Entre las variantes se incluye la mezcla de reinas con otras piezas; por ejemplo, colocar m reinas y m caballos en un tablero de n × n de manera que ninguna pieza ataque a otra [ 16 ] o colocar reinas y peones de manera que ninguna reina ataque a otra. [ 17 ]
cuadrados mágicos
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 n × n , coloque cada dígito del 1 al n en n posiciones de la matriz de manera que no haya dos instancias del mismo dígito en la misma fila o columna.
Cobertura exacta
Consideremos una matriz con una columna primaria para cada una de las n filas del tablero, una columna primaria para cada una de las n columnas 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 colocación de la reina, y cada fila tiene un 1 en las columnas correspondientes a la fila, columna y diagonales de esa casilla, y un 0 en todas las demás columnas. Entonces, el problema de las n reinas es equivalente a elegir un subconjunto de las filas de esta matriz de tal manera que cada columna primaria tenga un 1 en exactamente 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 completación plantea si, dado un tablero de ajedrez de n × n en el que ya hay algunas reinas colocadas, es posible colocar una reina en cada fila restante de manera que ninguna reina ataque a otra. Este problema y otros relacionados son NP-completos y #P-completos . [ 19 ] Cualquier colocación de como máximo n /60 reinas puede completarse, mientras que existen configuraciones parciales de aproximadamente n /4 reinas que no pueden completarse. [ 20 ]
arreglos de Costas
Una matriz de Costas de reinas no atacantes o NAQCA es una matriz de Costas que también es una solución al problema de las n reinas. La única NAQCA conocida es el caso trivial de 1×1, y se conjetura que no existen otras. [ 21 ]

Ejercicio de diseño de algoritmos

Esta animación ilustra el método de retroceso para resolver el problema. La i -ésima reina se coloca en la i -ésima fila del tablero de ajedrez, en una columna que se sabe que no causa conflictos. Si no se encuentra una columna, el programa regresa al último estado válido y luego intenta con otra columna.

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, se usa frecuentemente como ejemplo para diversas técnicas de programación, incluyendo enfoques no tradicionales como la programación con restricciones , la programación lógica o los algoritmos genéticos . Generalmente, se usa como ejemplo de un problema que se puede resolver con un algoritmo recursivo , formulando el problema de las n reinas de forma inductiva en términos de agregar una sola reina a cualquier solución al problema de colocar n −1 reinas en un tablero de ajedrez de n × n . La inducción llega a su fin con la solución al "problema" de colocar 0 reinas en el tablero, que es el tablero vacío. Este proceso se puede hacer más eficiente aplicando la observación de que cada columna del tablero debe contener exactamente una reina, y restringiendo las posiciones en las que el algoritmo intenta agregar la i -ésima reina a la i -ésima fila del tablero, en columnas que no estén ya atacadas por otras reinas. Estas opciones reducen significativamente el número de ubicaciones que deben probarse, lo que permite al algoritmo encontrar todas las soluciones en un8×8{\displaystyle 8\times 8}tablero de ajedrez en un tiempo tan breve que parece instantáneo. [ 22 ]

Solución de min-conflictos para 8 reinas

Una alternativa a la búsqueda exhaustiva es un algoritmo de «reparación iterativa», que normalmente comienza con todas las reinas en el tablero, por ejemplo, con una reina por columna. [ 23 ] Luego cuenta el número de conflictos (ataques) y utiliza una heurística para determinar cómo mejorar la colocació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. [ 24 ] [ 25 ]

A diferencia de la búsqueda con retroceso descrita anteriormente, la reparación iterativa no garantiza una solución: como todos los procedimientos voraces , puede quedarse atascada en un óptimo local. (En tal caso, el algoritmo puede reiniciarse con una configuración inicial diferente). Por otro lado, puede resolver problemas de tamaño que superan en varios órdenes de magnitud el alcance de una búsqueda en profundidad.

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

Programa de ejemplo

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 presente en el original y, en su lugar, utiliza listas para mantener el código lo más simple posible. Mediante el uso de una corrutina en forma de función generadora , ambas versiones del original se pueden unificar para calcular una o todas las soluciones. Solo se examinan 15 720 posibles posiciones de la reina. [ 28 ] [ 29 ]

def reinas ( n : int , i : int , a : lista , b : lista , c : lista ): if i < n : for j in range ( n ): if j not in a and i + j not in b and i - j not in c : yield from reinas ( n , i + 1 , a + [ j ], b + [ i + j ], c + [ i - j ]) else : yield apara solución en reinas ( 8 , 0 , [], [], []): imprimir ( solución )

El siguiente programa es una implementación de la descripción informal de Donald Knuth de la solución en la página 31, sección 7.2.2 Programación con retroceso de The Art of Computer Programming , volumen 4B, en el lenguaje de programación Python. [ 30 ]

def propiedad ( perm : lista ) -> bool : para k en rango ( 0 , len ( perm )): para j en rango ( 0 , len ( perm )): si j < k : si perm [ k ] == perm [ j ]: retornar Falso elif abs ( perm [ k ] - perm [ j ]) == k - j : retornar Falso retornar Verdaderodef extend ( perm : list , n : int ): new_perm = [ ] for p in perm : for i in range ( 0 , n ): new_perm.append ( p + [ i ] ) return new_permdef n_queens ( n : int ) -> int : dominio = lista ( rango ( 0 , n )) perm = [[]] for i in rango ( n ): nuevo_perm = lista ( filtro ( propiedad , extender ( perm , n ))) perm = nuevo_perm return len ( perm )

Véase también

Notas

  1. ↑ El número de combinaciones de 8 cuadrados de 64 es el coeficiente binomial 64 C 8 .
  2. ↑ Para otros valores de n , son posibles otras simetrías . Por ejemplo, existe una disposición de cinco reinas que no atacan en un tablero de 5×5 que es idéntica a su propia rotación de 90°. Estas soluciones solo tienen dos variantes (la misma y su reflexión). Si n > 1, no es posible que una solución sea igual a su propia reflexión, ya que esto requeriría que dos reinas se enfrentaran.

Referencias

  1. 1 2 W. W. Rouse Ball (1960) "El problema de las ocho reinas", en Mathematical Recreations and Essays , Macmillan, Nueva York, págs. 165–171.
  2. ↑ O.-J. Dahl , EW Dijkstra , CAR Hoare , Programación Estructurada , Academic Press, Londres, 1972 ISBN 0-12-200550-3, págs.  72–82.
  3. 1 2 3 Bo Bernhardsson (1991). "Soluciones explícitas al problema de las N-reinas para todo N". Boletín ACM SIGART . 2 (2): 7. doi : 10.1145/122319.122322 . S2CID 10644706 . 
  4. ↑ Hoffman, EJ; Loessi, JC; Moore, RC (1 de marzo de 1969). "Construcciones para la solución del problema de las m reinas" (PDF) . Mathematics Magazine . 42 (2): 66. doi : 10.2307/2689192 . JSTOR 2689192. Archivado del original el 8 de noviembre de 2016. Recuperado el 4 de noviembre de 2024 . 
  5. ↑ "El proyecto Q27" – vía GitHub.
  6. ↑ Sloman, Leila (21 de septiembre de 2021). "Matemática resuelve problema de ajedrez sobre el ataque a las reinas" . Quanta Magazine . 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, Cándida; 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. 133–137.
  11. ↑ Martin 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 n + k reyes dragón" . Recreational Mathematics Magazine . 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, CG. Rota, ed., MIT Press, Cambridge, Londres, 1984, págs. 237–247
  14. ↑ Burger, AP; Cockayne, EJ; Mynhardt, CM (1997). "Dominación e irredundancia en el grafo de reinas". Matemáticas Discretas . 163 ( 1– 3): 47– 66. doi : 10.1016/0012-365X(95)00327-S . hdl : 1828/2670 . MR 1428557 . 
  15. ↑ Weakley, William D. (2018). «Reinas alrededor del 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. Problemas matemáticos. Cham: Springer. pp. 43–54 . doi : 10.1007/978-3-319-97686-0_5 . ISBN  978-3-319-97684-6. MR 3889146 . 
  16. ↑ "Problema de reinas y caballos" . Archivado del original el 16 de octubre de 2005. Consultado el 20 de septiembre de 2005 .
  17. ↑ Bell, Jordan; Stevens, Brett (2009). "Una revisión de los resultados conocidos y las á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. Obtención de soluciones de n-reinas a partir de cuadrados mágicos y construcción de cuadrados mágicos a partir de soluciones de n-reinas. Journal of Recreational Mathematics, 24:272–280, 1992
  19. ↑ Gent, Ian P.; Jefferson, Christopher; Nightingale, Peter (agosto de 2017). "Complejidad de la completación de n -reinas" . Journal of Artificial Intelligence Research . 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 completación de 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. ↑ Drakakis, K., Gow, R., Rickard, S. (2009). "Vectores de distancia comunes entre arreglos de Costas". Advances in Mathematics of Communications . 3 (1): 35– 52. doi : 10.3934/amc.2009.3.35 . ISSN 1930-5338 . 
  22. ↑ Uehara, Ryuhei (2019). "5.1 El rompecabezas de las ocho reinas". Primer curso de algoritmos a través de rompecabezas . Springer Singapur. págs. 111–118 . doi : 10.1007/978-981-13-3188-6 . ISBN  9789811331886.
  23. ↑ Un algoritmo de tiempo polinomial para el problema de las N-reinas por Rok Sosic y Jun Gu, 1990. Describe el tiempo de ejecución para hasta 500.000 reinas, que era el máximo que podían ejecutar debido a las limitaciones de memoria.
  24. ↑ Minton, Steven; Johnston, Mark D.; Philips, Andrew B.; Laird, Philip (1 de diciembre de 1992). "Minimización de conflictos: un método heurístico de reparación 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 .  
  25. ↑ 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". IEEE Transactions on Knowledge and Data Engineering . 6 (5): 661– 668. Bibcode : 1994ITKDE...6..661S . doi : 10.1109/69.317698 . ISSN 1558-2191 . 
  26. ↑ Qiu, Zongyan (febrero de 2002). "Codificación de vector de bits del problema de las n reinas". ACM SIGPLAN Notices . 37 (2): 68– 70. doi : 10.1145/568600.568613 .
  27. ↑ Richards, Martin (1997). Algoritmos de retroceso en MCPL usando patrones de bits y recursión (PDF) (Informe técnico). Laboratorio de Computación de la Universidad de Cambridge. UCAM-CL-TR-433.
  28. ↑ Wirth, Niklaus (1976). Algoritmos + Estructuras de datos = Programas . Serie Prentice-Hall en Computación Automática. Prentice-Hall. Bibcode : 1976adsp.book.....W . ISBN 978-0-13-022418-7.pág. 145
  29. ↑ Wirth, Niklaus (2012) [orig. 2004]. "El problema de las ocho reinas". Algoritmos y estructuras de datos (PDF) . Versión de Oberon con correcciones y modificaciones autorizadas. págs. 114–118 . 
  30. ↑ Knuth, Donald Ervin (2023). El arte de la programación informática. Volumen 4B, parte 2: Algoritmos combinatorios . Boston, Múnich: Addison-Wesley. ISBN 978-0-201-03806-4.
  31. ↑ DeMaria, Rusel (15 de noviembre de 1993). El séptimo invitado: Guía de estrategia oficial (PDF) . Prima Games. ISBN 978-1-5595-8468-5Consultado el 22 de abril de 2021 .
  32. ↑ "ナゾ130 クイーンの問題5" .ゲームの匠(en japonés) . Consultado el 17 de septiembre de 2021 .

Lecturas adicionales

  • Bell, Jordan; Stevens, Brett (2009). "Una revisión de los resultados conocidos y las áreas de investigación para n -reinas" . Matemáticas Discretas . 309 (1): 1– 31. doi : 10.1016/j.disc.2007.12.043 .
  • Watkins, John J. (2004). Across the Board: The Mathematics of Chess Problems . Princeton: Princeton University Press. ISBN 978-0-691-11503-0.
  • Allison, L.; Yee, CN; McGaughey, M. (1988). "Problemas de reinas NxN tridimensionales" . Departamento de Ciencias de la Computación, Universidad de Monash, Australia.
  • Nudelman, S. (1995). "El problema modular de las N-reinas en dimensiones superiores" . Matemáticas Discretas . 146 ( 1–3 ): 159–167 . doi : 10.1016/0012-365X(94)00161-5 .
  • Engelhardt, M. (agosto de 2010). "Der Stammbaum der Lösungen des Damenproblems (en alemán, significa El cuadro genealógico de las soluciones al problema de las 8 reinas" . Spektrum der Wissenschaft : 68– 71.
  • Sobre el problema modular de la N-Reina en dimensiones superiores , Ricardo Gómez, Juan José Montellano y Ricardo Strausz (2004), Instituto de Matemáticas, Área de la Investigación Científica, Circuito Exterior, Ciudad Universitaria, México.
  • Budd, Timothy (2002). «Un estudio de caso: El rompecabezas de las ocho reinas» (PDF) . Introducción a la programación orientada a objetos (3.ª  ed.). Addison Wesley Longman. págs. 125-145 . ISBN  0-201-76031-2.
  • Wirth, Niklaus (2004) [actualizado en 2012]. "El problema de las ocho reinas". Algoritmos y estructuras de datos (PDF) . Versión de Oberon con correcciones y modificaciones autorizadas. págs. 114–118 . 
  • Weisstein, Eric W. "El problema de Queens" . MathWorld .
  • queens-cpm en GitHub: El rompecabezas de las ocho reinas en Turbo Pascal para CP/M
  • eight-queens.py en GitHub Solución en una línea del rompecabezas de las ocho reinas en Python
  • Soluciones en más de 100 lenguajes de programación diferentes (en Rosetta Code )