algorithm - resuelto - Resolviendo el problema de N-Queens... ¿Hasta dónde podemos llegar?

problema de las n reinas

Question

El problema N-Queens:

Este problema indica 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 (Prolog):

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 toma 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 coloca las 4 reinas en la fila 2 en 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 empleado en calcular la primera permutación):
Para N = 4,5 ..... 10 Computa en un segundo
Para N = 11-30 Toma entre -1-3 segundos
Para N = 40..50 todavía 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 del pasado. (El problema original era solo para codificar N-Queens)

También estoy interesado en ver implementaciones alternativas en otros idiomas (que se desempeñan mejor que mi implementación) o si hay margen para mejorar mi algoritmo / programa

Answer 1

¿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?

No hay límite. Es decir, verificar la validez de una solución es más costoso que construir una solución más siete simétricas.

Consulte Wikipedia: "Existen soluciones explícitas para colocar n reinas en una tabla n × n para todo n ≥ 4, que no requieren búsqueda combinatoria en absoluto". .

Answer 2

Loren Pechtel dijo: "Ahora, por una verdadera locura: 29 tomaron 9 segundos. ¡30 tomaron casi 6 minutos!"

Esta fascinante falta de previsibilidad en la complejidad del retroceso para diferentes tamaños de tableros fue la parte de este rompecabezas que más me interesó. Durante años he estado construyendo una lista de los ''conteos'' de pasos de algoritmo necesarios para encontrar la primera solución para cada tamaño de placa: utilizando el algoritmo simple y conocido de profundidad primero, en una función recursiva de C ++.

Aquí hay una lista de todos esos ''recuentos'' para tableros de hasta N = 49 ... menos N = 46 y N = 48 que aún están en progreso :

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

(Tengo que aparece en la Enciclopedia de Secuencias de números enteros (OEIS) como A140450 )

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

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

Principalmente, no registro cuánto tiempo de procesamiento exige cada solución, sino que registro cuántas ubicaciones fallidas de reina fueron necesarias antes de descubrir la primera solución algorítmica de cada placa. Por supuesto, la tasa de ubicaciones reina depende del rendimiento de la CPU, pero dada una prueba rápida en una CPU particular y un tamaño de placa particular, es una cuestión fácil calcular cuánto tiempo tomó resolver una de estas soluciones "encontradas".

Por ejemplo, en una CPU Intel Pentium D 3.4GHz, usando un solo subproceso de CPU:

• Para N = 35 mi programa ''colocó'' 24 millones de reinas por segundo y tomó solo 6 minutos encontrar la primera solución.
• Para N = 47 mi programa ''colocó'' 20.5 millones de reinas por segundo y tomó 199 días.

Mi actual i7-860 de 2.8GHz está golpeando a través de unos 28.6 millones de reinas por segundo, tratando de encontrar la primera solución para N = 48. Hasta el momento, se han demorado más de 550 días (teóricamente, si nunca se hubiera interrumpido) para colocar sin éxito a 1.369.331.731.000.000 (y escalar rápidamente) las reinas.

Mi sitio web no muestra (todavía) ningún código C ++, pero le doy un enlace en esa página a mi ilustración simple de cada uno de los 15 pasos de algoritmo necesarios para resolver el tablero N = 5.

¡Es un rompecabezas verdaderamente delicioso!

Answer 3

¿Qué sistema Prolog estás usando? Por ejemplo, con las versiones recientes de SWI-Prolog, 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ápidos que eso.

El problema de las N-reinas aparece incluso en uno de los ejemplos en línea de SWI-Prolog, disponible como reinas CLP (FD) 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 te muestra la imagen de las soluciones.

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

Answer 4

En cuanto a cuál es la N más grande resuelta por las 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, búsqueda local). Ver por ejemplo el papel clásico de [ Sosic y Gu ].

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

Las referencias para estas heurísticas casi perfectas son [ Kale 90 ] y [ San Segundo 2011 ]

Answer 5

En realidad, el camino aleatorio restringido (generar y probar) como lo que se describe en detalle es el camino a seguir si solo necesita un puñado de soluciones, ya que éstas se pueden generar rápidamente. Hice esto para una clase cuando tenía 20 o 21 años y publiqué la solución en el Journal of Pascal, Ada & Modula-2, marzo de 1987, "The Queens Problem Revisited". Acabo de desempolvar el código de ese artículo de hoy (y este es un código muy ineficiente) y luego de solucionar un par de problemas he estado generando N = 26 ... N = 60 soluciones.

Answer 6

Esta discusión combina tres problemas computacionales diferentes: (1) Encontrar una solución al problema de las reinas N, (2) Enumerar todas las soluciones para algunos N fijos, y (3) contar todas las soluciones para algunos N. arreglados. El primer problema parece complicado al principio para un tamaño de tabla como N = 8. Sin embargo, como sugiere Wikipedia, en algunos aspectos clave es fácil cuando N es grande. Las reinas en una tabla grande no se comunican mucho. A excepción de las limitaciones de memoria, un algoritmo de reparación heurística tiene un trabajo más fácil a medida que N aumenta.

Listado de cada solución es un asunto diferente. Probablemente se puede hacer con un buen código de programación dinámica hasta un tamaño que sea lo suficientemente grande como para que no tenga sentido leer la salida.

La versión más interesante de la pregunta es contar las soluciones. El estado de la técnica se resume en una referencia fabulosa conocida como The Encyclopedia of Integer Sequences . Se ha calculado hasta N = 26. Supongo que eso también usa programación dinámica, pero a diferencia del caso de enumerar todas las soluciones, el problema algorítmico es mucho más profundo y abierto a nuevos avances.

Answer 7

Saqué un viejo programa de Delphi que contó la cantidad de soluciones para cualquier tamaño de placa, hice una rápida modificación para detenerlo después de un golpe y veo un patrón extraño en los datos:

Sin embargo, la primera placa que tardó 1 segundo en resolverse fue n = 20. 21 resueltos en 62 milisegundos. (Nota: Esto se basa ahora, no en ningún sistema de alta precisión). 22 tomó 10 segundos, no se repetirá hasta 28.

No sé qué tan buena es la optimización, ya que originalmente era una rutina altamente optimizada de cuando las reglas de optimización eran muy diferentes. Sin embargo, hice una cosa muy diferente a la mayoría de las implementaciones: no tiene placa. Más bien, estoy rastreando qué columnas y diagonales son atacadas y agregando una reina por fila. Esto significa 3 búsquedas de matrices por celda probada y ninguna multiplicación en absoluto. (Como dije, de cuando las reglas eran muy diferentes.)

Ahora, por una verdadera locura: 29 tomó 9 segundos. 30 tardó casi 6 minutos!

Answer 8

Si solo desea 1 solución, puede encontrarla 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 requiere O (N ^ 2) y Python es un lenguaje más lento que cualquiera puede intentar implementarlo en otros lenguajes como C / C ++ o Java. Pero incluso con python obtendrá la primera solución para n = 1000 en 1 o 2 segundos.

Answer 9

Una breve solución presentada por Raymond Hettinger en Pycon: Easy Ai en Python.

#!/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

aunque la computación de todas las permutaciones no es escalable ( O(n!) )