Resolviendo el problema de N-Queens… ¿Hasta dónde podemos llegar?

StackOverflow https://stackoverflow.com/questions/1863531

Pregunta

El problema de las N-Reinas:

Este problema establece que dado un tablero de ajedrez de tamaño N por N, encuentre las diferentes permutaciones en las que se pueden colocar N reinas en el tablero sin que ninguna se amenace entre sí.

Mi pregunta es:
¿Cuál es el valor máximo de N para el cual un programa puede calcular la respuesta en un tiempo razonable?¿O cuál es la N más grande que hemos visto hasta ahora?

Aquí está mi programa en CLPFD (Prólogo):

generate([],_).
generate([H|T],N) :-
   H in 1..N ,
   generate(T,N).

lenlist(L,N) :-
   lenlist(L,0,N).

lenlist([],N,N).
lenlist([_|T],P,N) :-
   P1 is P+1,
   lenlist(T,P1,N).

queens(N,L) :-
   generate(L,N),lenlist(L,N),
   safe(L),
   !,
   labeling([ffc],L).

notattack(X,Xs) :-
   notattack(X,Xs,1).

notattack(X,[],N).
notattack(X,[Y|Ys],N) :-
   X #\= Y,
   X #\= Y - N,
   X #\= Y + N,
   N1 is N + 1,
   notattack(X,Ys,N1).

safe([]).
safe([F|T]) :-
   notattack(F,T),
   safe(T).

Este programa funciona bien, pero el tiempo que lleva sigue aumentando con N.Aquí hay una ejecución de muestra:

?- queens(4,L).

L = [2, 4, 1, 3] ;

L = [3, 1, 4, 2] ;

No

Esto significa que colocas las 4 reinas en la fila 2 de la columna 1, la fila 4 en la columna 2, la fila 1 en 3 y la fila 3 en 4 (en un tablero de ajedrez de 4 por 4).

Ahora veamos cómo funciona este programa (tiempo necesario para calcular la primera permutación):
Para N=4,5.....10 Calcula en un segundo
Para N=11-30 Tarda entre -1-3 segundos
Para N=40..50 Todavía se calcula en un minuto
En N = 60, sale de la pila global (el espacio de búsqueda es enorme).

Este fue un problema de tarea anterior.(El problema original era simplemente codificar N-Queens)

También estoy interesado en ver implementaciones alternativas en otros lenguajes (que funcionan mejor que mi implementación) o si hay margen de mejora en mi algoritmo/programa.

¿Fue útil?

Solución

a corto solución presentada por Raymond Hettinger en PyCon: fácil ai en pitón 

#!/usr/bin/env python
from itertools import permutations
n = 12
cols = range(n)
for vec in permutations(cols):
    if (n == len(set(vec[i] + i for i in cols))
          == len(set(vec[i] - i for i in cols))):
        print vec

computar todas las permutaciones no es escalable, aunque (O(n!))

Otros consejos

Esta discusión confunde tres problemas de cálculo diferentes: (1) encontrar una solución al problema de la N reinas, (2) Perfil de todas las soluciones para algunos N fijo, y (3) contar todas las soluciones para algunos fijo N. La primera problema parece difícil al principio para un tamaño de la junta tal como N = 8. Sin embargo, como sugiere la Wikipedia, en algunos aspectos clave es fácil cuando N es grande. Las reinas en un gran tablero no se comunican todo lo que mucho. A excepción de las limitaciones de memoria, un algoritmo heurístico de reparación tiene un trabajo más fácil y más fácil a medida que N aumenta.

Listing cada solución es un asunto diferente. Esto probablemente se puede hacer con un buen código de programación dinámica hasta un tamaño que es lo suficientemente grande que no hay ningún punto en la lectura de la salida.

La versión más interesante de la cuestión es contar las soluciones. El estado de la técnica se resume en una referencia fabulosa conocido como La Enciclopedia de secuencias del número entero . Se ha calculado hasta N = 26. Yo supongo que eso también utiliza la programación dinámica, pero a diferencia del caso de la inclusión de todas las soluciones, el problema algorítmico es mucho más profundo y abierto a nuevos avances.

  

Loren Pechtel dijo: "Ahora un poco de locura real: 29 tomó 9 segundos.   30 tomó casi 6 minutos! "

Este fascinante falta de previsibilidad en retroceso-complejidad para los diferentes tamaños de tablero era parte de este rompecabezas que más me interesa. Durante años he sido la creación de una lista de los 'cuenta' de etapas de algoritmos necesarios para encontrar el primera solución para cada tamaño del tablero - utilizando el algoritmo simple y bien conocido primero en profundidad, en un C recursiva ++ función.

Aquí hay una lista de todos aquellos 'cuenta' para placas hasta N = 49 ... menos N = 46 y N = 48, que son todavía trabajo en progreso

http://queens.cspea.co.uk/csp-q- allplaced.html

(Tengo que aparece en la Enciclopedia de secuencias del número entero (OEIS) como A140450 )

Esa página incluye un enlace a una lista de las primeras soluciones de juego.

(Mi lista de Las primeras soluciones es el número de secuencia OEIS A141843 )

Yo no grabo principalmente la cantidad de tiempo de procesamiento de cada solución exige, sino que grabo cómo se necesitaban muchas reinas colocaciones fallidos antes de haber descubierto mediante algoritmos primera solución de cada tablero. Por supuesto, la tasa de colocaciones reina depende del rendimiento de la CPU, pero teniendo en cuenta una rápida ejecución de prueba en una CPU particular y un tamaño de placa en particular, es una cuestión fácil de calcular el tiempo que tomó para resolver una de estas soluciones 'encontrado'.

Por ejemplo, en una CPU 3,4 GHz Intel Pentium D, utilizando un solo hilo CPU -

  • Para N = 35 mi programa 'colocado' 24 millones de reinas por segundo y se llevó sólo 6 minutos en encontrar la primera solución.
  • Para N = 47 mi programa 'colocado' 20,5 millones de reinas por segundo y se llevó 199 días.

Mi i7-860 a 2,8 GHz actual se agitaba a través de unos 28,6 millones reinas por segundo, tratando de encontrar la primera solución para N = 48. Hasta ahora se ha hecho cargo de 550 días (en teoría, si no hubiera sido ininterrumpida) para colocar sin éxito 1,369,331,731,000,000 (y subiendo rápidamente) reinas.

Mi sitio web no (todavía) no muestra ningún código C ++, pero yo sí dar un enlace en esa página web para mi simple ilustración de cada una de las 15 etapas de algoritmos necesarios para resolver la junta N = 5.

Es un delicioso rompecabezas de verdad!

¿Qué sistema está utilizando Prolog? Por ejemplo, con las versiones recientes de SWI-Prolog, se puede encontrar fácilmente soluciones para N = 80 y N = 100 en fracciones de segundo, utilizando su código original. Muchos otros sistemas Prolog serán mucho más rápido que eso.

El problema N-Queens es incluso aparece en uno de los ejemplos en línea de SWI-Prolog, disponible como CLP (FD) reinas en SWISH.

Ejemplo con 100 reinas : 

?- time((n_queens(100, Qs), labeling([ff], Qs))).
Qs = [1, 3, 5, 57, 59 | ...] .
2,984,158 inferences, 0.299 CPU in 0.299 seconds (100% CPU, 9964202 Lips)

SWISH también le muestra la imagen nices de soluciones.

Aquí es un GIF animado que muestra el proceso solución completa para N = 40 reinas con SWI-Prolog:

CLP (FD) proceso de la solución durante 40 reinas

En cuanto a cuál es el N más grande resuelto por computadoras, hay referencias en la literatura en las que se ha encontrado una solución para N alrededor de 3*10^6 utilizando un algoritmo de reparación de conflictos (es decir,busqueda local).Véase, por ejemplo, el artículo clásico de [Sosic y Gu].

En cuanto a la resolución exacta con retroceso, existen algunas heurísticas de ramificación inteligentes que logran configuraciones correctas casi sin retroceso.Estas heurísticas también se pueden utilizar para encontrar la primero-k soluciones al problema:Después de encontrar una configuración inicial correcta, la búsqueda retrocede para encontrar otras configuraciones válidas en las cercanías.

Referencias para estos casi perfecto las heurísticas son [col rizada 90] y [San Segundo 2011]

  

¿Cuál es el valor máximo de n para el cual un programa puede calcular la respuesta en tiempo razonable? O lo que es el N más grande que hemos visto hasta ahora?

No hay límite. Es decir, la comprobación de la validez de una solución es más costosa que la construcción de una solución más siete los simétricos.

Vea Wikipedia: existen "soluciones explícitos para colocar n reinas en una n × n tablero para todo n ≥ 4, que no requiere combinatoria buscar que sea. ".

Me arrastré a cabo un viejo programa de Delphi que contó el número de soluciones para cualquier tamaño del tablero dado, hice una modificación rápida para hacer que se detenga después de un hit y estoy viendo un extraño patrón en los datos:

La primera junta que se hizo cargo de 1 segundo para resolver era n = 20. 21 resolvió en 62 milisegundos, sin embargo. (Nota:. Esto se basa apagado Ahora, no cualquier sistema de alta precisión) 22 tardó 10 segundos, no se repetirán hasta el 28

.

No sé lo bueno que es la optimización ya que era originalmente una rutina altamente optimizado de cuando las reglas de optimización eran muy diferentes. Me hizo hacer una cosa muy diferente a la mayoría de las implementaciones, sin embargo - que no tiene ninguna junta. Más bien, yo estoy rastreando las columnas y diagonales son atacados y la adición de una reina por fila. Esto significa 3 búsquedas de matriz por célula probado y no multiplicación en absoluto. (Como dije, desde cuando las reglas eran muy diferentes.)

Ahora un poco de locura real: 29 tomó 9 segundos. 30 tomó casi 6 minutos!

En realidad limitada paseo aleatorio (generar y prueba) como lo indica bakore es el camino a seguir si sólo tiene un puñado de soluciones ya que estos se pueden generar con rapidez. Hice esto para una clase cuando era 20 o 21 y publicó la solución en el Diario de Pascal, Ada y Modula-2, marzo de 1987 "The Queens Problema Revisited". Acabo de desempolvado el código de ese artículo de hoy (y esto es un código muy ineficiente) y después de la fijación de un par de problemas han estado generando N = 26 N = 60 ... soluciones.

Si sólo desea 1 solución entonces se puede encontrar con avidez en el tiempo lineal O (N). Mi código en Python: 

import numpy as np

n = int(raw_input("Enter n: "))

rs = np.zeros(n,dtype=np.int64)
board=np.zeros((n,n),dtype=np.int64)

k=0

if n%6==2 :

    for i in range(2,n+1,2) :
        #print i,
        rs[k]=i-1
        k+=1

    rs[k]=3-1
    k+=1
    rs[k]=1-1
    k+=1

    for i in range(7,n+1,2) :
        rs[k]=i-1
        k+=1

    rs[k]=5-1

elif n%6==3 :

    rs[k]=4-1
    k+=1

    for i in range(6,n+1,2) :
        rs[k]=i-1
        k+=1

    rs[k]=2-1
    k+=1

    for i in range(5,n+1,2) :

        rs[k]=i-1
        k+=1

    rs[k]=1-1
    k+=1
    rs[k]=3-1

else :

    for i in range(2,n+1,2) :

        rs[k]=i-1
        k+=1

    for i in range(1,n+1,2) :

        rs[k]=i-1
        k+=1

for i in range(n) :
    board[rs[i]][i]=1

print "\n"

for i in range(n) :

    for j in range(n) :

        print board[i][j],

    print

Aquí, sin embargo la impresión toma tiempo O (n ^ 2) y también pitón ser un lenguaje más lento cualquiera puede tratar de implementarlo en otros lenguajes como C / C ++ o Java. Pero incluso con el pitón obtendrá la primera solución para n = 1000 dentro de 1 o 2 segundos.

Licenciado bajo: CC-BY-SA con atribución
No afiliado a StackOverflow
scroll top