Rompecabezas de las ocho reinas

Ajustar Compartir Imprimir Citar
Problema matemático establecido en un tablero de ajedrez
abcdefgh
8
Chessboard480.svg
f8 white queen
d7 white queen
g6 white queen
a5 white queen
h4 white queen
b3 white queen
e2 white queen
c1 white queen
8
77
66
55
44
33
22
11
abcdefgh
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 de modo que no haya dos reinas que se amenacen entre sí; por lo 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, a menudo se usa como un problema de ejemplo para varias técnicas de programación de computadoras.

El rompecabezas de las ocho reinas es un caso especial del problema más general de n reinas de colocar n reinas que no atacan en un n×n tablero de ajedrez. 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 (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. Nauck también extendió el rompecabezas 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. Gunther propuso un método que utiliza determinantes para encontrar soluciones. J.W.L. 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 de profundidad primero.

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 arreglos posibles de ocho reinas en un tablero de 8 × 8, pero solo 92 soluciones. Es posible usar atajos que reducen los requisitos computacionales o reglas generales que evitan las técnicas computacionales de fuerza bruta. Por ejemplo, aplicando una regla simple que elige una reina de cada columna, es posible reducir el número de posibilidades a 16.777.216 (es decir, 88) 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 en busca de ataques diagonales.

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

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 (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 eso). Tales soluciones tienen solo dos variantes (en sí mismas y su reflejo). 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. Las soluciones 1 y 8 tienen una línea de 4 reinas.

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 × 1018. Si el objetivo es encontrar una única solución, se puede mostrar que existen soluciones para todos los n ≥ 4 sin realizar ninguna búsqueda. 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. Sea (i, j) el cuadrado en la columna i y la fila j en la n × n tablero de ajedrez, k un número entero.

Un enfoque es

  1. Si el resto se divide n por 6 no es 2 o 3 entonces la lista es simplemente todos los números seguidos de todos los números impares no mayor que n.
  2. De lo contrario, escriba listas separadas de números iguales y extraños (2, 4, 6, 8 – 1, 3, 5, 7).
  3. Si el resto es 2, swap 1 y 3 en lista impar y mover 5 al final (3, 1, 7, 5).
  4. Si el resto es 3, mueva 2 al final de la lista uniforme y 1,3 al final de la lista impar (4, 6, 8, 2 – 5, 7, 1, 3).
  5. Apéndice lista impar a la lista uniforme y lugar 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. Siguen 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 n × n tablero, es decir, el número de conjuntos independientes de tamaño n en un n × n gráfico de la reina. El tablero de 27×27 es el tablero de orden más alto que se ha enumerado por completo. Las siguientes tablas dan el número de soluciones al problema de las n reinas, tanto fundamentales (secuencia A002562 en el OEIS) como todas (secuencia A000170 en el OEIS), para todos los casos conocidos.

nfundamentales Todos
1 1 1
2 0 0
3 0 0
4 1 2
5 2 10
6 1 4
7 6 40
8 12 92
9 46 352
10 92 724
11 341 2.680
12 1.787 14.200
13 9,233 73.712
14 45.752 365.596
15 285,053 2.279.184
16 1,846,955 14,772,512
17 11.977.939 95.815.104
18 83.263.591 666,090,624
19 621,012,754 4,968,057,848
20 4.878.666.808 39.029,188,884
21 39,333,324,973 314,666,222,712
22 336,376,244,042 2,691,008,701,644
23 3.029,242,658,210 24,233,937,684,440
24 28.439.272.956.934 227,514,171,973,736
25 275,986,683,743,434 2,207,893,435,808,352
26 2,789,712,466,510,289 22,317,699,616,364,044
27 29,363,495,934,315,694 234,907,967,154,122,528

Enumeración asintótica

En 2021, Michael Simkin demostró que para grandes números n, el número de soluciones del n problema de las reinas es aproximadamente ()0.143n)n{displaystyle (0.143n)}}. Más precisamente, el número Q()n){displaystyle {mathcal}(n)} de soluciones tiene crecimiento asintotico

Q()n)=()()1± ± o()1))ne− − α α )n{fnMicrosoft Sans Serif}(n)=(1pm o(1))ne^{-alpha })}{n}}}
α α {displaystyle alpha }o

Si se considera un tablero de ajedrez toroidal (donde las diagonales "envuelven" desde el borde superior a la parte inferior y desde el borde izquierdo a la derecha), es posible colocar n reinas en una n× × n{displaystyle ntimes n} tabla si n↑ ↑ 1,5mod6.{displaystyle nequiv 1,5mod 6.} En este caso, el número asintotico de soluciones es

T()n)=()()1+o()1))ne− − 3)n.{displaystyle T(n)=(1+o(1))ne^{-3} {n}

Problemas relacionados

Dimensiones superiores

Encuentra el número de reinas que no atacan 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 que no atacan en un espacio de ajedrez de 3×3×3), y de hecho se sabe que para cualquier k, hay dimensiones más altas donde las reinas nk no son suficientes para atacar todos los espacios.

Usando piezas distintas de 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 se ataquen dos piezas entre sí. En el caso de los caballos, una solución fácil es colocar uno en cada casilla de un color dado, ya que solo 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 las matrices de permutación de orden n.

Variaciones de ajedrez

Se pueden solicitar problemas relacionados con variaciones de ajedrez como el shogi. Por ejemplo, el problema de los reyes dragones n+k pide colocar peones de shogi k y n+ k reyes dragones que no se atacan mutuamente en un tablero de shogi n×n.

Tablas no estándar

Pólya estudió el problema de las n reinas en un tablero toroidal ("en forma de dona") y demostró que hay una solución en un n× Tablero n si y solo si n no es divisible por 2 o 3. En 2009, Pearson y Pearson poblaron algorítmicamente tableros tridimensionales (n× n×n) con n2 reinas, y propuso que los múltiplos de estos pueden producir soluciones para un grupo de cuatro versión dimensional del rompecabezas.

Domination

Dado un tablero 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 cuadrado. Para n = 8, el número de dominación de la reina es 5.

Reinas y otras piezas

Las variantes incluyen mezclar reinas con otras piezas; por ejemplo, colocando m reinas y m caballos en un tablero n×n para que ninguna pieza ataque a otra o colocando reinas y peones de modo que no haya dos reinas que se ataquen entre sí.

cuadrados mágicos

En 1992, Demirörs, Rafraf y Tanik publicaron un método para convertir algunos cuadrados mágicos en soluciones de reinas n y viceversa.

Plazas latinas

En una matriz n×n, coloque cada dígito del 1 al n en ubicaciones n en la matriz de modo que no haya dos instancias del mismo dígito en la misma fila o columna.

Cubierta exacta

Considere una matriz con una columna principal para cada uno de los rangos n del tablero, una columna principal para cada uno de los archivos n y una columna secundaria para cada de los 4n − 6 diagonales no triviales del tablero. La matriz tiene n2 filas: una para cada posible ubicación de la reina, y cada fila tiene un 1 en las columnas correspondientes al rango, archivo y rango de ese cuadrado. diagonales 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 tal 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 generalizado de cobertura exacta, del cual sudoku es otro ejemplo.

n- se termina

El problema de finalización pregunta si, dado un tablero de ajedrez n×n en el que ya se han colocado algunas reinas, es posible colocar una reina en cada fila restante de modo que no hay dos reinas que se ataquen entre sí. Esta y otras preguntas relacionadas son NP-completa y #P-completa. 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.

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 usa como un problema de ejemplo para varias técnicas de programación, incluidos enfoques no tradicionales como la programación con restricciones, la programación lógica o los algoritmos genéticos. La mayoría de las veces, se usa como un ejemplo de un problema que se puede resolver con un algoritmo recursivo, expresando el problema de las n reinas de manera inductiva en términos de agregar una sola reina a cualquier solución del problema de colocar n−1 reinas en un tablero de ajedrez n×n. La inducción llega a su fin 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 usar de una manera que es mucho más eficiente que el ingenuo algoritmo de búsqueda de fuerza bruta, que considera todos los 648 = 248 = 281 474 976 710 656 posibles ubicaciones ciegas de ocho reinas, y luego las filtra para eliminar todas las ubicaciones que colocan dos reinas en la misma casilla (¡dejando solo 64!/56! = 178,462,987,637,760 ubicaciones posibles) o en posiciones de ataque mutuo. 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, 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 solo 88 = 224 = 16 777 216 ubicaciones 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 diagonales de ataque.

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

El programa de búsqueda en profundidad de retroceso, una ligera mejora en el 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 soluciones 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 ubicaciones posibles de damas. Una mejora adicional, que examina solo 5.508 posibles reinas colocaciones, es combinar el método basado en la permutación con el método temprano método de poda: 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 efectiva en este problema.

solución de conflictos min a 8 reinas

Una alternativa a la búsqueda exhaustiva es una 'reparación iterativa' algoritmo, que normalmente comienza con todas las reinas en el tablero, por ejemplo, con una reina por columna. Luego cuenta la cantidad de conflictos (ataques) y usa una heurística para determinar cómo mejorar la ubicación de las reinas. Los 'conflictos mínimos' La heurística (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 al problema de 1.000.000 de reinas.

A diferencia de la búsqueda de retroceso descrita anteriormente, la reparación iterativa no garantiza una solución: como todos los procedimientos codiciosos, puede quedarse atascado 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 mediante la enumeración recursiva de soluciones parciales válidas, una fila a la vez. En lugar de construir posiciones de tablero completas, las diagonales y columnas bloqueadas se rastrean con operaciones bit a bit. Esto no permite la recuperación de soluciones individuales.

Programa de muestra

El siguiente programa es una traducción de la solución de Niklaus Wirth al lenguaje de programación Python, pero no utiliza 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. Mediante el uso de una rutina 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 colocaciones de reinas. 

def queens()n, i, a, b, c): si i . n: para j dentro rango()n): si j no dentro a y i+j no dentro b y i-j no dentro c: del rendimiento queens()n, i+1, a+[j] b+[i+j] c+[i-j]) más: rendimiento apara solución dentro queens()8, 0, [], [], []): impresión()solución)

En la cultura popular