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.

Nuestro reto tiene 2 partes, por una parte y sin hacer trampas intentar encontrar una solución válida y por otra la búsqueda de información sobre que algoritmos/estrategias permitirían resolver el problema de forma secuencial…

El problema no es sencillo y requiere una parte de investigación que nos puede servir para otros similares…

 

Veamos como pista la SEGUNDA parte:

Tenemos un tablero de 8X8, el cual podemos representar como una matriz (8,8), por lo que una solución al problema viene dada por un vector de 8 posiciones de numeros del 1 al 8.

(R[1],R[2],R[3],R[4],R[5],R[6],R[7],R[8]), asi por tanto un ejemplo de vector seria (1,8,3,6,5,4,7,2).

La estrategía básica consistiría en dar valor a R[1],…,R[8] de forma sistematica y comprobando que

cumplidos los requisitos de R[i] al añadir la reina R[i+1] en esa posición estos se siguen cumpliento.

 

Hay un sistema denominado backtracking que se basa en la busqueda en profundidad en el ARBOL del espacio de estados posibles,

donde cada nivel del arbol en una nueva colocación de una reina el el tablero.

 

¿Como comprobamos si una nueva reina choca con otra?

Sea R[a] en la posición (i,j) y R[b] en posición (k,l).

Evidentemente si i=k Ó j=l las reinas estarian en la misma fila o columna, por lo que se matarian.

El caso de las diagonales es un poquito mas complidado y consiste en dada una reina en (i,j), las diagonales son las casillas de la forma (i+n,j+n), (i+n,j-n) con n en{-7,..,7} y el resultado del vector posición de la reina nueva dentro de la matriz.

Por ejemplo para (i,j) = (3,1) –> (3+n,1+n) –> (4,2),(5,3),(6,4),(7,5),(8,6) y (1,3),(2,2),

estos són los vectores de posición que mata una reina en (3,1) en diagonales mas los del tipo (3,x) y (x,1) con x entre {1,..,8}

 

En este punto el algoritmo ya se nos hace mas sencillo.

. Para i = 1 hasta 8

.                           Poner reina R[i]

.                           Para j = 1 hasta 8

.                                            Poner Reina R[i+1]  en posicion (j,i+1) y comprobar choques con las anteriorer R[1] a R[i]

.                                            Si llegamos a profundidad 8 tenemos una solución…

.                           Fin Para

. Fin Para

 

 

¿Como representariamos el tablero en un ordenador?

 

¿Que lenguaje de programación usarias?

 

¿Cuantos pasos de busqueda individuales habria que realizar en el peor de los casos?

 

Mandad respuestas a presidencia@amuaci.es …