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 problema de las ocho reinas consiste en colocar ocho reinas de ajedrez en un tablero de 8×8 de modo que ninguna de ellas se amenace entre sí; por lo tanto, una solución requiere que ninguna de las dos reinas comparta 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 un problema de 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 no atacantes en un tablero de ajedrez de n × n . Existen soluciones para todos los números naturales n, con 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,143 n ) 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 , incluido Carl Friedrich Gauss , han trabajado tanto en el rompecabezas de las ocho reinas como en su versión generalizada de n reinas. En 1874, S. Günther propuso un método que utilizaba determinantes para encontrar soluciones. [1] JWL Glaisher refinó 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 cuandonorte= 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 utilizar atajos que reducen los requisitos computacionales o reglas generales que evitan las 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. La generación de permutaciones reduce aún más las posibilidades a solo 40.320 (es decir, ¡8! ), que luego se pueden verificar para detectar ataques diagonales.

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

Una solución fundamental suele tener ocho variantes (incluida su forma original) que se obtienen al rotar 90, 180 o 270° y luego reflejar cada una de las cuatro variantes rotacionales en un espejo en una 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 reflejo, su rotación de 90° y el reflejo 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 para n  = 8 , pero serían intratables para problemas de n  ≥ 20 , ya que 20! = 2,433 × 10 18. Si el objetivo es encontrar una única solución, se puede demostrar que existen soluciones para todos los n ≥ 4 sin necesidad de realizar ninguna búsqueda. [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 ) el cuadrado en la columna i y la fila j en el tablero de ajedrez n × n , k un entero.

Un enfoque [3] es

  1. Si el resto de dividir n por 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, 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. Añade la lista impar a la lista par y coloca 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 mencionada anteriormente. A continuación se presentan algunos ejemplos más.

Soluciones de conteo para otros tamañosnorte

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 ninguna línea de 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 donde es una constante que se encuentra entre 1,939 y 1,945. [7] (Aquí o (1) representa la notación o pequeña ).

Si en cambio se considera un tablero de ajedrez toroidal (donde las diagonales se "envuelven" desde el borde superior al inferior y desde el borde izquierdo al derecho), 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
Halla el número de reinas no atacantes que se pueden colocar en un espacio de ajedrez de dimensión d y 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 reinas no son suficientes para atacar todos los espacios. [10] [11]
Utilizando 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 modo que ninguna pieza se ataque entre sí. En el caso de los caballos, una solución fácil es colocar uno en cada casilla de un color determinado, ya que se mueven solo al color opuesto. La solución también es fácil para las torres y los reyes. Se pueden colocar dieciséis reyes en el tablero dividiéndolo en casillas de 2 por 2 y colocando los reyes en puntos equivalentes en cada casilla. La colocación de n torres en un tablero de n × n está en correspondencia directa con matrices de permutación de orden n .
Variantes del ajedrez
Se pueden plantear problemas similares para variantes del ajedrez como el shogi . Por ejemplo, el problema de los n + k reyes dragones pide colocar k peones de shogi y n + k reyes dragones que no se atacan 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 ("con forma de rosquilla") y demostró que hay 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
Las variantes incluyen mezclar reinas con otras piezas; por ejemplo, colocar m reinas y m caballos en un tablero n × n de modo que ninguna pieza ataque a otra [16] o colocar reinas y peones de modo que ninguna reina se ataque entre sí. [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 ubicaciones en la matriz de modo 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 ubicació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 modo que cada columna primaria tenga un 1 en precisamente 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.
n -reinas completadas
El problema de completitud plantea la pregunta de 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-completas y #P-completas . [19] Cualquier colocación de como máximo n /60 reinas puede completarse, mientras que hay configuraciones parciales de aproximadamente n /4 reinas que no pueden completarse. [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, a menudo se utiliza como un problema de ejemplo para varias 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 . La mayoría de las veces, se utiliza como un ejemplo de un problema que se puede resolver 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 un tablero de ajedrez n × n . La inducción llega a su punto más bajo con la solución al "problema" de colocar 0 reinas en el tablero de ajedrez, que es el tablero de ajedrez vacío.

Esta técnica se puede utilizar de una manera mucho más eficiente que el ingenuo algoritmo de búsqueda por 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 coloquen dos reinas en la misma casilla (dejando solo 64!/56! = 178.462.987.637.760 ubicaciones posibles) o en posiciones que se ataquen mutuamente. Este algoritmo muy pobre, entre otras cosas, producirá los mismos resultados una y otra vez en todas las diferentes permutaciones de las asignaciones de las ocho reinas, así como repetirá los mismos cálculos una y otra vez para los diferentes subconjuntos de cada solución. Un mejor algoritmo de fuerza bruta coloca una sola reina en cada fila, lo que da como resultado solo 8 8  = 2 24  = 16 777 216 colocaciones ciegas.

Es posible hacerlo mucho mejor. 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 se vuelve atrás para resolver el problema. Se coloca una reina en una columna que se sabe que no genera conflictos. Si no se encuentra una columna, el programa vuelve al último estado correcto y luego prueba con una columna diferente.

El programa de búsqueda en profundidad con 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 los ataques de torres y diagonales incluso en tableros incompletos, examina solo 15.720 posibles ubicaciones de reinas. Una mejora adicional, que examina solo 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 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 mini-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 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 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 eficaz: encuentra fácilmente una solución incluso para el problema de 1.000.000 de reinas. [22] [23]

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ños 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 de tablero completas, se rastrean diagonales y columnas bloqueadas 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. Se examinan solo 15.720 posibles ubicaciones de la reina. [26] [27]

def  reinas ( n :  int ,  i :  int ,  a :  lista ,  b :  lista ,  c :  lista ):  si  i  <  n :  para  j  en  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 ])  de lo contrario :  rendimiento  apara  la solución  en  reinas ( 8 ,  0 ,  [],  [],  []):  imprimir ( solución )

En la cultura popular

Véase 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 disposición de cinco reinas no atacantes en un tablero de 5×5 que es idéntica a su propia rotación de 90°. Tales soluciones tienen solo dos variantes (ella misma 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 Mathematical Recreations and Essays , Macmillan, Nueva York, págs. 165-171.
  2. ^ O.-J. Dahl , EW Dijkstra , CAR Hoare Structured Programming , Academic Press, Londres, 1972 ISBN  0-12-200550-3 , págs. 72–82.
  3. ^ abc Bo Bernhardsson (1991). "Soluciones explícitas al problema de N-reinas para todos los N". Boletín ACM SIGART . 2 (2): 7. doi :10.1145/122319.122322. S2CID  10644706.
  4. ^ EJ Hoffman et al., "Construcciones para la solución del problema de m Queens". Mathematics Magazine , vol. XX (1969), págs. 66-72. [1] Archivado el 8 de noviembre de 2016 en Wayback Machine.
  5. ^ El Proyecto Q27
  6. ^ Sloman, Leila (21 de septiembre de 2021). "Matemático responde a un problema de ajedrez sobre el ataque de las damas". 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. 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 reyes dragones n+k". Revista de Matemáticas Recreativas . 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. ^ Burger, AP; Cockayne, EJ; Mynhardt, CM (1997), "Dominación e irredundancia en el grafo de las reinas", Discrete Mathematics , 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.), Graph Theory: Favorite Conjectures and Open Problems – 2 , Libros de problemas de matemáticas, Cham: Springer, págs. 43–54, doi :10.1007/978-3-319-97686-0_5, ISBN 978-3-319-97684-6, Sr.  3889146
  16. ^ "Problema de reinas y caballos". Archivado desde el original el 16 de octubre de 2005. Consultado el 20 de septiembre de 2005 .
  17. ^ Bell, Jordan; Stevens, Brett (2009). "Un estudio 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. 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 compleció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 compleción de n-reinas". Investigación en las 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 reinas 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, Andrew B.; Laird, Philip (1 de diciembre de 1992). "Minimización de conflictos: un método de reparación heurística para 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". IEEE Transactions on Knowledge and Data Engineering . 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 n-queen". ACM SIGPLAN Notices . 37 (2): 68–70. doi :10.1145/568600.568613.
  25. ^ 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.
  26. ^ Wirth, Niklaus (1976). Algoritmos + Estructuras de datos = Programas . Serie Prentice-Hall sobre computación automática. Prentice-Hall. Bibcode :1976adsp.book.....W. ISBN 978-0-13-022418-7.pág. 145
  27. ^ 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. pp. 114–118.
  28. ^ DeMaria, Rusel (15 de noviembre de 1993). The 7th Guest: The Official Strategy Guide (PDF) . Prima Games. ISBN 978-1-5595-8468-5. Recuperado el 22 de abril de 2021 .
  29. ^ "ナゾ130 クイーンの問題5".ゲームの匠(en japonés) . Consultado el 17 de septiembre de 2021 .

Lectura adicional

Enlaces externos

El Wikilibro Implementación de algoritmos tiene una página sobre el tema: Problema de N-reinas