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

INTRODUCCIÓN AL ANÁLISIS DE ALGORITMOS

Teniendo todas las consideraciones en cuenta, se puede aplicar el esquema backtracking para im-
plementar las ocho reinas de una manera realmente eficiente. Para ello, se reformula el problema
como uno de búsqueda en un árbol. Entonces se dice que en un vector V de enteros entre 1 y
1…k
8 es k-prometedor, para 0 ≤ k ≤ 8 si ninguna de las k reinas colocadas en las posiciones (1, V ), (2,
1
V ),…, (8, V ) amenaza a ninguna de las otras. Las soluciones a nuestro problema se corresponden
2 8
con aquellos vectores que son 8-prometedores.

establecimiento del algoritmo

Sea N el conjunto de vectores de k-prometedores, 0 ≤ k ≤ 8, sea G = (N, A) el grafo dirigido tal que

(U, V) A, si y solo si existe un entero k, con 0 ≤ k ≤ 8 tal que

• U es k-prometedor.

• V es (k + 1)-prometedor.

• U = V para todo i {1,..., k}.
i i

Este grafo es un árbol. Su raíz es el vector vacío correspondiente a k = 0. Sus hojas son o bien
soluciones (k = 8) o posiciones sin salida (k < 8). Las soluciones del problema de las ocho reinas
se pueden obtener explorando este árbol. Sin embargo, no se genera explícitamente el árbol para
explorarlo después. Los nodos se van generando y abandonando en el transcurso de la exploración
mediante un recorrido en profundidad (figura 6.4).

Figura 6.4. Esquema reducido del árbol de soluciones

133