Problema de las N Reinas
Resolución paralela

Indice
Introducción al problema
Representación y Soluciones
Resolución secuencial
Resolución paralela
Conclusiones
Bibliografía
2

Introducción

3

Introducción

El problema de las N reinas consiste en situar N reinas en un tablero de ajedrez de
NxN sin que se amenacen entre ellas.
Una reina amenaza a otra si está en la misma fila, columna o diagonal.

4

Introducción
Movimientos posibles de una reina en el tablero: 5

Representación y Soluciones

6

Representación
Para representar el problema, se podría plantear como una matriz de NxN enteros, donde un 1 significa que la reina está en esa posición, y un 0 que la casilla está vacía.
Representación …ver más…

Esta será la versión tomada como base para la solución paralela.
15

Resolución paralela

16

Resolución paralela

La solución inmediata en OpenMP sería que cada hilo tomase una tarea de la bolsa, genere las tareas correspondientes a partir de ella, y repetir esto hasta que no queden tareas.

17

Resolución paralela
En MPI se puede plantear de forma similar, con gestión de tareas, solo que habrá un nodo maestro que controle las tareas por realizar, y los demás nodos son los encargados de pedir tareas y enviar las nuevas al master.
En este caso pueden darse varias opciones: 18

Resolución paralela
El nodo maestro genera una sola configuración inicial, y cada uno de los nodos siguientes van generando nuevas configuraciones e insertándolas en la bolsa. En este caso se producen grandes cantidades de comunicaciones.
19

Resolución paralela
Otra opción es que el nodo maestro genere una cantidad inicial de tareas a resolver, y luego las reparta entre todos los nodos.
El reparto puede ser dinámico o estático.
En este caso las comunicaciones se reducen al principio para repartir, y al final para obtener los resultados.
20

Conclusiones

21

Conclusiones
A priori, antes de realizar los desarrollos y las pruebas, se pueden sacar una serie
de