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

INTRODUCCIÓN AL ANÁLISIS DE ALGORITMOS

Las restricciones explícitas pueden o no depender de una particular instancia I del problema a ser
resuelto. Todas las tuplas que satisfacen a restricciones explícitas definen un posible espacio de so-
lución para I. Las restricciones implícitas determinan cuál de las tuplas en un espacio de solución de
I en realidad satisfacen la función del criterio. Así, las restricciones implícitas describen el camino en
el cual las x deben de relacionarse una a otra.
i

el proBleMa de laS ocHo reINaS (8-queeNS)

Un problema combinatorio clásico es colocar las ocho reinas en un tablero de ajedrez de tal forma
que no se puedan atacar entre ellas, es decir, que no existan dos reinas en la misma hilera, columna
o diagonal, enumerando las hileras y columnas del tablero del 1 al 8, del mismo modo que se haría
con las reinas. Ya que cada reina debe estar sobre una hilera diferente, se puede asumir que la reina i
se colocará en la hilera i. Toda solución puede ser representada como 8 tuplas (x ,…, x ) donde x es
1 8 i
la columna en la cual la reina i será colocada. La restricción explicita usando esta formulación será S
= {1, 2, 3,…, 8}, 1 ≤ i ≤ n, por lo que el espacio de soluciones consta de 8 tuplas de 8. Una de las
8
restricciones implícitas del problema es que dos x no deben de ser las mismas (esto es, toda reina
debe de estar en diferente columna) y tampoco en la misma diagonal (figura 6.1). La primera restric-
ción indica que todas las soluciones son permutaciones de las ocho tuplas (1,.., 8). Esto reduce el
espacio de la solución de 8 tuplas a 8! tuplas.
8

Figura 6.1. Posiciones que puede atacar la reina

plaNteaMIeNto del proBleMa

Como cada reina puede amenazar a todas las reinas que estén en la misma fila (figura 6.2), cada una
ha de situarse en una fila diferente. Se pueden representar las ocho reinas mediante un vector [1-8],
teniendo en cuenta que cada índice del vector representa una fila y el valor una columna. Así, cada
reina estaría en la posición (i, v[i]) para i = 1-8.

131