Page 140 - INTRODUCCIÓN AL ANÁLISIS DE ALGORITMOS

INTRODUCCIÓN AL ANÁLISIS DE ALGORITMOS

Hay que decidir si un vector es k-prometedor; sabiendo que es una extensión de un vector (k −
1)-prometedor, únicamente se requiere comprobar la última reina que se deba añadir. Este se puede
acelerar si se asocia 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.

descripción del algoritmo

A continuación, se muestra el algoritmo (Horowitz y Sahni, 1978) que arroja la solución de nuestro
problema, en el cual S es un vector global. Para imprimir todas las soluciones, la llamada inicial
1. . . 8
es reinas (0,0,0,0) (algoritmo 6.1).

Algoritmo 6.1. Algoritmo para la solución del problema

El algoritmo comprueba primero si k = 8. Si esto es cierto, se tiene 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 se incrementa k (buscamos (k + 1)-pro-
metedor) y se añaden la nueva fila, columna y diagonales al conjunto de restricciones. Al realizar la
recurrencia se ha añadido al vector sol una nueva reina, la cual no entra en jaque con ninguna de
las anteriores. Además, se ha incrementado el conjunto de restricciones añadiendo una nueva fila,
columna y diagonales (una positiva y otra negativa) prohibidas. Un ejemplo del árbol en profundidad
se puede ver fácilmente en la figura 6.5 con un ejemplo de las 4 reinas:

134