Решение проблемы N-Куинса …, Как далеко мы можем пойти?

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

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

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

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

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

На этой странице есть ссылка на список соответствующих первых решений.

(Мой список First Solutions - это порядковый номер 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.

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

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

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

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

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

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

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

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

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

This discussion conflates three different computational problems: (1) Finding a solution to the N queens problem, (2) Listing all solutions for some fixed N, and (3) counting all of the solutions for some fixed N. The first problem looks tricky at first for a size of board such as N=8. However, as Wikipedia suggests, in some key ways it is easy when N is large. The queens on a large board don't communicate all that much. Except for memory constraints, a heuristic repair algorithm has an easier and easier job as N increases.

Listing every solution is a different matter. That can probably be done with a good dynamic programming code up to a size that is large enough that there is no point in reading the output.

The most interesting version of the question is to count the solutions. The state of the art is summarized in a fabulous reference known as The Encyclopedia of Integer Sequences. It has been computed up to N=26. I would guess that that also uses dynamic programming, but unlike the case of listing every solution, the algorithmic problem is much deeper and open to further advances.