Решение проблемы N-Queens ... Как далеко мы можем пойти?

Question

Проблема N-Королев:

В этой задаче указывается, что, учитывая шахматную доску размером N на N, найдите различные перестановки, в которых N досок могут быть помещены на доску без какой-либо угрозы друг другу.

Мой вопрос:
Какое максимальное значение N, для которого программа может рассчитать ответ в разумные сроки? Или какой самый большой N мы видели до сих пор?

Вот моя программа на CLPFD (Пролог):

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).

Эта программа прекрасно работает, но время, которое она занимает, увеличивается с увеличением N. Вот пример выполнения:

?- queens(4,L).

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

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

No

Это означает, что вы помещаете 4 королевы в строку 2 в столбце 1, строку 4 в столбце 2, строку 1 в 3 и строку 3 в 4. (На шахматной доске 4 на 4)

Теперь давайте посмотрим, как работает эта программа (время, затрачиваемое на вычисление первой перестановки):
Для N = 4,5 ..... 10 вычислений в секунду
Для N = 11-30 занимает от -1-3 секунд
Для N = 40..50 По-прежнему рассчитывается в течение минуты
При N = 60 он выходит из глобального стека (пространство поиска огромно).

Это была проблема с домашним заданием в прошлом. (Первоначальной проблемой было просто закодировать N-Queens)

Мне также интересно видеть альтернативные реализации на других языках (которые работают лучше, чем моя реализация) или Если есть место для улучшения в моем алгоритме / программе

Answer 1

Это обсуждение объединяет три разные вычислительные задачи: (1) поиск решения проблемы N королев, (2) перечисление всех решений для некоторого фиксированного N и (3) подсчет всех решений для некоторого фиксированного N. Первый сначала проблема выглядит сложной для такого размера платы, как N = 8. Однако, как предполагает Википедия, в некоторых ключевых случаях легко, когда N велико. Королевы на большой доске не так много общаются. За исключением ограничений памяти, алгоритм эвристического восстановления становится все легче и проще с увеличением N.

Перечисление каждого решения - это другое дело. Вероятно, это можно сделать с помощью хорошего динамического программного кода, размер которого настолько велик, что нет смысла читать выходные данные.

Самым интересным вариантом вопроса является подсчет решений. Уровень техники обобщен в невероятной ссылке, известной как Энциклопедия целочисленных последовательностей . Он был рассчитан до N = 26. Я предполагаю, что для этого также используется динамическое программирование, но в отличие от случая перечисления каждого решения, алгоритмическая проблема гораздо глубже и открыта для дальнейших достижений.

Answer 2

Лорен Печтель сказала: «Теперь для настоящего безумия: 29 заняло 9 секунд. 30 заняло почти 6 минут! "

Это удивительное отсутствие предсказуемости сложности возврата при разных размерах доски было частью этой головоломки, которая меня больше всего интересовала. В течение многих лет я составлял список «подсчетов» шагов алгоритма, необходимых для нахождения первого решения для каждого размера платы - с использованием простого и хорошо известного алгоритма «глубина в начале» в рекурсивной функции C ++. .

Вот список всех этих «подсчетов» для плат до N = 49 ... минус N = 46 и N = 48, которые все еще находятся в стадии разработки :

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

(в энциклопедии целочисленных последовательностей (OEIS) это указано как A140450 )

Эта страница содержит ссылку на список подходящих первых решений.

(Мой список Первые решения - это порядковый номер OEIS A141843 )

В первую очередь я не записываю, сколько времени обработки требует каждое решение, а скорее записываю, сколько неудачных размещений ферзей потребовалось до обнаружения алгоритмически первого решения каждой платы. Конечно, скорость размещения ферзей зависит от производительности процессора, но, учитывая быстрый тестовый запуск для конкретного процессора и определенного размера платы, легко подсчитать, сколько времени потребовалось для решения одного из этих «найденных» решений.

Например, на процессоре Intel Pentium D 3,4 ГГц с использованием одного процессора -

• При N = 35 моя программа «помещала» 24 миллиона королев в секунду, и для поиска первого решения потребовалось всего 6 минут.
• При N = 47 моя программа «помещала» 20,5 млн. Королев в секунду и занимала 199 дней.

Мой текущий 2,8 ГГц i7-860 работает около 28,6 млн. Королев в секунду, пытаясь найти первое решение для N = 48. До настоящего времени потребовалось более 550 дней (теоретически, если оно никогда не было прервано), чтобы безуспешно разместить 1 369 331 731 000 000 (и быстро растущих) королев.

Мой веб-сайт (пока) не показывает никакого кода на C ++, но я даю ссылку на этой веб-странице на мою простую иллюстрацию каждого из 15 шагов алгоритма, необходимых для решения доски N = 5.

Это действительно восхитительная головоломка!

Answer 3

Какую систему Prolog вы используете? Например, в последних версиях SWI-Prolog вы можете легко найти решения для N = 80 и N = 100 за доли секунды, используя ваш оригинальный код. Многие другие системы Prolog будут намного быстрее, чем это.

Проблема с N-ферзями даже описана в одном из онлайн-примеров SWI-Prolog, доступного как CLP (FD) queens в SWISH.

Пример с 100 королевами :

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

SWISH также показывает отличные изображения решений.

Вот анимированный GIF, показывающий полный процесс решения для N = 40 королев с SWI-Prolog:

Answer 4

короткое решение, представленное Раймондом Хеттингером на pycon: easy ai в 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

вычисление всех перестановок не масштабируется, хотя (O(n!))

Answer 5

Какое максимальное значение N, для которого программа может рассчитать ответ в разумные сроки? Или какой самый большой N мы видели до сих пор?

Нет предела. То есть проверка достоверности решения обходится дороже, чем создание одного решения плюс семь симметричных.

См. Википедия: «Существуют явные решения для размещения n ферзей на доске n × n для всех n ≥ 4, не требуя комбинаторного поиска вообще». .

Answer 6

Что касается самого большого N, решаемого компьютерами, в литературе есть ссылки, в которых было найдено решение для N около 3 * 10 ^ 6 с использованием алгоритма восстановления конфликта (то есть локального поиска). См., Например, классическую статью [ Sosic and Gu ].

Что касается точного решения с возвратом, существует некоторая умная эвристика ветвления, которая позволяет получить правильные конфигурации практически без возврата. Эту эвристику также можно использовать для поиска решения проблемы first-k : после нахождения начальной правильной конфигурации поиск возвращается, чтобы найти другие действительные конфигурации поблизости.

Ссылки для этих почти идеальных эвристик: [ Kale 90 ] и [ San Segundo 2011 ]

Answer 7

Я вытащил старую программу на Delphi, которая подсчитывала количество решений для любого размера платы, сделала быструю модификацию, чтобы остановить ее после одного нажатия, и я вижу странную картину в данных:

Первая доска, для решения которой потребовалась более 1 секунды, была n = 20. 21, но была решена за 62 миллисекунды. (Примечание: это основано сейчас, а не на какой-либо высокоточной системе.) 22 заняло 10 секунд, не повторяться до 28.

Я не знаю, насколько хороша оптимизация, поскольку изначально это была высокооптимизированная процедура, когда правила оптимизации были очень разными. Я сделал одну вещь, которая сильно отличается от большинства реализаций, - у нее нет платы. Скорее, я отслеживаю, какие столбцы и диагонали атакованы, и добавляю по одной королеве на строку. Это означает, что 3 проверенных массива на каждую проверенную ячейку и никакого умножения. (Как я уже сказал, с тех пор, когда правила сильно отличались.)

Теперь для настоящего безумия: 29 заняло 9 секунд. 30 заняло почти 6 минут!

Answer 8

Если вы хотите только 1 решение, его можно найти жадно за линейное время O (N). Мой код на 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

Здесь, однако, печать занимает O (N ^ 2) времени, а также Python является более медленным языком, любой может попробовать реализовать его на других языках, таких как C / C ++ или Java. Но даже с python он получит первое решение для n = 1000 в течение 1 или 2 секунд.

Answer 9

Фактически ограниченное случайное блуждание (генерация и тестирование), как то, что обрисовал Бакоре, - это путь, если вам просто нужно несколько решений, потому что они могут быть сгенерированы быстро. Я сделал это для класса, когда мне было 20 или 21, и опубликовал решение в Журнале Паскаля, Ада и Модула-2, март 1987 года, «Пересмотренная проблема Квинса». Я только что вычистил код из этой статьи сегодня (а это очень неэффективный код) и после исправления пары проблем генерировал N = 26 ... N = 60 решений.