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

Ответ 1

краткое решение, представленное raymond hettinger на pycon: easy ai in 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!))

Ответ 2

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

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

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

Ответ 3

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

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

Здесь список всех этих "подсчетов" для плат до N = 49... минус N = 46 и N = 48, которые все еще находятся в процессе выполнения:

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

(Я получил это в Encyclopedia of Integer Sequences (OEIS) как A140450)

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

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

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

Например, на процессоре Intel Pentium D с тактовой частотой 3,4 ГГц, используя один процессорный поток -

• Для N = 35 моя программа "разместила" 24 миллиона ферзей в секунду и заняла всего 6 минут, чтобы найти первое решение.
• Для N = 47 моя программа "разместила" 20,5 миллионов королеве в секунду и заняла 199 дней.

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

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

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

Ответ 4

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

Проблема N-queens даже показана в одном из онлайн-примеров 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 in 0.299 seconds (100% CPU, 9964202 Lips)

SWISH также отображает изображение решений nices.

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

Ответ 5

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

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

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

Ответ 6

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

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

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

Ответ 7

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

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

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

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

Ответ 8

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

Ответ 9

Если вам нужно только 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 секунд.

Ответ 10

Каково время работы (ЦП) первого решения N-Queen?