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.

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

Historia

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 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 ${\displaystyle (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 ${\displaystyle fila-columna}$ ; mientras que para las posiciones en la misma diagonal ascendente, se cumple que tienen el mismo valor ${\displaystyle fila+columna}$ . Así, si tenemos dos reinas colocadas en posiciones ${\displaystyle (i,j)}$  y ${\displaystyle (k,l)}$  entonces están en la misma diagonal si y solo si cumple:

${\displaystyle i-j=k-l}$  o ${\displaystyle i+j=k+l}$ 

${\displaystyle j-l=i-k}$  o ${\displaystyle 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 ${\displaystyle V_{1\dots k}}$  de enteros entre 1 y 8 es ${\displaystyle k}$ -prometedor, para ${\displaystyle 0\leq k\leq 8}$  , si ninguna de las ${\displaystyle k}$  reinas colocadas en las posiciones ${\displaystyle (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 ${\displaystyle N}$  el conjunto de vectores de ${\displaystyle k}$ -prometedores, ${\displaystyle 0\leq k\leq 8}$ , sea ${\displaystyle G=(N,A)\,}$  el grafo dirigido tal que ${\displaystyle (U,V)\in A}$  si y solo si existe un entero ${\displaystyle k}$ , con ${\displaystyle 0\leq k\leq 8}$  tal que

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

Este grafo es un árbol. Su raíz es el vector vacío correspondiente a ${\displaystyle k=0}$ . sus hojas son o bien soluciones (${\displaystyle k=8}$ ), o posiciones sin salida (${\displaystyle 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 ${\displaystyle k}$ -prometedor, sabiendo que es una extensión de un vector ${\displaystyle (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 ${\displaystyle sol_{1\dots 8}}$  es un vector global. Para imprimir todas las soluciones, la llamada inicial es ${\displaystyle \mathrm {reinas} (0,\emptyset ,\emptyset ,\emptyset )}$ .

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

El algoritmo comprueba primero si ${\displaystyle 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 ${\displaystyle k}$  es distinto de 8, el algoritmo explora las extensiones ${\displaystyle (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 ${\displaystyle k}$  (buscamos ${\displaystyle (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 ${\displaystyle n}$  reinas. El problema consistiría en colocar ${\displaystyle n}$  reinas en un tablero de ajedrez de ${\displaystyle 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.^[1]​

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 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 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 traslaciones, simetrías y rotaciones 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	Agosto 04, 2021 Últimos artículos Agosto 04, 2021 Thomisus vulnerabilis Agosto 04, 2021 Thomisus zyuzini Agosto 03, 2021 Thompsonella Agosto 01, 2021 Thomson MO5 Agosto 03, 2021 Thor: Love and Thunder Agosto 03, 2021 Thor (cohete) Agosto 03, 2021 Thor Vilhjálmsson Agosto 02, 2021 Thornton (Colorado) Agosto 04, 2021 Thornber Agosto 03, 2021 Thorncroftia Más leído Agosto 04, 2021 Lucio Domicio Enobarbo (cónsul 94 a. C.) Agosto 04, 2021 Lucio Emilio Mamercino Agosto 04, 2021 Lucio Emilio Paulo (cónsul 50 a. C.) Agosto 03, 2021 Lucio Estertinio Avito Agosto 03, 2021 Lucio Escribonio Libón problema, ocho, reinas, problema, ocho, reinas, pasatiempo, consiste, poner, ocho, reinas, tablero, ajedrez, amenacen, propuesto, ajedrecista, alemán, bezzel, 1848, cita, requerida, juego, ajedrez, reina, amenaza, aquellas, piezas, encuentren, misma, fila, col. 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 aleman 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 atras o Backtracking Movimientos posibles de una reina en un tablero de 4 4 Una posible solucion entre las 92 posibles soluciones en un tablero de 8 8 Indice 1 Historia 2 Planteamiento del Problema 2 1 Establecimiento del algoritmo 2 2 Descripcion del algoritmo 2 3 Implementacion 3 El problema de las n reinas 3 1 Numero de soluciones 4 Simetrias escondidas 5 Soluciones al problema de las ocho reinas 6 Referencias 7 Vease tambien 8 Enlaces externos 8 1 Enlaces a solucionesHistoria EditarEl problema fue originalmente propuesto en 1848 por el ajedrecista Max Bezzel Durante anos muchos matematicos incluyendo a Gauss y a Georg Cantor han trabajado en el y lo han generalizado a n reinas Las primeras soluciones fueron ofrecidas por Franz Nauck en 1850 Nauck tambien se aboco a las n reinas en un tablero de nxn de tamano arbitrario En 1874 S Gunther propuso un metodo para hallar las soluciones usando determinantes y J W L Glaisher redefinio su aproximacion Edsger Dijkstra uso este problema en 1972 para ilustrar el poder de la llamada programacion estructurada Publico una descripcion muy detallada del desarrollo del algoritmo de backtracking depth first Este acertijo aparecio en el popular juego de computadora de los 90 llamado The 7th Guest Planteamiento del Problema EditarComo cada reina puede amenazar a todas las reinas que esten 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 indice del vector representa una fila y el valor una columna Asi cada reina estaria en la posicion 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 displaystyle 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 solucion es incorrecta ya que la reina 3 y la 6 estarian en la misma columna Por tanto el vector corresponderia a una permutacion de los ocho primeros numeros enteros El problema de las filas y columnas lo tenemos resuelto pero que ocurre con las diagonales Para las posiciones sobre una misma diagonal descendente se cumple que tienen el mismo valor f i l a c o l u m n a displaystyle fila columna mientras que para las posiciones en la misma diagonal ascendente se cumple que tienen el mismo valor f i l a c o l u m n a displaystyle fila columna Asi si tenemos dos reinas colocadas en posiciones i j displaystyle i j y k l displaystyle k l entonces estan en la misma diagonal si y solo si cumple i j k l displaystyle i j k l o i j k l displaystyle i j k l j l i k displaystyle j l i k o j l k i displaystyle 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 busqueda en un arbol Decimos que en un vector V 1 k displaystyle V 1 dots k de enteros entre 1 y 8 es k displaystyle k prometedor para 0 k 8 displaystyle 0 leq k leq 8 si ninguna de las k displaystyle k reinas colocadas en las posiciones 1 V 1 2 V 2 k V k displaystyle 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 displaystyle N el conjunto de vectores de k displaystyle k prometedores 0 k 8 displaystyle 0 leq k leq 8 sea G N A displaystyle G N A el grafo dirigido tal que U V A displaystyle U V in A si y solo si existe un entero k displaystyle k con 0 k 8 displaystyle 0 leq k leq 8 tal que U displaystyle U es k displaystyle k prometedor V displaystyle V es k 1 displaystyle k 1 prometedor U i V i displaystyle U i V i para todo i 1 k displaystyle i in 1 dots k Este grafo es un arbol Su raiz es el vector vacio correspondiente a k 0 displaystyle k 0 sus hojas son o bien soluciones k 8 displaystyle k 8 o posiciones sin salida k lt 8 displaystyle k lt 8 Las soluciones del problema de las ocho reinas se pueden obtener explorando este arbol Sin embargo no generamos explicitamente el arbol para explorarlo despues Los nodos se van generando y abandonando en el transcurso de la exploracion mediante un recorrido en profundidad Esquema reducido del arbol de soluciones Hay que decidir si un vector es k displaystyle k prometedor sabiendo que es una extension de un vector k 1 displaystyle k 1 prometedor Unicamente necesitamos comprobar la ultima reina que haya que anadir 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 estan puestas Descripcion del algoritmo Editar A continuacion se muestra el algoritmo que soluciona nuestro problema en el cual s o l 1 8 displaystyle sol 1 dots 8 es un vector global Para imprimir todas las soluciones la llamada inicial es r e i n a s 0 displaystyle mathrm reinas 0 emptyset emptyset emptyset procedimiento r e i n a s k c o l d i a g 45 d i a g 135 displaystyle mathrm reinas k col diag45 diag135 s o l 1 k displaystyle sol 1 dots k es k displaystyle k prometedor c o l s o l i 1 i k displaystyle col sol i mid 1 leq i leq k d i a g 45 s o l i i 1 1 i k displaystyle diag45 sol i i 1 mid 1 leq i leq k d i a g 135 s o l i i 1 1 i k displaystyle diag135 sol i i 1 mid 1 leq i leq k si k 8 displaystyle k 8 entonces un vector 8 displaystyle 8 prometedor es una solucion escribir s o l displaystyle sol dd si no explorar las extensiones k 1 displaystyle k 1 prometedoras de sol para j 1 displaystyle j leftarrow 1 hasta 8 displaystyle 8 hacersi j c o l displaystyle j notin col y j k d i a g 45 displaystyle j k notin diag45 y j k d i a g 135 displaystyle j k notin diag135 entoncess o l k 1 j displaystyle sol k 1 leftarrow j s o l 1 k 1 displaystyle sol 1 dots k 1 es k 1 displaystyle k 1 prometedor r e i n a s k 1 c o l j d i a g 45 j k d i a g 135 j k displaystyle mathrm reinas left k 1 col cup j diag45 cup j k diag135 cup j k right dd dd dd El algoritmo comprueba primero si k 8 displaystyle 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 solucion Si k displaystyle k es distinto de 8 el algoritmo explora las extensiones k 1 displaystyle k 1 prometedoras para ello realiza un bucle el cual va de 1 a 8 debido al numero 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 displaystyle k buscamos k 1 displaystyle k 1 prometedor y anadimos la nueva fila columna y diagonales al conjunto de restricciones Al realizar la recurrencia hemos anadido al vector sol una nueva reina que no entra en jaque con ninguna de las anteriores Ademas hemos incrementado el conjunto de restricciones anadiendo una nueva fila columna y diagonales una positiva y otra negativa prohibidas Implementacion Editar A continuacion se muestra una posible implementacion del anterior algoritmo en C include lt iostream gt include lt sstream gt include lt cstdio gt include lt vector gt include lt algorithm gt define NREINAS 8 dimensiones del tablero y numero de reinas using namespace std vector lt int gt sol int nro sol 1 inline bool contiene const vector lt int gt amp v const int val return find v begin v end val v end void reinas int k vector lt int gt col vector lt int gt diag45 vector lt int gt diag135 if k NREINAS printf 3d nro sol for int j 0 j lt NREINAS j cout lt lt lt lt j 1 lt lt lt lt sol j lt lt cout lt lt endl else for int j 1 j lt NREINAS j if contiene col j amp amp contiene diag45 j k amp amp 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 lt lt SOLUCIONES AL PROBLEMA DE LAS lt lt NREINAS lt lt REINAS lt lt endl sol resize NREINAS reinas 0 vector lt int gt vector lt int gt vector lt int gt return 0 El problema de las n reinas EditarEl problema de las ocho reinas se puede plantear de modo general como problema de las n displaystyle n reinas El problema consistiria en colocar n displaystyle n reinas en un tablero de ajedrez de n n displaystyle n times n de tal manera que ninguna de las reinas quede atacando a otras Su analisis y solucion es isomorfo al de las ocho reinas El tablero de 27x27 es el mas grande hasta ahora numerado 1 Numero de soluciones Editar n distintas todas las soluciones 1 1 12 0 03 0 04 1 25 2 106 1 47 6 408 12 929 46 35210 92 72411 341 2 68012 1 787 14 20013 9 233 73 71214 45 752 365 59615 285 053 2 279 18416 1 846 955 14 772 51217 11 977 939 95 815 10418 83 263 591 666 090 62419 621 012 754 4 968 057 84820 4 878 666 808 39 029 188 88421 39 333 324 973 314 666 222 71222 336 376 244 042 2 691 008 701 64423 3 029 242 658 210 24 233 937 684 44024 28 439 272 956 934 227 514 171 973 73625 275 986 683 743 434 2 207 893 435 808 35226 2 789 712 466 510 289 22 317 699 616 364 04427 29 363 495 934 315 694 234 907 967 154 122 528Simetrias escondidas EditarAdemas de las simetrias relativas a la colocacion 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 90 1 1 1 1 01 0 1 1 0 11 1 0 0 1 11 1 0 0 1 11 0 1 1 0 10 1 1 1 1 0 4 7 6 6 6 7 47 4 6 6 6 4 76 6 6 4 6 6 66 6 4 8 4 6 66 6 6 4 6 6 67 4 6 6 6 4 74 7 6 6 6 7 4 4 8 16 18 18 16 8 48 16 14 8 8 14 16 816 14 4 12 12 4 14 1618 8 12 8 8 12 8 1818 8 12 8 8 12 8 1816 14 4 12 12 4 14 168 16 14 8 8 14 16 84 8 16 18 18 16 8 4 28 30 47 44 54 44 47 30 2830 32 44 48 44 48 44 32 3047 44 28 38 38 38 28 44 4744 48 38 36 20 36 38 48 4454 44 38 20 40 20 38 44 5444 48 38 36 20 36 38 48 4447 44 28 38 38 38 28 44 4730 32 44 48 44 48 44 32 3028 30 47 44 54 44 47 30 28Cuando el conjunto de soluciones es correcto para n se da la simetria completa tanto vertical como horizontalmente Esta simetria puede darse con un conjunto de soluciones incompleto Sin embargo la suma de cada fila y de cada columna si el conjunto de soluciones esta completo da como resultado el numero total de soluciones posibles para n 6 para n 7 para n 8 para n 90 1 1 1 1 0 41 0 1 1 0 1 41 1 0 0 1 1 41 1 0 0 1 1 41 0 1 1 0 1 40 1 1 1 1 0 4 4 4 4 4 4 4 0s Soluciones 4d Suma diagonal 0s d 4 4 7 6 6 6 7 4 407 4 6 6 6 4 7 406 6 6 4 6 6 6 406 6 4 8 4 6 6 406 6 6 4 6 6 6 407 4 6 6 6 4 7 40 4 7 6 6 6 7 4 40 40 40 40 40 40 40 40 36s Soluciones 40d suma diagonal 36s d 4 4 8 16 18 18 16 8 4 928 16 14 8 8 14 16 8 9216 14 4 12 12 4 14 16 9218 8 12 8 8 12 8 18 9218 8 12 8 8 12 8 18 9216 14 4 12 12 4 14 16 928 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 64s Soluciones 92d Suma diagonal 64s d 28 28 30 47 44 54 44 47 30 28 35230 32 44 48 44 48 44 32 30 35247 44 28 38 38 38 28 44 47 35244 48 38 36 20 36 38 48 44 35254 44 38 20 40 20 38 44 54 35244 48 38 36 20 36 38 48 44 35247 44 28 38 38 38 28 44 47 35230 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 288s Soluciones 352d Suma diagonal 288s d 64 Por ultimo 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 conexion entre el tablero de n casillas y el de n 1 casillas Para conjunto de soluciones completas Tablero de Suma linea y soluciones posibles Suma diagonal esquinas tablero n 1 x n 1 resta suma linea suma diagonal6 x 6 4 0 Esquinas tablero 7 x 7 47 x 7 40 36 Esquinas tablero 8 x 8 48 x 8 92 64 Esquinas tablero 9 x 9 289 x 9 352 288 Esquinas tablero 10 x 10 6410 x 10 724 628 Esquinas tablero 11 x 11 9611 x 11 2680 2180 Esquinas tablero 12 x 12 50012 x 12 14200 11440 Esquinas tablero 13 x 13 276013 x 13 73712 61820 Esquinas tablero 14 x 14 1189214 x 14 365596 296080 Esquinas tablero 15 x 15 6951615 x 15 De hallar la relacion entre los valores que resultan en las esquinas y el numero total de soluciones de cada tablero o su tamano se podria encontrar los resultados correctos de cualquier valor de n Soluciones al problema de las ocho reinas EditarEl 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 simetrias y rotaciones de las 12 soluciones unicas que se muestran a continuacion Solucion unica 1 Solucion unica 2 Solucion unica 3 Solucion unica 4 Solucion unica 5 Solucion unica 6 Solucion unica 7 Solucion unica 8 noscript, wikipedia, wiki, leyendo, leer, libro, biblioteca, español , española, descargar, gratis, descargar gratis, mp3, video, mp4, 3gp, jpg, jpeg, gif, png, imagen, música, canción, película, libro, juego, juegos © Derechos de autor 2021, Todos los derechos reservados  |   www.wiki3.es-es.nina.az Rss Feed SiteMap Ping DMCA Contacta con nosotros Página principal Cerrado Llama: