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

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

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

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

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

Лорен Пехтель сказала: «А теперь настоящее безумие: 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 дней.

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

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

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

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

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

Пример с 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 также показывает вам красивые изображения решений.

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

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

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

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

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

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

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

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

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

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

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

Фактически ограниченное случайное блуждание (генерация и тестирование), подобное тому, что описано в bakore, - это правильный путь, если вам просто нужно несколько решений, потому что они могут быть сгенерированы быстро. Я сделал это для класса, когда мне было 20 или 21 год, и опубликовал решение в журнале Pascal, Ada & Modula-2, март 1987 г., "The Queens Problem Revisited". Я просто стряхнул пыль с кода из этой статьи сегодня (а это очень неэффективный код) и после исправления пары проблем сгенерировал N = 26 ... N = 60 решений.

Если вам нужно только одно решение, его можно с жадностью найти за линейное время O (N). Мой код на питоне:

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 секунд.