Может ли головоломка N-Queens теоретически быть решена за полиномиальное время? Если да, то в чем его лучшая сложность? Я нашел много алгоритмов, но я не нашел, что такое временная сложность. Есть ли какие-либо документы или документы, дающие точное количество его сложности?
(P.S. Явное решение очень интересно, но я забыл сказать, что хочу найти все решения.)
Эта ссылка ссылается на "хорошо известное" явное решение. Его можно вычислить в линейном времени:
n четный, но не форма (n mod 6 = 2). Поместите королев на квадраты (m, 2m) и (n/2 + m, 2m-1) при m = 1, 2,.,, n/2
n четный, но не форма (n mod 6 = 0) и Поместите королев на квадраты (m, 1+ (2 (m-1) + n/2 - 1) mod n) и (n + 1-m, n- (2 (m-1) + n/2 -1) mod n) при m = 1,2,..., n/2
n нечетно. Используйте (1) или (2), в зависимости от того, что подходит, на n - 1 и продолжайте с королевой в (n, n).
Обратите внимание, что перечисление всех решений займет гораздо больше времени. Количество решений растет сверхэкспоненциально с размером доски (http://oeis.org/A000170), поэтому их невозможно перечислить даже с временем 2^O(x) (но только O(n) требуется пространство).
Вы хотите найти одно решение или все решения? Если вы хотите найти только одно решение, это можно сделать тривиально, согласно Википедии.
Существуют явные решения для размещения n ферзей на плате n × n, не требуя комбинаторного поиска.