Aplicación de técnicas incompletas al problema de las N-Reinas

”Aplicaci´on de t´ecnicas incompletas al problema de las N-Reinas” Pablo Itaim Ananias Valpara´ıso, 05 de Septiembre del 2005 Resumen El problema de las n-Reinas (n-Queens Problem) es muy antiguo. Propuesto por primera vez en el a˜ no 1848, consiste en encontrar una asignaci´ on a n reinas en un tablero de ajedrez de n x n de modo tal, que ´estas no se ataquen. El presente trabajo presenta el problema en cuesti´ on, muestra un ejemplo sencillo de ´el y profundiza en distintos m´etodos de resoluci´ on basados en t´ecnicas incompletas de optimizaci´ on.

1.

Introducci´ on

El problema de las n-Reinas consiste en encontrar una distribuci´on de n reinas en un tablero de ajedrez de n x n de modo tal, que ´estas no se ataquen. As´ı, no pueden encontrarse dos reinas en la misma fila, columna o diagonal. Este problema tiene 2 Versiones. La m´as simple consiste en encontrar exactamente una soluci´on v´alida para un valor n dado. La otra versi´ on, m´ as dif´ıcil, consiste en encontrar todas las soluciones posibles para un valor n. Fue propuesto para n = 8 en el a˜ no 1848 en un trabajo an´onimo [1], siendo posteriormente atribuido a Max Bezzel. Sin embargo, la publicaci´ on detallada m´as antigua que se conoce fue realizada por Nauck [2] en 1850. Ese mismo a˜ no, Gauss postul´ o la existencia de 72 soluciones para n = 8. Posteriormente, en el a˜ no 1874, Glaisher [3] prob´ o la existencia de 92 soluciones. La investigaci´ on sobre este tema no ha parado hasta hoy por lo que existe una amplia variedad de algoritmos sugeridos para su resoluci´ on. Muchas de las soluciones planteadas se basan en proporcionar una f´ormula espec´ıfica para colocar las reinas o extrapolar conjuntos peque˜ nos de soluciones para proporcionar soluciones para valores de n m´ as grandes. Observaciones emp´ıricas de problemas de peque˜ no tama˜ no muestran que el n´ umero de soluciones crece en forma exponencial al ir aumentando el valor de n [4]. Se puede observar que este problema tiene una soluci´on (Q(1) = 1) para n = 1, no tiene soluci´on para n = 2 y n = 3 y tiene 2 soluciones para n = 4. Para una mejor lectura, el presente informe se ha organizado de la siguiente manera: en la secci´on 2, se define el problema a resolver, indicando las principales caracter´ısticas de ´este. En la secci´on 3, se describen muy brevemente algunas de las aplicaciones que tiene el problema d las n-reinas dando un ejemplo pr´actico en la secci´on 4. En los puntos 5 y 6 se discute respecto a las formas de modelar el problema, definiendo adem´as el modelo final a utilizar en la resoluci´on de ´este en el presente trabajo. En la secci´on 7, se describen los distintos algoritmos implementados. En el punto 8, se presentan los casos de prueba con los cuales se ejecutaron los algoritmos y cuyos resultados se entregan en el punto 9. Finalmente, en el punto 10, se indican las conclusiones m´ as importantes del presente trabajo.

2.

Definici´ on del Problema

Como se plante´ o anteriormente, el problema de las n-Reinas consiste en encontrar una distribuci´on de n reinas en un tablero de n x n de modo tal, que ´estas no se ataquen. As´ı, no pueden encontrarse dos reinas en la misma fila, columna o diagonal.

Este Problema tiene 2 Versiones. La m´as simple consiste en encontrar exactamente una soluci´on v´alida para un valor n dado. La otra versi´ on, m´ as dif´ıcil, consiste en encontrar todas las soluciones posibles para un valor n. La Tabla 1 muestra el n´ umero total de Soluciones Q(n) para 4 ≤ n ≤ 20 [5, 6]. n 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

Q(n) 2 10 4 40 92 352 724 2.680 14.200 73.712 365.596 2.279.184 14.772.512 95.815.104 666.090.624 4.968.057.848 39.029.188.884

Tabla 1: N´ umero total de soluciones Q(n) para 4 ≤ n ≤ 20 Para solucionar este problema, se han dise˜ nado numerosos Algoritmos basados en algunos como Backtracking, Algoritmos Gen´eticos, B´ usqueda local con resoluci´on de conflictos, programaci´on entera y redes neuronales entre otros. Adem´ as, el Problema de las n reinas pertenece a la clase de problemas NP-completos [7], pero se resuelve f´ acilmente en tiempo polinomial cuando solamente se busca una soluci´on [4]. Existen soluciones anal´ıticas donde se da una f´ormula expl´ıcita para la localizaci´on de las reinas o bien se encadenan soluciones obtenidas para valores menores de n [8, 9]. El problema con estas soluciones es que generan un n´ umero muy peque˜ no de soluciones. Backtracking es, en general, ineficiente y para el problema de las n-reinas no es f´acil encontrar soluciones para n > 100 en tiempos razonables [10], sin embargo, Kal´e [11] dise˜ n´o un algoritmo especializado de backtracking que consigue resolver el problema hasta tama˜ nos del orden de 1.000. Se han realizado numerosas aplicaciones de algoritmos gen´eticos para resolver el problema de las n-reinas [7, 12, 13, 14], pero se han visto ineficientes a´ un cuando se hayan probado diversas representaciones del problema y diversos operadores. Por otra parte, los Algoritmos para Programaci´on Entera son t´ıpicamente exponenciales y consecuentemente consiguen resolver problemas de tama˜ no muy peque˜ no [15]. Un Algoritmo de Redes Neuronales utilizando un modelo modificado de Hopfield [16] parece funcionar mejor que otros modelos de redes neuronales presentados, pero solo se publican resultados para valores de n peque˜ nos. La B´ usqueda local con minimizaci´ on de conflictos [4] parece ser el mejor algoritmo encontrado hasta ahora. Este algoritmo de Socic y Gu tiene tiempo de ejecuci´on lineal por lo que es extremadamente r´apido. En su articulo, ellos muestran que su algoritmo es capaz de obtener una soluci´on para cualquier valor de n, n < 1000 en menos de 0.1 segundo y 55 segundos para n = 3,000,000, en un computador del a˜ no 94 (IBM RS 6000/530). Ahora, dada la naturaleza probabil´ıstica del algoritmo, no se tiene garant´ıa del tiempo del peor caso del algoritmo, pero en la pr´ actica muestra un excelente desempe˜ no y un comportamiento muy robusto. Hynek [14] dise˜ n´ o una Heur´ıstica basada en una fase de preprocesamiento y posteriormente aplica un operador de mutaci´ on basado en b´ usqueda local. Los resultados computacionales muestran que el algoritmo es efectivo y logra soluciones hasta n = 1000 en tiempos razonables.

3.

Aplicaciones

El Problema de las n-reinas es conocido usualmente como uno relacionado a un juego y tambi´en como un problema apropiado para probar algoritmos nuevos. Sin embargo, tiene otras aplicaciones ya que se le 2

considera como un modelo de m´ axima cobertura. Una soluci´on al problema de las n-reinas garantiza que cada objeto puede ser accesado desde cualquiera de sus ocho direcciones vecinas (dos verticales, dos horizontales y cuatro diagonales) sin que tenga conflictos con otros objetos. Algunas aplicaciones posibles son: Control de Tr´ afico A´ereo Sistemas de Comunicaciones Programaci´ on de Tareas Computacionales ´ Procesamiento Paralelo Optico Compresi´ on de Datos Balance de Carga en un Computador multiprocesador Ruteo de mensajes o datos en un Computador multiprocesador etc. Un ejemplo pr´ actico de una aplicaci´ on del problema de las n-reinas es el siguiente: para lograr el mayor ancho de banda posible en un sistema de comunicaciones de banda estrecha y direccional, se deben ubicar los n transceptores de forma tal que no se interfieran entre ellos. Con los n transceptores ubicados en patrones sin conflictos, lo que corresponde a una soluci´ on del problema de las n-reinas, cada transceptor puede comunicarse con el mundo exterior en forma libre en 8 direcciones sin que sea inhibido por otro transceptor. La Figura 1 muestra una distribuci´ on para 10 transceptores. Esta distribuci´on corresponde a una de las soluciones para el problema de las 10-reinas.

Figura 1: Ubicaci´ on de 10 Transmisores/Receptores sin conflicto entre ellos (Cada uno puede comunicarse en cualquier direcci´ on vertical, horizontal o diagonal

4.

Ejemplo

Para visualizarlo mejor, analizaremos el problema de las n reinas para n = 6. Como ya hemos visto, esto consiste en ubicar 6 reinas en un tablero de 6x6 sin que ellas se ataquen. Se sabe que para este caso existen 4 soluciones v´ alidas, las que se presentan en los gr´aficos de la figura 2. Con alg´ un m´etodo, comenzamos la b´ usqueda de una soluci´on y encontramos la a). A partir de ella podemos encontrar las otras 3 de la siguiente forma: La soluci´ on b) se obtiene rotando la soluci´on a), 90 grados a la derecha. La soluci´ on c) es el reflejo de la soluci´on b) respecto al borde derecho de ´esta. Es decir, si se coloca un espejo en el borde derecho de la soluci´on b), se observa la soluci´on c). La soluci´ on d) es el reflejo de la soluci´on a) respecto del borde derecho de ´esta. 3

Figura 2: Soluciones al problema de las 6-reinas Si bien estos m´etodos ayudan a encontrar soluciones v´alidas del problema, no las encuentran todas, por lo que se hace necesario contar con otros m´etodos para solucionar el problema. Adem´as, es necesario encontrar una soluci´on inicial para poder aplicarlos.

5.

Modelo en Extenso El problema de las n-reinas tiene, b´ asicamente, dos modelos asociados que cumplen con lo siguiente: La Funci´ on Objetivo no tiene un uso pr´actico ya que se sabe a priori el valor de n. Dos reinas no pueden estar en la misma Fila. Dos reinas no pueden estar en la misma Columna. Dos reinas no pueden estar en la misma Diagonal.

Para efectos de mejor entendimiento, se van a dividir las diagonales seg´ un el signo de su pendiente. De esta forma, tendremos diagonales positivas y diagonales negativas. Adem´as, vamos a definir el n´ umero de reinas y ancho del tablero de ajedrez como N , con N = {1, . . . , n}. Si bien la cantidad de formas de modelar son pocas, estos modelos se resuelven o desarrollan de muchas formas y con varios m´etodos distintos.

5.1.

Modelo 1

Este modelo es el m´ as general y el m´as f´acil de implementar. Utiliza una variable binaria xij para representar la existencia de una reina en la casilla (i, j). As´ı, si existe, xij = 1 y si no, vale 0. Las restricciones abarcan las filas, las columnas, diagonales positivas y diagonales negativas. La restricci´ on de las filas impide que existan dos reinas en la misma fila. Esto se verifica sumando todos los valores de las casillas xij para una fila determinada. As´ı, dicha suma deber´ıa ser igual a 1 para todas las filas ya que deber´ıa haber un solo 1 en cada fila. Esta restricci´on se puede resumir de la siguiente forma: n X

∀i ∈ N

xij = 1

j=1

Del mismo modo, la restricci´ on de las columnas impide que existan dos reinas en la misma columna. Esto se verifica sumando todos los valores de las casillas xij para una columna determinada. As´ı, dicha suma deber´ıa ser igual a 1 para todas las columnas ya que deber´ıa haber un solo 1 en cada columna. Esta restricci´on se puede resumir de la siguiente forma: n X

∀j ∈ N

xij = 1

i=1

4

Las diagonales son un poco m´ as complicadas de verificar por la definici´on de los valores de recorrido de la variable. En las diagonales, tanto positivas como negativas, debe haber a lo m´as una reina. Esto se verifica sumando los valores de las casillas que forman las distintas diagonales. Si analizamos la formaci´ on de las diagonales positivas, veremos que ´estas estar´an definidas por la suma k = i + j. As´ı, todos los pares (i, j) que tengan el mismo valor para k, estar´an en la misma diagonal positiva.

Figura 3: Ejemplo de diagonales positivas y negativas para n = 6 Por ejemplo, en la figura 3, podemos observar que todos los pares que forman la diagonal positiva suman 8. Ahora, para el mismo ejemplo, podemos observar que k se mueve dentro del rango {2, . . . , 12}. Si no consideramos las dos diagonales de las esquinas ((1, 1) y (6, 6)), el valor de k var´ıa en el rango de {3, . . . , 11}. De esta forma, definiendo los valores de k podemos recorrer todas las diagonales positivas. Generalizando, podemos afirmar que k = i + j var´ıa en el rango de {2, . . . , 2n} o {3, . . . , 2n − 1} dependiendo si consideramos las casillas de las esquinas. De esta forma, podemos definir la restricci´on para las diagonales positivas de la siguiente forma: n X n X

xij ≤ 1

∀k = {2, . . . , 2n} o k = {3, . . . , 2n − 1}

i=1 j=1

| {z } i+j=k

An´alogamente, analizamos la formaci´ on de las diagonales negativas. Podemos verificar que ´estas est´an definidas por la resta k = i − j. As´ı, todos los pares (i, j) que tienen el mismo valor para k, est´an en la misma diagonal negativa. Por ejemplo, en la figura 3, podemos observar que para todos los pares que forman la diagonal negativa, sus restas valen 1. Ahora, para el mismo ejemplo, podemos observar que k se mueve dentro del rango {−5, . . . , 5}. Si no consideramos las dos diagonales de las esquinas ((6, 1) y (1, 6)), el valor de k var´ıa en el rango de {−4, . . . , 4}. De esta forma, definiendo los valores de k podemos recorrer todas las diagonales negativas. Generalizando, podemos afirmar que k = i−j var´ıa en el rango de {−5, . . . , 5} o {−4, . . . , 4} dependiendo si consideramos las casillas de las esquinas. De esta forma, podemos definir la restricci´on para las diagonales negativas de la siguiente forma: n X n X

xij ≤ 1

∀k = {−5, . . . , 5} o k = {−4, . . . , 4}

i=1 j=1

| {z } i−j=k

El problema de este modelo es el tama˜ no del espacio de b´ usqueda, que es 2n∗n . As´ı, para n = 10, este ser´ıa de 1030 aproximadamente, lo cual lo hace muy ineficiente a la hora de buscar todas las soluciones al problema.

5.2.

Modelo 2

Otra forma de modelar el mismo problema es considerando otro tipo de variables. Podemos utilizar la variable xi para representar la posici´ on de la reina en la fila i. En este caso, el dominio de xi ser´ıa {1, . . . , n}. A diferencia del modelo anterior, las restricciones abarcan las columnas y todas las diagonales, sin distinguir 5

entre positivas y negativas. Las filas se verifican por defecto, al tener que asign´arsele un valor a la variable. Es decir, por la forma del modelo, no pueden haber dos reinas en la misma fila, por lo que esa restricci´on se omite. La restricci´ on de las columnas impide que existan dos reinas en la misma columna. Esto se verifica observando los valores de las variables. Si estos son distinto, entonces se cumple con la restricci´on, si son iguales, no. Otra forma an´ aloga es calculando la diferencia entre dos valores de x. De esta forma, si xi −xj = 0 (con i 6= j) las dos reinas est´ an en la misma columna. Esta restricci´on se puede resumir de la siguiente forma: xi 6= xj

∀i 6= j con i y j ∈ N

An´alogamente: xi − xj 6= 0

∀i 6= j con i y j ∈ N

Al igual que en el modelo anterior, en las diagonales, tanto positivas como negativas, debe haber a lo m´as una reina. Dada la definici´ on del modelo, el valor de la variable me indica la columna y el ´ındice de la variable, la fila. Utilizando esos valores, se puede calcular la pendiente de una recta que pase por los dos casilleros, xi y xj que estoy verificando. Sabiendo que todas las diagonales positivas forman un ´angulo de 45◦ respecto a la base del tablero y que todas las diagonales negativas forman un ´angulo de −45◦ respecto ◦ a la misma base, si calculamos la pendiente y el ´angulo resultante es + an − 45 , entonces los dos casilleros est´ en la misma diagonal. En general, para poder encontrar la pendiente de una recta, basta con conocer dos puntos de esa recta y calcular la diferencia entre las coordenadas de ambos puntos. Por ejemplo, si queremos calcular la pendiente ∆y y al de la recta de la figura 4, calculamos el ∆x = x2 − x1 y el ∆y = y2 − y1 . Despu´es, calculamos ∆x resultado le calculamos la tangente.

Figura 4: C´ alculo de la pendiente de una recta Como la tan 45 = 1, eso significa que el ∆x y el ∆y deben ser iguales. En nuestro caso, como no queremos que las reinas est´en en la misma diagonal, vamos a exigir que esas diferencias sean distintas. De esta forma, podemos definir la restricci´on para las diagonales de la siguiente forma: |xi − xj | 6= |i − j|

∀i 6= j con i y j ∈ N

Lo bueno de este modelo, comparado con el anterior, es que reduce en forma dr´astica el espacio de b´ usqueda, quedando en n!. De esta forma, para n = 10, el espacio de b´ usqueda es 106 aproximadamente.

6.

Modelo General Considerando los modelos anteriormente descritos, podemos formalizarlos de acuerdo a lo siguiente:

6.1.

Modelo 1

Variables :  xij =

1 0

si existe una reina en la posici´on (i, j) si no

Dominio : {0, 1}

6

Restricciones : n X j=1 n X i=1 n X n X

Xij

=

1

; ∀i = {1, . . . , n}

Restricci´on en las Filas

Xij

=

1

; ∀j = {1, . . . , n}

Restricci´on en las Columnas

Xij

≤ 1

; ∀k = {3, . . . , 2n − 1}

Xij

≤ 1

; ∀k = {1 − n, . . . , n − 1}

Restricci´on en las Diagonales positivas

i=1 j=1

| {z } i+j=k

n X n X

Restricci´on en las Diagonales negativas

i=1 j=1

| {z } i−j=k

6.2.

Modelo 2

Variables : xi = posici´ on de la reina en la fila i. Dominio : {1, . . . , n} Restricciones : xi = 6 xj ∀i 6= j con i y j ∈ N Restricci´on en las Columnas |xi − xj | = 6 |i − j| ∀i 6= j con i y j ∈ N Restricci´on en las Diagonales Este modelo se puede implementar como un vector de largo n con una secuencia correspondiente a una permutaci´on de los valores de 1 . . . n. De esta forma no es necesario verificar las restricciones en las filas o las columnas ya que el mismo modelo se encarga de asegurar que no existan violaciones en este sentido. As´ı, se pueden abocar todos los esfuerzos a la verificaci´on de las restricciones en las diagonales.

7.

Descripci´ on de los Algoritmos

Los algoritmos implementados para la resoluci´on del problema planteado fueron b´asicamente tres: el desarrollado por Minton [17], que se basa en Hill-Climbing, el GRASP [18, 19, 20], que se basa en una etapa de preproceso y en otra de postproceso de una soluci´on y en Simulated Annealing [21], que se basa en un proceso de enfriamiento. Adem´ as, cada uno de los algoritmos anteriores fue modificado para comprobar el aporte de sus distintos componentes a la resoluci´on del problema. El detalle de cada algoritmo se describe a continuaci´on.

7.1.

Algoritmo de Minton

El algoritmo de Minton posee dos etapas: Etapa de Preproceso: Una etapa de preproceso crea una asignaci´on inicial usando un algoritmo greedy que itera dentro de las filas, ubicando cada reina en la columna donde tenga menos conflictos con las reinas previamente ubicadas. Etapa de Reparaci´ on: Para hacer una reparaci´on, el programa selecciona una reina que este en conflicto y la mueve a otra columna donde tenga menos cantidad de conflictos utilizando un algoritmo Hill-Climbing. Esta fase se repite hasta que se encuentre una soluci´on. A continuaci´ on se describir´ an las implementaciones efectuadas del algoritmo de Milton.

7

7.1.1.

Algoritmo original

´ Lo primero fue implementar el algoritmo de acuerdo a la descripci´on que se hace en [17]. Este comienza con la generaci´on de una soluci´ on inicial mediante un greedy, el cual va ubicando las reinas en las posiciones donde menos conflictos produzcan respecto a las reinas previamente instanciadas. Una vez que se ha construido la soluci´on inicial, ´esta se repara utilizando un Hill-Climbing. Para ello, el algoritmo posee un registro con las reinas en conflicto, el cual va actualizando despu´es de cada movimiento. As´ı, en cada iteraci´on, se toma la reina con m´ as conflictos y se mueve a una posici´on donde produzca el menor n´ umero de violaciones a las restricciones. Esto se repite hasta que se encuentre una soluci´on v´alida o se efect´ uen una cantidad de iteraciones determinadas. Si al t´ermino de la etapa de reparaci´ on no se ha encontrado una soluci´on factible, el algoritmo comienza desde cero con la aplicaci´ on del greedy ubicando la primera reina al azar para evitar que siempre se construya la misma soluci´ on inicial. Esto se repite hasta que se encuentre una soluci´on final factible o se cumpla con un n´ umero determinado de restart. El Algoritmo se define de acuerdo a lo siguiente: Representaci´ on: Xi la columna donde se ubica la reina en la fila i. Funci´ on de evaluaci´ on: cantidad de restricciones violadas. Movimiento: cambio de posici´ on de la reina a otra columna en la misma fila. Criterio de selecci´ on de las variables: mayor cantidad de conflictos. Criterio de aceptaci´ on: mejor mejora. Criterio de t´ ermino: m´ aximo n´ umero de iteraciones o encuentro de una soluci´on factible. N´ umero de restarts: 10 Soluci´ on inicial: creada por un Greedy En Pseudo c´ odigo: Procedimiento Minton (n reinas) s =crear una configuraci´ on inicial (greedy) // instanciar el arreglo violaciones for i