Czy układanka N-Queens teoretycznie może zostać rozwiązana w czasie wielomianowym? Jeśli tak, jaka jest najlepsza złożoność tego? Znalazłem wiele algorytmów, ale nie znalazłem tego, czym dokładnie jest złożoność czasu. Czy są jakieś papiery lub dokumenty dające dokładną liczbę złożoności?Jaka jest najlepsza złożoność zagadek N-Queens?
(PS: Wyraźna rozwiązanie jest bardzo interesująca, ale zapomniałem powiedzieć, życzę, aby znaleźć wszystkie rozwiązania.)
masz na myśli znalezienie jednego rozwiązania lub wszystkie rozwiązania? Jeśli chcesz znaleźć tylko jedno rozwiązanie, można to zrobić w sposób trywialny, zgodnie z Wikipedii.
Explicit istnieją rozwiązania umieszczania n królowych na pokładzie n x n, nie wymagając jakiejkolwiek kombinatoryczne wyszukiwania.
Ten link podaje "dobrze znane" jawne rozwiązanie. To może być obliczona w czasie liniowej:
n jest parzyste, ale nie w formie (6 mod n = 2). Umieść królowe na kwadratach (m, 2m) i (n/2 + m, 2m-1) dla m = 1, 2,. . . , N/2
n jest parzyste, ale nie w formie (6 mod n = 0) i Place królowych na placach (m, 1 + (2 (M-1) + n/2 - 1) mod n) i (n + 1-m, n- (2 (m-1) + n/2 -1) mod n) dla m = 1,2, ..., n/2
n jest nieparzyste. Użyj (1) lub (2), w zależności od tego, co jest właściwe, na n - 1 i rozciągnij z królową na (n, n).
Zauważ, że wyliczając wszystkie rozwiązania zajęłoby znacznie dłużej. Liczba rozwiązań rośnie super-wykładniczo wraz z rozmiarem płyty (http://oeis.org/A000170), więc nie można ich wyliczyć nawet z czasem 2^O(x) (ale potrzebna jest tylko przestrzeń O(n)).
Pomijany link wiki: http://en.wikipedia.org/wiki/Eight_queens_puzzle#Explicit_solutions – biziclop
Czy potrafisz znaleźć jednoznaczne rozwiązanie? Próbowałem i nie udało mi się. Źródłowe referencje do WP są tylko gotówką, ale widziałem jednoznaczne rozwiązanie w Internecie. –
Przykro mi, mam na myśli znalezienie wszystkich rozwiązań. – Rosetta