Problema de las ocho reinas

De Wikipedia, la enciclopedia libre
Saltar a: navegación, búsqueda
Movimientos posibles de una reina en un tablero de 4x4.
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 8x8

El problema de las ocho reinas es un pasatiempo en el que se colocan ocho reinas 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 colocar 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).

Historia[editar]

El problema fue originalmente propuesto en 1848 por el ajedrecista Max Bezzel, y durante los años, muchos matemáticos, incluyendo a Gauss y a Georg Cantor, han trabajado en este problema 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. Él publicó una descripción altamente 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[editar]

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 columna 3, fila1; la reina 2 en la columna 1, fila 2; la reina 3 en la columna 6, fila 3; la reina 4 en la columna 2, fila 4; etc... Como se puede apreciar esta solución es incorrecta ya que estarían la reina 3 y la 6 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 cubierto, ¿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 consideracioneas, podemos aplicar el esquema de retroactivamente para implementar 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\leq8 , 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[editar]

Sea N el conjunto de vectores de k-prometedores, 0\leq k\leq8, 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\leq8 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. Este 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) controlados por las reinas que ya están puestas.

Descripción del algoritmo[editar]

A continuación se muestra el algoritmo que arroja la solución de nuestro problema, en el cual sol_{1\dots8} es un vector global. Para imprimir todas las soluciones, la llamada inicial es \mathrm{reinas}(0,\empty,\empty,\empty).

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\mid1\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 la cual 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[editar]

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";
    sol.resize(NREINAS);
    reinas(0, vector<int>(), vector<int>(), vector<int>());
 
    return 0;
}

El problema de las n reinas[editar]

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 otra.

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

Número de soluciones[editar]

n: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 24 25 26
única: 1 0 0 1 2 1 6 12 46 92 341 1,787 9.233 45.752 28.439.272.956.934 275.986.683.743.434 2.789.712.466.510.289
distinta: 1 0 0 2 10 4 40 92 352 724 2.680 14.200 73.712 365.596 227.514.171.973.736 2.207.893.435.808.352 22.317.699.616.364.044 87

Soluciones al problema de las ocho reinas[editar]

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

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
Solución única 1
Chess zhor 26.png
Chess zver 26.png a8 __ b8 __ c8 __ d8 __ e8 ql f8 __ g8 __ h8 __ Chess zver 26.png
a7 __ b7 ql c7 __ d7 __ e7 __ f7 __ g7 __ h7 __
a6 __ b6 __ c6 __ d6 ql e6 __ f6 __ g6 __ h6 __
a5 __ b5 __ c5 __ d5 __ e5 __ f5 __ g5 ql h5 __
a4 __ b4 __ c4 ql d4 __ e4 __ f4 __ g4 __ h4 __
a3 __ b3 __ c3 __ d3 __ e3 __ f3 __ g3 __ h3 ql
a2 __ b2 __ c2 __ d2 __ e2 __ f2 ql g2 __ h2 __
a1 ql b1 __ c1 __ d1 __ e1 __ f1 __ g1 __ h1 __
Chess zhor 26.png
Solución única 2
Chess zhor 26.png
Chess zver 26.png a8 __ b8 __ c8 __ d8 ql e8 __ f8 __ g8 __ h8 __ Chess zver 26.png
a7 __ b7 ql c7 __ d7 __ e7 __ f7 __ g7 __ h7 __
a6 __ b6 __ c6 __ d6 __ e6 __ f6 __ g6 ql h6 __
a5 __ b5 __ c5 ql d5 __ e5 __ f5 __ g5 __ h5 __
a4 __ b4 __ c4 __ d4 __ e4 __ f4 ql g4 __ h4 __
a3 __ b3 __ c3 __ d3 __ e3 __ f3 __ g3 __ h3 ql
a2 __ b2 __ c2 __ d2 __ e2 ql f2 __ g2 __ h2 __
a1 ql b1 __ c1 __ d1 __ e1 __ f1 __ g1 __ h1 __
Chess zhor 26.png
Solución única 3
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 ql g7 __ h7 __
a6 __ b6 __ c6 __ d6 __ e6 __ f6 __ g6 __ h6 ql
a5 __ b5 __ c5 ql d5 __ e5 __ f5 __ g5 __ h5 __
a4 ql b4 __ c4 __ d4 __ e4 __ f4 __ g4 __ h4 __
a3 __ b3 __ c3 __ d3 __ e3 __ f3 __ g3 ql h3 __
a2 __ b2 __ c2 __ d2 __ e2 ql f2 __ g2 __ h2 __
a1 __ b1 ql c1 __ d1 __ e1 __ f1 __ g1 __ h1 __
Chess zhor 26.png
Solución única 4
Chess zhor 26.png
Chess zver 26.png a8 __ b8 __ c8 ql d8 __ e8 __ f8 __ g8 __ h8 __ Chess zver 26.png
a7 __ b7 __ c7 __ d7 __ e7 __ f7 ql g7 __ h7 __
a6 __ b6 __ c6 __ d6 __ e6 __ f6 __ g6 __ h6 ql
a5 ql b5 __ c5 __ d5 __ e5 __ f5 __ g5 __ h5 __
a4 __ b4 __ c4 __ d4 ql e4 __ f4 __ g4 __ h4 __
a3 __ b3 __ c3 __ d3 __ e3 __ f3 __ g3 ql h3 __
a2 __ b2 __ c2 __ d2 __ e2 ql f2 __ g2 __ h2 __
a1 __ b1 ql c1 __ d1 __ e1 __ f1 __ g1 __ h1 __
Chess zhor 26.png
Solución única 5
Chess zhor 26.png
Chess zver 26.png a8 __ b8 __ c8 __ d8 __ e8 ql f8 __ g8 __ h8 __ Chess zver 26.png
a7 __ b7 __ c7 ql d7 __ e7 __ f7 __ g7 __ h7 __
a6 __ b6 __ c6 __ d6 __ e6 __ f6 __ g6 __ h6 ql
a5 __ b5 __ c5 __ d5 ql e5 __ f5 __ g5 __ h5 __
a4 __ b4 __ c4 __ d4 __ e4 __ f4 __ g4 ql h4 __
a3 ql b3 __ c3 __ d3 __ e3 __ f3 __ g3 __ h3 __
a2 __ b2 __ c2 __ d2 __ e2 __ f2 ql g2 __ h2 __
a1 __ b1 ql c1 __ d1 __ e1 __ f1 __ g1 __ h1 __
Chess zhor 26.png
Solución única 6
Chess zhor 26.png
Chess zver 26.png a8 __ b8 __ c8 __ d8 __ e8 ql f8 __ g8 __ h8 __ Chess zver 26.png
a7 __ b7 __ c7 __ d7 __ e7 __ f7 __ g7 ql h7 __
a6 __ b6 __ c6 __ d6 ql e6 __ f6 __ g6 __ h6 __
a5 ql b5 __ c5 __ d5 __ e5 __ f5 __ g5 __ h5 __
a4 __ b4 __ c4 ql d4 __ e4 __ f4 __ g4 __ h4 __
a3 __ b3 __ c3 __ d3 __ e3 __ f3 __ g3 __ h3 ql
a2 __ b2 __ c2 __ d2 __ e2 __ f2 ql g2 __ h2 __
a1 __ b1 ql c1 __ d1 __ e1 __ f1 __ g1 __ h1 __
Chess zhor 26.png
Solución única 7
Chess zhor 26.png
Chess zver 26.png a8 __ b8 __ c8 __ d8 ql e8 __ f8 __ g8 __ h8 __ Chess zver 26.png
a7 ql b7 __ c7 __ d7 __ e7 __ f7 __ g7 __ h7 __
a6 __ b6 __ c6 __ d6 __ e6 ql f6 __ g6 __ h6 __
a5 __ b5 __ c5 __ d5 __ e5 __ f5 __ g5 __ h5 ql
a4 __ b4 __ c4 __ d4 __ e4 __ f4 ql g4 __ h4 __
a3 __ b3 __ c3 ql d3 __ e3 __ f3 __ g3 __ h3 __
a2 __ b2 __ c2 __ d2 __ e2 __ f2 __ g2 ql h2 __
a1 __ b1 ql c1 __ d1 __ e1 __ f1 __ g1 __ h1 __
Chess zhor 26.png
Solución única 8
Chess zhor 26.png
Chess zver 26.png a8 __ b8 __ c8 ql d8 __ e8 __ f8 __ g8 __ h8 __ Chess zver 26.png
a7 __ b7 __ c7 __ d7 __ e7 __ f7 ql g7 __ h7 __
a6 __ b6 __ c6 __ d6 ql e6 __ f6 __ g6 __ h6 __
a5 ql b5 __ c5 __ d5 __ e5 __ f5 __ g5 __ h5 __
a4 __ b4 __ c4 __ d4 __ e4 __ f4 __ g4 __ h4 ql
a3 __ b3 __ c3 __ d3 __ e3 ql f3 __ g3 __ h3 __
a2 __ b2 __ c2 __ d2 __ e2 __ f2 __ g2 ql h2 __
a1 __ b1 ql c1 __ d1 __ e1 __ f1 __ g1 __ h1 __
Chess zhor 26.png
Solución única 9
Chess zhor 26.png
Chess zver 26.png a8 __ b8 __ c8 __ d8 __ e8 __ f8 ql g8 __ h8 __ Chess zver 26.png
a7 __ b7 ql c7 __ d7 __ e7 __ f7 __ g7 __ h7 __
a6 __ b6 __ c6 __ d6 __ e6 __ f6 __ g6 ql h6 __
a5 ql b5 __ c5 __ d5 __ e5 __ f5 __ g5 __ h5 __
a4 __ b4 __ c4 __ d4 ql e4 __ f4 __ g4 __ h4 __
a3 __ b3 __ c3 __ d3 __ e3 __ f3 __ g3 __ h3 ql
a2 __ b2 __ c2 __ d2 __ e2 ql f2 __ g2 __ h2 __
a1 __ b1 __ c1 ql d1 __ e1 __ f1 __ g1 __ h1 __
Chess zhor 26.png
Solución única 10
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 ql b6 __ c6 __ d6 __ e6 __ f6 __ g6 __ h6 __
a5 __ b5 __ c5 __ d5 __ e5 __ f5 __ g5 __ h5 ql
a4 __ b4 __ c4 __ d4 __ e4 ql f4 __ g4 __ h4 __
a3 __ b3 ql c3 __ d3 __ e3 __ f3 __ g3 __ h3 __
a2 __ b2 __ c2 __ d2 __ e2 __ f2 ql g2 __ h2 __
a1 __ b1 __ c1 ql d1 __ e1 __ f1 __ g1 __ h1 __
Chess zhor 26.png
Solución única 11
Chess zhor 26.png
Chess zver 26.png a8 __ b8 __ c8 __ d8 __ e8 __ f8 ql g8 __ h8 __ Chess zver 26.png
a7 __ b7 __ c7 __ d7 ql e7 __ f7 __ g7 __ h7 __
a6 __ b6 __ c6 __ d6 __ e6 __ f6 __ g6 ql h6 __
a5 ql b5 __ c5 __ d5 __ e5 __ f5 __ g5 __ h5 __
a4 __ b4 __ c4 __ d4 __ e4 __ f4 __ g4 __ h4 ql
a3 __ b3 ql c3 __ d3 __ e3 __ f3 __ g3 __ h3 __
a2 __ b2 __ c2 __ d2 __ e2 ql f2 __ g2 __ h2 __
a1 __ b1 __ c1 ql d1 __ e1 __ f1 __ g1 __ h1 __
Chess zhor 26.png
Solución única 12

Referencias[editar]

  • Watkins, John J. (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[editar]

Enlaces externos[editar]

Enlaces a soluciones[editar]