Problema de las ocho reinas

El problema de las ocho reinas es un pasatiempo que consiste en poner ocho reinas en el tablero de ajedrez sin que se amenacen.

[1]​[2]​ En el juego del ajedrez la reina amenaza a aquellas piezas que se encuentren en su misma fila, columna o diagonal.

Para resolver este problema se puede emplear un esquema vuelta atrás (o Backtracking).

[1]​[2]​[3]​ Durante años, muchos matemáticos, incluyendo a Carl Friedich Gauss, han trabajado en él y lo han generalizado a n-reinas.

En 1874, S. Günther propuso un método para hallar las soluciones usando determinantes, y J.W.L.

[3]​[5]​ Edsger Dijkstra usó este problema en 1972 para ilustrar el poder de la llamada programación estructurada.

Podemos representar las 8 reinas mediante un vector[1-8], teniendo en cuenta que cada índice del vector representa una fila y el valor una columna.

Por tanto el vector correspondería a una permutación de los ocho primeros números enteros.

El problema de las filas y columnas lo tenemos resuelto, pero ¿qué ocurre con las diagonales?

Teniendo en cuenta todas estas consideraciones, podemos aplicar el esquema retroactivamente para colocar las ocho reinas de una manera realmente eficiente.

Las soluciones a nuestro problema se corresponden con aquellos vectores que son 8-prometedores.

Las soluciones del problema de las ocho reinas se pueden obtener explorando este árbol.

Sin embargo, no generamos explícitamente el árbol para explorarlo después.

Los nodos se van generando y abandonando en el transcurso de la exploración mediante un recorrido en profundidad.

Esto se puede acelerar si asociamos a cada nodo prometedor el conjunto de columnas, el de diagonales positivas (a 45 grados) y el de diagonales negativas (a 135 grados) controladas por las reinas que ya están puestas.

En este bucle se comprueba si entran en jaque las reinas colocadas en el tablero.

Si no entran en jaque, se realiza una recurrencia en la cual incrementamos

Al realizar la recurrencia hemos añadido al vector sol una nueva reina, que no entra en jaque con ninguna de las anteriores.

Además, hemos incrementado el conjunto de restricciones añadiendo una nueva fila, columna y diagonales (una positiva y otra negativa) prohibidas.

A continuación se muestra una posible implementación del anterior algoritmo en C++.

Su análisis y solución es isomorfo al de las ocho reinas.

Partiendo del conjunto completo de soluciones para n casillas de lado, contando las veces que cada casilla aparece en las mismas, resulta: Cuando el conjunto de soluciones es correcto para n, se da la simetría completa, tanto vertical como horizontalmente.

Ésta simetría puede darse con un conjunto de soluciones incompleto.

Sin embargo, la suma de cada fila y de cada columna, si el conjunto de soluciones está completo da como resultado el número total de soluciones posibles: s = Soluciones = 4 d = Suma diagonal = 0 s - d. = [4] s = Soluciones = 40 d = suma diagonal = 36 s - d = [4] s = Soluciones = 92 d = Suma diagonal = 64 s - d = [28] s = Soluciones = 352 d = Suma diagonal = 288 s - d = [64] Por último, la resta entre las soluciones de un tablero y la suma de la diagonal correspondientes coincide con el valor que aparece en las esquinas del tablero siguiente.

Es posible utilizar atajos que reduzcan los requisitos computacionales o reglas prácticas que eviten técnicas computacionales de fuerza bruta.

Por ejemplo, al aplicar una regla simple que restringe a cada reina a una sola columna (o fila), aunque todavía se considera fuerza bruta, 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 revisan para detectar ataques diagonales.

El número Š(n) viene dado por la fórmula: A continuación se da el ejemplo de las dos soluciones de un tablero de 4 x 4 (marcadas en las casillas negras), es decir n = 4 Calculando para la primera solución Š1 = 2+8+9+15 = 34 Calculando para la segunda solución Š2 = 3+5+12+14 = 34

Por ejemplo: Šdiagonal = 1 + 7 + 13 +19 +25 = 65 A continuación se da el número Š hasta el tablero n = 10 (comprobado con algoritmos computacionalmente para todas las soluciones hasta tablero de  11 por 11 que tiene 2.680 soluciones).