8 Reinas En Prolog

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
mismafila, 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íaplantear 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 ineficiente, se usa más
espacio del necesario.
7Representación
Otra opción es hacer uso de un vector de
N enteros, donde cada posición
corresponde a una columna del tablero, y
el entero representa la fila en la que se
encuentra la reinadentro de dicha
columna.
Más eficiente y más sencilla de usar.
8

Soluciones
Como cada posición del vector representa
una columna, no pueden situarse dos
reinas en la misma columna.
Si el vectortiene varios enteros iguales,
quiere decir que esas reinas están en la
misma fila, por lo que sería incorrecta la
solución.
Queda el problema de las diagonales.
9

Soluciones

Dos reinas estánen la misma diagonal si:
Mismo valor de fila - columna
(Diagonal descendente)
Mismo valor de fila + columna
(Diagonal ascendente)

10

Soluciones
Una posible solución en un tablero de N=8:S=(6,4,2,0,5,7,1,3)
11

Resolución secuencial

12

Resolución secuencial
La solución secuencial se podría plantear
como un backtracking.
Complejidad: O(n!)
Problema: Poco eficiente, paratamaño
grande del tablero puede tardar
demasiado.
13

Resolución secuencial
Otra posibilidad es usar una bolsa de
tareas.
Eliminamos los vectores que no sean
prometedores, es decir, que...