Algoritmo 8 Reinas

“Un amigo suyo aficionado al ajedrez, en medio de una partida especialmente trabada, le

cuenta una inquietud que él tiene hace mucho tiempo con este juego y que nadie ha podido

responderle todavía. Se trata de cómo colocar ocho piezas iguales (8 reinas en este caso)

sobre el tablero, de tal forma que ninguna pueda comerse a otra”.

Sabiendo que en este juego, una reina amenaza a cualquier otra pieza que esté en la misma

columna, fila o cualquiera de las cuatro diagonales, el problema es obviamente la forma en

que dichas piezas deben estar distribuidas sobre el tablero en un primer momento.

Nota: se sugiere intentar resolverlo a mano.

Se pide responder:

A)

- 1. ¿Con qué tipo de algoritmo estamos tratando al intentar resolver este problema? ¿Por qué?

- 2. ¿Con cuántos “Arreglos” de datos deberíamos trabajar para resolverlo?

- 3. Implemente un procedimiento general en pseudocódigo para resolver el problema planteado.

B)

- 1. Defina con sus propias palabras qué es un algoritmo recursivo y qué tipos de recursión existen.

- 2.Explique el algoritmo utilizado para resolver el juego-problema llamado “Las Torres de Hanoi”.

CANTIDAD MÍNIMA DE PALABRAS: 1000.

CANTIDAD MÁXIMA DE PALABRAS: 1500.

RESPUESTAS:

Respuesta a pregunta: 1. ¿Con qué tipo de algoritmo estamos tratando al intentar resolver este problema? ¿Por qué?

El problema planteado corresponde a un conocido problema llamado “Problema de las 8 Reinas” o “Problema de las N Reinas” fue planteado por el ajedrecista Max Bezzel en 1848. Y tal como dice la descripción del problema la idea es situar 8 reinas en un tablero de ajedrez sin que entre ellas se amenacen entre ellas.

Si bien hay varias formas de resolver el problema se entiende según lo planteado en la descripción del problema en el encabezado de la tarea que el algoritmo a utilizar corresponde a uno de “Bactracking” o “Vuelta atrás”.

Algoritmos de Backtracking:

Los algoritmos de Backtracking son semejantes a un recorrido de profundidad en un grafo y cada nodo del grafo es una subtarea. Son útiles para buscar soluciones a problemas, se caracterizan por no seguir reglas para la búsqueda de la solución, simplemente realizan una búsqueda sistemática, o sea hay que probar todo lo posible hasta encontrar la solución o entregar como resultado que no existe una solución al problema planteado.

En el caso del Backtracking El problema se separa en varias búsquedas parciales o subtareas, asimismo éstas subtareas pueden incluir otras subtareas. Esto implica que son en general de naturaleza recursiva.

El hecho de que se llamen recursivos se debe a que de no encontrar una solución se retrocede a la subtarea original y se prueba una subtarea aún no probada hasta encontrar la solución. (Encontrando una solución similar a otra encontrada anteriormente o una nueva solución).

El problema de las 8 reinas.

En el caso del problema de las 8 reinas eso es justamente lo que se necesita, probar diferentes ubicaciones en el tablero hasta dar con la solución. Cantidad de ubicaciones posibles depende directamente del tamaño del tablero (8x8) y tal como se explicó anteriormente una solución puede repetirse.

2. ¿Con cuántos “Arreglos” de datos deberíamos trabajar para resolverlo?

Para el problema de las 8 reinas con 5 arreglos se puede encontrar la solución al problema:

Arreglos 1, 2, 3: Validar si una reina está o no está atacando a otra reina ubicada en su misma fila o columna.

Arreglo 4: Guarda la solución actual.

Arreglo 5: Guarda las soluciones acumuladas.

- 3. Implemente un procedimiento general en pseudocódigo para resolver el problema planteado

ResuelveProblemaReinas (Integer tamanotablero, Reina reina[tamanotablero]);

i <- 0 //Comenzamos situando la reina 0

while i < tamanotablero

reina[i].row

...