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. Fue propuesto por el ajedrecista alemán Max Bezzel en 1848[cita requerida]. 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 emplearemos un esquema vuelta atrás (o Backtracking).

Movimientos posibles de una reina en un tablero de 4×4.
Chess zhor 26.png
Chess zver 26.png a8 __ b8 __ c8 __ d8 ql e8 __ f8 __ g8 __ h8 __ Chess zver 26.png
a7 __ b7 __ c7 __ d7 __ e7 __ f7 __ g7 ql h7 __
a6 __ b6 __ c6 ql d6 __ e6 __ f6 __ g6 __ h6 __
a5 __ b5 __ c5 __ d5 __ e5 __ f5 __ g5 __ h5 ql
a4 __ b4 ql c4 __ d4 __ e4 __ f4 __ g4 __ h4 __
a3 __ b3 __ c3 __ d3 __ e3 ql f3 __ g3 __ h3 __
a2 ql b2 __ c2 __ d2 __ e2 __ f2 __ g2 __ h2 __
a1 __ b1 __ c1 __ d1 __ e1 __ f1 ql g1 __ h1 __
Chess zhor 26.png
Una posible solución entre las 92 posibles soluciones en un tablero de 8×8.

HistoriaEditar

El problema fue originalmente propuesto en 1848 por el ajedrecista Max Bezzel. Durante años, muchos matemáticos, incluyendo a Gauss y a Georg Cantor, 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 ProblemaEditar

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   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  ; mientras que para las posiciones en la misma diagonal ascendente, se cumple que tienen el mismo valor  . Así, si tenemos dos reinas colocadas en posiciones   y   entonces están en la misma diagonal si y solo si cumple:

  o  

  o  

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   de enteros entre 1 y 8 es  -prometedor, para   , si ninguna de las   reinas colocadas en las posiciones   amenaza a ninguna de las otras. Las soluciones a nuestro problema se corresponden con aquellos vectores que son 8-prometedores.

Establecimiento del algoritmoEditar

Sea   el conjunto de vectores de  -prometedores,  , sea   el grafo dirigido tal que   si y solo si existe un entero  , con   tal que

  •   es  -prometedor
  •   es  -prometedor
  •   para todo  

Este grafo es un árbol. Su raíz es el vector vacío correspondiente a  . sus hojas son o bien soluciones ( ), o posiciones sin salida ( ). 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  -prometedor, sabiendo que es una extensión de un vector  -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 algoritmoEditar

A continuación se muestra el algoritmo que soluciona nuestro problema, en el cual   es un vector global. Para imprimir todas las soluciones, la llamada inicial es  .

procedimiento  

//  es  -prometedor//
// //
// //
// //
si   entonces //un vector  -prometedor es una solución//
escribir  
si no //explorar las extensiones  -prometedoras de sol//
para   hasta   hacer
si   y   y   entonces
 //  es  -prometedor//
 

El algoritmo comprueba primero si  , 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   es distinto de 8, el algoritmo explora las extensiones  -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   (buscamos  -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ónEditar

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 reinasEditar

El problema de las ocho reinas se puede plantear de modo general como problema de las   reinas. El problema consistiría en colocar   reinas en un tablero de ajedrez de   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.[1]

Número de solucionesEditar

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 escondidasEditar

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 linea - 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 reinasEditar

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 traslaciones, simetrías y rotaciones de las 12 soluciones únicas, que se muestran a continuación:

Existen muchas soluciones computacionales al problema de las 8 reinas, las más populares están en lenguaje C/C++ y la mayoría hace uso de las llamadas recursivas, pero en general es posible conseguir soluciones en otros lenguejes como Perl, Java, JavaScript, en Visual Basic NET y muchos otros más, lo que demuestra la alta popularidad que tiene este problema dentro del mundo de la programación de computadoras.

ReferenciasEditar

  1. Preußer, Thomas B. (26 de junio de 2019), 27-Queens Puzzle: Massively Parellel Enumeration and Solution Counting: preusser/q27, consultado el 21 de septiembre de 2019 .

Véase tambiénEditar

Enlaces externosEditar

Enlaces a solucionesEditar