De Wikipedia, la enciclopedia libre
Movimientos posibles de una reina en un tablero de 4x4
|
|
| Una posible solucón entre muchas en un tablero de 8x8 |
El problema de las ocho reinas se trata de un puzle en el que se colocan ocho reinas sin que se amenacen. En el juego de ajedrez la reina amenaza a aquellas fichas que se encuentren en su misma fila, columna o diagonal. Las 8 reinas consiste en colocar sobre un tablero de ajedrez ocho reinas sin que estas se den jaques entre ellas. Para resolver este problema emplearemos un esquema vuelta atrás (Backtracking).
[editar] Planteamiento del Problema
Podemos numerar las 8 reinas del 1 al 8, así cada reina tiene un identificador propio, es decir, “un nombre propio”. 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, lo mismo sucede con las columnas y diagonales. Para ello representamos el tablero mediante un vector, el cual tiene longitud 8, este vector tiene este significado:
Ejemplo de dos reinas amenazadas en el tablero de 4x4
Vector [3,1,6,2,8,6,4,7] a la reina 1 esta en la columna 3, la reina 2 en la columna 1, la reina 3 en la columna 6, la reina 4 en la columna 2, 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 cumple:
i – j = k – 1 ó i + j = k + 1 j – 1 = i – k ó j – 1 = k – i
Y por tanto, están en la misma diagonal si y solo si
Con todas las consideraciones tenidas en cuenta podemos aplicar el esquema de vuelta atrás para implementar las ocho reinas de una manera realmente eficiente. Para ello, reformulamos el problema como un problema de búsqueda en un árbol. Decimos que en un vector V[1..k] de enteros entre 1 y 8 es k-prometedor, para 0≤k≤8 , si ninguna de las k reinas colocadas en las posiciones (1,V[1]), (2,V[2]),…, (k,V[k]) amenaza a ninguna de las otras. Las soluciones a nuestro problema se corresponden con aquellos vectores que son 8-prometedores.
[editar] Establecimiento del Algoritmo
Sea N el conjunto de vectores de k-prometedores, 0≤k≤8, sea G= el grafo dirigido tal que (U,V) Є A si y solo si existe un entero k, con 0≤k≤8 tal que
- U es k-prometedor
- V es (k+1)-prometedor
- U[i]=V[i] para todo i Є [1..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.
El siguiente esquema muestra como sería este árbol, debido a su gran tamaño, lo he reducido ya que no entraría en el folio.
Hay que decidir si un vector es k-prometedor, sabiendo que es una extensión de un vector (k–1)-prometedor, sólo 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.
[editar] Implementación del Algoritmo
A continuación se muestra la implementación de nuestro problema, en el cual sol[1..8] es un vector global. Para imprimir todas las soluciones la llamada inicial es reinas(0,Ø,Ø,Ø).
procedimiento reinas(k,col,siag45,diag135)
{sol[1..k] es k-prometedor,
col = {sol[i] | 1≤i≤k },
diag45 = {sol[i] – i +1 | 1≤i≤k }y
diag135 = {sol[i] + 1 -1 | 1≤i≤k }}
si k = 8 entonces {un vector 8-prometedor es una solución}
escribir sol
fsi
sino {explorar las extensiones (k+1)-prometedoras de sol}
para j←1 hasta 8 hacer
si j col y j- k diag45 y j+k diag135
entonces sol[k+1]←j
{sol[1..k+1] es (k+1)-prometedor}
reinas(k+1,col {j},diag45 {j-k},diag135 {j+k})
fsi
fpara
fsino
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.
[editar] Soluciones al Problema de las Ocho Reinas
El problema de las ocho reinas tiene 92 soluciones distintas. Es decir las soluciones difieren entre si de operaciones de simetría, rotación y/o traslación del tablero, haciendo que todas ellas sean contadas como una. En este caso el problema tiene 12 únicas soluciones y se presentan a continuación:
[editar] Referencias
- Watkins, John J. (2004). Across the Board: The Mathematics of Chess Problems. Princeton: Princeton University Press. ISBN 0-691-11503-6.
[editar] Enlaces externos
[editar] Enlaces a Soluciones
[editar] Véase también
