Asdas

”El Problema de las N-Reinas”
Andreas Spading

Pablo Itaim Ananias

Valpara´ 01 de Julio del 2005
ıso,
Resumen
El problema de las n -Reinas (n-Queens Problem ) es muy antiguo, propuesto por primera vez en el a˜o
n
1848, consiste en encontrar una asignaci´n a n reinas en un tablero de ajedrez de n x n de modo tal, que
o
´stas no se ataquen. El presente trabajo presenta el problema encuesti´n, muestra un ejemplo sencillo
e
o
de ´l y profundiza en las diferentes alternativas de modelamiento y m´todos de resoluci´n existentes.
e
e
o
Adem´s, se muestra un ejemplo de resoluci´n del problema utilizando un algoritmo Branch and Bound.
a
o

1.

Introducci´n
o

El problema de las n -Reinas consiste en encontrar una distribuci´n de n reinas en un tablero de ajedrez
o
den x n de modo tal, que ´stas no se ataquen. As´ no pueden encontrarse dos reinas en la misma fila,
e
ı,
columna o diagonal.
Este problema tiene 2 Versiones. La m´s simple consiste en encontrar exactamente una soluci´n v´lida
a
oa
para un valor n dado. La otra versi´n, m´s dif´
o
a
ıcil, consiste en encontrar todas las soluciones posibles para
un valor n.
Fue propuesto para n = 8 en ela˜o 1848 en un trabajo an´nimo [1], siendo posteriormente atribuido a
n
o
Max Bezzel. Sin embargo, la publicaci´n detallada m´s antigua que se conoce fue realizada por Nauck [2]
o
a
en 1850. Ese mismo a˜o, Gauss postul´ la existencia de 72 soluciones para n = 8. Posteriormente, en el a˜o
n
o
n
1874, Glaisher [3] prob´ la existencia de 92 soluciones.
o
La investigaci´n sobre este temano ha parado hasta hoy por lo que existe una amplia variedad de
o
algoritmos sugeridos para su resoluci´n. Muchas de las soluciones planteadas se basan en proporcionar una
o
f´rmula espec´
o
ıfica para colocar las reinas o extrapolar conjuntos peque˜os de soluciones para proporcionar
n
soluciones para valores de n m´s grandes.
a
Observaciones emp´
ıricas de problemas de peque˜o tama˜omuestran que el n´mero de soluciones crece
n
n
u
en forma exponencial al ir aumentando el valor de n [4].
Se puede observar que este problema tiene una soluci´n (Q(1) = 1) para n = 1, no tiene soluci´n para
o
o
n = 2 y n = 3 y tiene 2 soluciones para n = 4.

2.

Definici´n del Problema:
o

El Problema de las n -Reinas consiste en encontrar una distribuci´n de n reinas en un tablero de nx n
o
de modo tal, que ´stas no se ataquen. As´ no pueden encontrarse dos reinas en la misma fila, columna o
e
ı,
diagonal.
Este Problema tiene 2 Versiones. La m´s simple consiste en encontrar exactamente una soluci´n v´lida
a
oa
para un valor n dado. La otra versi´n, m´s dif´
o
a
ıcil, consiste en encontrar todas las soluciones posibles para
un valor n.
Se puede observar que esteproblema tiene una soluci´n (Q(1) = 1) para n = 1, no tiene soluci´n para
o
o
n = 2 y n = 3 y tiene 2 soluciones para n = 4. La Tabla 1 muestra el n´mero total de Soluciones Q(n) para
u
4 ≤ n ≤ 20 [5] [6].
Para solucionar este problema, se han dise˜ado numerosos Algoritmos basados en algunos como Backn
tracking, Algoritmos Gen´ticos, B´squeda local con resoluci´n de conflictos, programaci´nentera y redes
e
u
o
o
neuronales entre otros. Adem´s, el Problema de las n reinas pertenece a la clase de problemas NP-completos
a
[7], pero se resuelve f´cilmente en tiempo polinomial cuando solamente se busca una soluci´n [4].
a
o

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.51295.815.104
666.090.624
4.968.057.848
39.029.188.884

Cuadro 1: N´mero total de soluciones Q(n) para 4 ≤ n ≤ 20
u
Existen soluciones anal´
ıticas donde se da una f´rmula expl´
o
ıcita para la localizaci´n de las reinas o bien
o
se encadenan soluciones obtenidas para valores menores de n [8] [9]. El problema con estas soluciones es que
generan un n´mero muy peque˜o de soluciones.
u...