Problema de las ocho reinas

Movimientos posibles de una reina en un tablero de 4×4.

Una posible solución entre las 92 posibles soluciones en un tablero de 8×8.

El problema de las ocho reinas es un pasatiempo que consiste en poner ocho reinas en el tablero de ajedrez sin que se amenacen. Fue propuesto por el ajedrecista alemán Max Bezzel en 1848.​​ En el juego del ajedrez la reina amenaza a aquellas piezas que se encuentren en su misma fila, columna o diagonal. El juego de las 8 reinas consiste en poner sobre un tablero de ajedrez ocho reinas sin que estas se amenacen entre ellas. Para resolver este problema se puede emplear un esquema vuelta atrás (o Backtracking).

Historia

El problema fue originalmente propuesto en 1848 por el ajedrecista Max Bezzel.​​​ Durante años, muchos matemáticos, incluyendo a Carl Friedich Gauss, han trabajado en él y lo han generalizado a n-reinas. Las primeras soluciones fueron ofrecidas por Franz Nauck en 1850.​​​ Nauck también se abocó a las n-reinas (en un tablero de nxn de tamaño arbitrario). En 1874, S. Günther propuso un método para hallar las soluciones usando determinantes, y J.W.L. Glaisher redefinió su aproximación.​​

Edsger Dijkstra usó este problema en 1972 para ilustrar el poder de la llamada programación estructurada. Publicó una descripción muy detallada del desarrollo del algoritmo de backtracking, "depth-first".​​

Este acertijo apareció en el popular juego de computadora de los '90 llamado "The 7th Guest".

Planteamiento del Problema

Como cada reina puede amenazar a todas las reinas que estén en la misma fila, cada una ha de situarse en una fila diferente. 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. Así cada reina estaría en la posición (i, v[i]) para i = 1-8.

Ejemplo de dos reinas amenazadas en el tablero de 4 por 4.

El vector $(3,1,6,2,8,6,4,7)$ significa que la reina 1 esta en la fila 1, columna 3; la reina 2 en la fila 2, columna 1; la reina 3 en la fila 3, columna 6; la reina 4 en la fila 4, columna 2; etc... Como se puede apreciar esta solución es incorrecta ya que la reina 3 y la 6 estarían en la misma 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? Para las posiciones sobre una misma diagonal descendente, se cumple que tienen el mismo valor $fila-columna$; mientras que para las posiciones en la misma diagonal ascendente, se cumple que tienen el mismo valor $fila+columna$. Así, si tenemos dos reinas colocadas en posiciones $(i,j)$ y $(k,l)$ entonces están en la misma diagonal si y solo si cumple:

$i-j=k-l$ o $i+j=k+l$

$j-l=i-k$ o $j-l=k-i$

Teniendo en cuenta todas estas consideraciones, podemos aplicar el esquema retroactivamente para colocar las ocho reinas de una manera realmente eficiente. Para ello, reformulamos el problema como problema de búsqueda en un árbol. Decimos que en un vector $V_{1\dots k}$ de enteros entre 1 y 8 es $k$-prometedor, para $0\leq k\leq 8$ , si ninguna de las $k$ reinas colocadas en las posiciones $(1,V_{1}),(2,V_{2}),\dots ,(k,V_{k})$ amenaza a ninguna de las otras. Las soluciones a nuestro problema se corresponden con aquellos vectores que son 8-prometedores.

Establecimiento del algoritmo

Sea $N$ el conjunto de vectores de $k$-prometedores, $0\leq k\leq 8$, sea $G=(N,A)\,$ el grafo dirigido tal que $(U,V)\in A$ si y solo si existe un entero $k$, con $0\leq k\leq 8$ tal que

• $U$ es $k$-prometedor
• $V$ es $(k+1)$-prometedor
• $U_{i}=V_{i}$ para todo $i\in \{1,\dots ,k\}$

Este grafo es un árbol. Su raíz es el vector vacío correspondiente a $k=0$. sus hojas son o bien soluciones ($k=8$), o posiciones sin salida ($k<8$). 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.

Esquema reducido del árbol de soluciones.

Hay que decidir si un vector es $k$-prometedor, sabiendo que es una extensión de un vector $(k-1)$-prometedor. Únicamente necesitamos comprobar la última reina que haya que añadir. 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.

Descripción del algoritmo

A continuación se muestra el algoritmo que soluciona nuestro problema, en el cual $sol_{1\dots 8}$ es un vector global. Para imprimir todas las soluciones, la llamada inicial es $\mathrm {reinas} (0,\emptyset ,\emptyset ,\emptyset )$.

procedimiento $\mathrm {reinas} (k,col,diag45,diag135)\,$ //$sol_{1\dots k}$ es $k$-prometedor// //$col=\{sol_{i}\mid 1\leq i\leq k\}$// //$diag45=\{sol_{i}-i+1\mid 1\leq i\leq k\}$// //$diag135=\{sol_{i}+i-1\mid 1\leq i\leq k\}$// si $k=8\,$ entonces //un vector $8$-prometedor es una solución// escribir $sol\,$ si no //explorar las extensiones $(k+1)$-prometedoras de sol// para $j\leftarrow 1$ hasta $8\,$ hacer si $j\notin col$ y $j-k\notin diag45$ y $j+k\notin diag135$ entonces $sol_{k+1}\leftarrow j$//$sol_{1\dots k+1}$ es $(k+1)$-prometedor// $\mathrm {reinas} \left(k+1,col\cup \{j\},diag45\cup \{j-k\},diag135\cup \{j+k\}\right)$

El algoritmo comprueba primero si $k=8$, si esto es cierto resulta que tenemos ante nosotros un vector 8-prometedor, lo cual indica que cumple todas las restricciones originando una solución. Si $k$ es distinto de 8, el algoritmo explora las extensiones $(k+1)$-prometedoras, para ello realiza un bucle, el cual va de 1 a 8, debido al número de reinas. 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 $k$ (buscamos $(k+1)$-prometedor) y añadimos la nueva fila, columna y diagonales al conjunto de restricciones. 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.

Implementación

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

#include <iostream>
#include <sstream>
#include <cstdio>
#include <vector>
#include <algorithm>
#define NREINAS 8 // dimensiones del tablero y número de reinas
using namespace std;
vector<int> sol;
int nro_sol=1;

inline bool contiene(const vector<int>& v, const int val)
{
    return find(v.begin(), v.end(), val) != v.end();
}

void reinas(int k, vector<int> col, vector<int> diag45, vector<int> diag135)
{
    if( k == NREINAS )
    {
	printf("%3d:", nro_sol++);
        for(int j=0; j<NREINAS; j++)
 cout << " (" << j+1 << "," << sol[j] << ")";
        cout << endl;
    }
    else
    {
        for(int j=1; j<=NREINAS; j++)
            if( !contiene(col, j) && !contiene(diag45, j-k) && !contiene(diag135, j+k) )
            {
                sol[k] = j;

                col.push_back(j);
                diag45.push_back(j-k);
                diag135.push_back(j+k);

                reinas(k+1,col, diag45, diag135);

                col.pop_back();
                diag45.pop_back();
                diag135.pop_back();
            }
    }
}

int main() {
    cout << "SOLUCIONES AL PROBLEMA DE LAS " << NREINAS << " REINAS"<<endl;
    sol.resize(NREINAS);
    reinas(0, vector<int>(), vector<int>(), vector<int>());

    return 0;
}

El problema de las n reinas

El problema de las ocho reinas se puede plantear de modo general como problema de las $n$ reinas. El problema consistiría en colocar $n$ reinas en un tablero de ajedrez de $n\times n$ de tal manera que ninguna de las reinas quede atacando a otras.

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

El tablero de 27x27 es el más grande hasta ahora numerado.​

Número de soluciones

n	distintas	todas las soluciones:
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

Simetrías escondidas

Además de las simetrías relativas a la colocación de las reinas y su reflejo o giro se da otra no tan evidente que conecta las soluciones entre un tablero de lado (n) y el tablero siguiente de lado (n+1). Partiendo del conjunto completo de soluciones para n casillas de lado, contando las veces que cada casilla aparece en las mismas, resulta:

para n:6	para n:7	para n:8	para n:9
0 1 1 1 1 0 1 0 1 1 0 1 1 1 0 0 1 1 1 1 0 0 1 1 1 0 1 1 0 1 0 1 1 1 1 0	4 7 6 6 6 7 4 7 4 6 6 6 4 7 6 6 6 4 6 6 6 6 6 4 8 4 6 6 6 6 6 4 6 6 6 7 4 6 6 6 4 7 4 7 6 6 6 7 4	4 8 16 18 18 16 8 4 8 16 14 8 8 14 16 8 16 14 4 12 12 4 14 16 18 8 12 8 8 12 8 18 18 8 12 8 8 12 8 18 16 14 4 12 12 4 14 16 8 16 14 8 8 14 16 8 4 8 16 18 18 16 8 4	28 30 47 44 54 44 47 30 28 30 32 44 48 44 48 44 32 30 47 44 28 38 38 38 28 44 47 44 48 38 36 20 36 38 48 44 54 44 38 20 40 20 38 44 54 44 48 38 36 20 36 38 48 44 47 44 28 38 38 38 28 44 47 30 32 44 48 44 48 44 32 30 28 30 47 44 54 44 47 30 28

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:

para n:6	para n:7	para n:8	para n:9
0 1 1 1 1 0 :4 1 0 1 1 0 1 :4 1 1 0 0 1 1 :4 1 1 0 0 1 1 :4 1 0 1 1 0 1 :4 0 1 1 1 1 0 :4 :4 :4 :4 :4 :4 :4 :0 s = Soluciones = 4 d = Suma diagonal = 0 s - d. = [4]	4 7 6 6 6 7 4 :40 7 4 6 6 6 4 7 :40 6 6 6 4 6 6 6 :40 6 6 4 8 4 6 6 :40 6 6 6 4 6 6 6 :40 7 4 6 6 6 4 7 :40 [4] 7 6 6 6 7 4 :40 :40 :40 :40 :40 :40 :40 :40 :36 s = Soluciones = 40 d = suma diagonal = 36 s - d = [4]	4 8 16 18 18 16 8 4 :92 8 16 14 8 8 14 16 8 :92 16 14 4 12 12 4 14 16 :92 18 8 12 8 8 12 8 18 :92 18 8 12 8 8 12 8 18 :92 16 14 4 12 12 4 14 16 :92 8 16 14 8 8 14 16 8 :92 [4] 8 16 18 18 16 8 4 :92 :92 :92 :92 :92 :92 :92 :92 :92 :64 s = Soluciones = 92 d = Suma diagonal = 64 s - d = [28]	28 30 47 44 54 44 47 30 28 :352 30 32 44 48 44 48 44 32 30 :352 47 44 28 38 38 38 28 44 47 :352 44 48 38 36 20 36 38 48 44 :352 54 44 38 20 40 20 38 44 54 :352 44 48 38 36 20 36 38 48 44 :352 47 44 28 38 38 38 28 44 47 :352 30 32 44 48 44 48 44 32 30 :352 [28] 30 47 44 54 44 47 30 28 :352 :352 :352 :352 :352 :352 :352 :352 :352 :352 :288 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. Resultando una conexión entre el tablero de n casillas y el de n+1 casillas. Para conjunto de soluciones completas:

Tablero de:	Suma línea y soluciones posibles	Suma diagonal	esquinas tablero n+1 x n+1 resta suma línea - suma diagonal
6 x 6	4	0	Esquinas tablero 7 x 7 = 4
7 x 7	40	36	Esquinas tablero 8 x 8 = 4
8 x 8	92	64	Esquinas tablero 9 x 9 = 28
9 x 9	352	288	Esquinas tablero 10 x 10 = 64
10 x 10	724	628	Esquinas tablero 11 x 11 = 96
11 x 11	2680	2180	Esquinas tablero 12 x 12 = 500
12 x 12	14200	11440	Esquinas tablero 13 x 13 = 2760
13 x 13	73712	61820	Esquinas tablero 14 x 14 = 11892
14 x 14	365596	296080	Esquinas tablero 15 x 15 = 69516
15 x 15	...

De hallar la relación entre los valores que resultan en las esquinas y el número total de soluciones de cada tablero o su tamaño, se podría encontrar los resultados correctos de cualquier valor de n.

Soluciones al problema de las ocho reinas

El problema de las ocho reinas tiene 92 soluciones, de las cuales 12 son esencialmente distintas, es decir, las 92 soluciones existentes se pueden obtener a partir de operaciones de simetría de rotación y reflexión de las 12 soluciones únicas, que se muestran a continuación:

Solución única 1	Solución única 2	Solución única 3
Solución única 4	Solución única 5	Solución única 6
Solución única 7	Solución única 8	Solución única 9
Solución única 10	Solución única 11	Solución única 12

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 (es decir, ₆₄C₈) posibles arreglos de ocho reinas en un tablero de 8x8, pero solo 92 soluciones. 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, 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 revisan para detectar ataques diagonales.

Existen muchas soluciones computacionales al problema de las 8 reinas, que hacen uso de las llamadas recursivas, en cualquier lenguaje de programación, lo que demuestra la alta popularidad que tiene este problema dentro del mundo de la programación de computadoras.

El curioso número Š(n)

Si enumeramos las casillas de un tablero de ajedrez de cualquier tamaño (n x n) con los números naturales, empezando de izquierda a derecha y de arriba hacia abajo, encontramos el curioso caso del número Š(n), el cual siempre es una constante para un tablero dado de n x n lados y nos dice cuanto será la sumatoria de las casillas en donde se pueden ubicar las n reinas para todas las soluciones de dicho tablero. El número Š(n) viene dado por la fórmula:

Š(n) = $(n^{3}+n)/2$

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

Š(4) = $(4^{3}+4)/2$

Calculando para la primera solución Š1 = 2+8+9+15 = 34

Calculando para la segunda solución Š2 = 3+5+12+14 = 34

A continuación se da el ejemplo de las diez soluciones de un tablero de 5 x 5 (marcadas en las casillas negras), es decir n = 5

Š(5) = $(5^{3}+5)/2$ = 65

Calculando para la primera solución Š1 = 1+8+15+17+24 = 65

Calculando para la segunda solución Š2 = 1+9+12+20+23 = 65

Calculando para la tercera solución Š3 = 2+9+11+18+25 = 65

Calculando para la cuarta solución Š4 = 2+10+13+16+24 = 65

Calculando para la quinta solución Š5 = 3+6+14+17+25 = 65

Calculando para la sexta solución Š6 = 3+10+12+19+21 = 65

Calculando para la séptima solución Š7 = 4+6+13+20+22 = 65

Calculando para la octava solución Š8 = 4+7+15+18+21 = 65

Calculando para la novena solución Š9 = 5+7+14+16+23 = 65

Calculando para la décima solución Š10 = 5+8+11+19+22 = 65

Sin embargo, este número aplica para cualquier conjunto de celdas siempre que no se repitan columnas ni filas. 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).

La secuencia de Š(n) para tableros de 2x2 en adelante es {5, 15, 34, 65, 111, 175, 260, ...}, fue descubierta por Paul Muljadi en 2005 y coincide con las constantes mágicas (secuencia A006003 en la OEIS).

Referencias

• Gómez Campos, Luis Ernesto (2004). Across the Board: The Mathematics of Chess Problems. Princeton: Princeton University Press. ISBN 0-691-11503-6. 
• Brassard, Gilles; Bratley, Paul (1997). «Exploración de grafos». Fundamentos de Algoritmia. Madrid: Prentice Hall. ISBN 84-89660-00-X. 

Véase también

• Ajedrez
• Polinomio de torre

Enlaces externos

• Weisstein, Eric W. «QueensProblem». En Weisstein, Eric W, ed. MathWorld (en inglés). Wolfram Research. 
• Solutions to the 8-Queens Problem
• Walter Koster's N-Queens Page
• Durango Bill's N-Queens Page
• On-line Guide to Constraint Programming

Enlaces a soluciones

• Solución interactiva al problema de las 8 reinas en VB.NET y en C#
• Método general n reinas con implementación en java
• N-Queens solvers in many programming languages
• Find your own solution Archivado el 12 de marzo de 2008 en Wayback Machine.
• J Somers N-Queen code
• Atari BASIC
• Genetic algorithms
• Java
• Standard ML
• Quirkasaurus' 8 Queens Solution
• LISP solution for N-Queens Problem
• Javascript solution for 8-Queens Problem
• Las ocho reinas. Solución
• Solución del problema de las ocho reinas (en el Dept. de Matemática Aplicada de la Universidad de Valencia).
• The N-Queens Problem
• The Q27 Project

• Datos: Q623317
• Multimedia: Eight queens position / Q623317