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

INTRODUCCIÓN AL ANÁLISIS DE ALGORITMOS

Figura 6.2. Ejemplo de dos reinas amenazadas en el tablero de 4 por 4

El vector (3,1,6,2,8,6,4,7) significa que la reina 1 está en la columna 3, fila 1; la reina 2 en la columna
1, fila 2; la reina 3 en la columna 6, fila 3; la reina 4 en la columna 2, fila 4, etc. (figura 6.3). Como se
puede apreciar, esta solución es incorrecta, ya que estarían la reina 3 y la 6 en la misma columna. Por
tanto, el vector correspondería a una permutación de los ocho primeros números enteros.

Figura. 6.3. Un ejemplo de ocho reinas

El problema de las filas y columnas está cubierto, pero qué ocurre con las diagonales. Para las posi-
ciones sobre una misma diagonal descendente se cumple que tienen el mismo valor fila − columna,
mientras que para las posiciones en la misma diagonal ascendente se cumple que tienen el mismo
valor fila + columna. Así, si se tienen dos reinas colocadas en posiciones (i, j) y (k, l), entonces están
en la misma diagonal si y solo si cumple:

i − j = k − l o i + j = k + l

j − l = i − k o j − l = k – i

132