N-Queens II

Q: Jaka jest złożoność czasowa problemu N-hetmanów II?

Backtracking jest ograniczony przez O(n!) : w pierwszym wierszu jest n możliwości, w następnym najwyżej n-1 i tak dalej. Przycinanie znacznie zmniejsza rzeczywistą pracę — do 856,189 częściowych plansz dla n = 12 . Złożoność pamięciowa wynosi O(n) .

TrudneNawroty

+10

Hetman atakuje każde pole w swoim wierszu, swojej kolumnie i na obu przekątnych, niezależnie od odległości. Dla danej liczby całkowitej n zwróć liczbę sposobów rozmieszczenia n hetmanów na planszy n × n tak, aby żadne dwa hetmany się nie atakowały.

Plansze różniące się na choćby jednym polu liczą się osobno, także ich lustrzane odbicia.

Funkcja

totalNQueens(n: integer) → integer

ninteger: rozmiar planszy i liczba hetmanów
Zwracainteger: liczba sposobów rozmieszczenia hetmanów tak, aby żaden nie atakował innego

Ograniczenia

1 ≤ n ≤ 12
Odpowiedź dla n = 12 wynosi 14,200, więc mieści się w 32-bitowej liczbie całkowitej.

Przykłady

Wejście: n = 4
Wyjście: 2
Wyjaśnienie: Zapisując numery kolumn z hetmanami w kolejnych wierszach od góry do dołu, otrzymujemy plansze 1, 3, 0, 2 i 2, 0, 3, 1: są swoimi lustrzanymi odbiciami, ale liczymy je jako dwa rozwiązania. Każdy inny wybór umieszcza dwa hetmany w tej samej kolumnie lub na tej samej przekątnej.

Pytanie dodatkowe

Czy potrafisz policzyć tylko te plansze, które pozostają różne po obróceniu i odbiciu lustrzanym planszy? Dla n = 8 92 plansze dzielą się na 12 takich grup.

Podpowiedzi

Otwieraj je po kolei. Każda zdradza trochę więcej.

Otwarte: 0 z 3

Rozwiązanie

Dwie hetmany w jednym wierszu zawsze się atakują, więc plansza to jedna kolumna na wiersz: n^n list, około 8.9 × 10^12 dla n = 12. Zamiast tego buduj planszę wiersz po wierszu, odrzucaj częściową planszę, gdy tylko hetman zostanie zaatakowany, i oznaczaj zajęte kolumny oraz przekątne, aby sprawdzenie pola wymagało trzech wyszukiwań.

Wypróbuj każde ustawienie, umieszczając jedną hetmanę w każdym wierszu

Poprawne, ale nie kończy się na największych testach

Intuicja

Zapisz ustawienie jako listę cols, w której dla każdego wiersza podana jest kolumna królowej, i przejdź przez wszystkie n^n list tak jak licznik. Hetmany w wierszach i < j atakują się, gdy cols[i] == cols[j] lub |cols[i] - cols[j]| == j - i, ponieważ przekątna przesuwa się o jedną kolumnę na wiersz. Każda lista jest sprawdzana raz, więc żadna plansza nie zostanie pominięta ani policzona dwukrotnie.

Nic nie przerywa działania wcześniej: konflikt w pierwszych dwóch wierszach nadal pozostawia n^(n-2) list. Dla n = 8 oznacza to 16,777,216 list dla 92 plansz; dla n = 12 — 8.9 × 10^12, czyli około 2,5 godziny przy nanosekundzie na listę.

Algorytm

Zacznij od cols wypełnionego zerami.
Dodaj 1 do licznika, jeśli żadna para wierszy i < j nie spełnia warunku cols[i] == cols[j] ani |cols[i] - cols[j]| == j - i.
Przejdź dalej jak w liczniku kilometrów: zaczynając od ostatniego wiersza, zmień każde wystąpienie n-1 na 0, a następnie dodaj 1 do pierwszego wpisu poniżej n-1.
Zatrzymaj się i zwróć licznik, gdy każdy wpis miał wartość n-1.

def totalNQueens(n):
    def is_valid(cols):
        # cols[r] is the column of the queen in row r, so rows never clash.
        for i in range(n):
            for j in range(i + 1, n):
                if cols[i] == cols[j] or abs(cols[i] - cols[j]) == j - i:
                    return False
        return True

    cols = [0] * n
    count = 0
    while True:
        if is_valid(cols):
            count += 1
        # Move to the next placement, like an odometer with n digits in base n.
        row = n - 1
        while row >= 0 and cols[row] == n - 1:
            cols[row] = 0
            row -= 1
        if row < 0:
            return count
        cols[row] += 1

Przeszukiwanie z nawrotami z wykorzystaniem zbiorów kolumn i przekątnych

Intuicja

Umieszczaj hetmany wiersz po wierszu i sprawdzaj każdy z nich w chwili umieszczania. Wypełnienie niższych wierszy nie uratuje zaatakowanego hetmana, więc pomiń to pole. Bezpieczny hetman wywołuje rekurencję dla następnego wiersza i jest usuwany po powrocie z wywołania; osiągnięcie wiersza n oznacza znalezienie jednej planszy.

Na pole (row, c) mogą atakować tylko trzy linie: jego kolumna, przekątna /, dla której row + c jest stałe, oraz przekątna \, dla której row - c jest stałe (dodaj n-1, aby indeksować ją od 0). Tablice flag cols, diag i anti sprowadzają test bezpieczeństwa do trzech odczytów. Każda linia może zawierać najwyżej jednego hetmana, więc wyczyszczenie flag po powrocie przywraca tablice do dokładnego poprzedniego stanu.

Wiersz k oferuje najwyżej n - k kolumn, więc przeszukiwanie jest ograniczone przez O(n!), przy użyciu O(n) pamięci.

Algorytm

Utwórz tablice flag cols o rozmiarze n oraz diag i anti o rozmiarze 2n-1; wszystkie ustaw jako wyłączone.
place(row): jeśli row == n, zwróć 1.
Dla każdej kolumny c pomiń ją, jeśli cols[c], diag[row + c] lub anti[row - c + n - 1] jest włączona.
W przeciwnym razie włącz trzy flagi, dodaj place(row + 1) do sumy, a następnie je wyłącz.
Zwróć sumę. Odpowiedzią jest place(0).

def totalNQueens(n):
    cols = [False] * n             # cols[c]: column c holds a queen
    diag = [False] * (2 * n - 1)   # diag[r + c]: that / diagonal holds a queen
    anti = [False] * (2 * n - 1)   # anti[r - c + n - 1]: that \ diagonal holds a queen

    def place(row):
        if row == n:
            return 1  # a queen in every row: one complete board
        count = 0
        for c in range(n):
            if cols[c] or diag[row + c] or anti[row - c + n - 1]:
                continue  # attacked: three lookups, no scan of the board
            cols[c] = diag[row + c] = anti[row - c + n - 1] = True
            count += place(row + 1)
            cols[c] = diag[row + c] = anti[row - c + n - 1] = False  # take it back
        return count

    return place(0)

Backtracking z użyciem masek bitowych

Intuicja

Wyszukiwanie z flagami nadal sprawdza wszystkie n kolumn każdego wiersza; maski bitowe przechodzą od razu do wolnych pól. Bit c oznacza kolumnę c w wypełnianym wierszu: cols przechowuje zajęte kolumny, a left i right pola atakowane wzdłuż każdej przekątnej. Następnie free = ~(cols | left | right) & full, gdzie full oznacza dolne n bitów, a free & -free to najniższe wolne pole. W następnym wierszu kolumna pozostaje zajęta, a atak na każdej przekątnej przesuwa się o jedną kolumnę.

Dla n = 4 i pierwszej hetmanki umieszczonej na bit = 0010 wiersz 1 otrzymuje free = 1000: kolumnę 3, znalezioną bez sprawdzania pozostałych. Dla n = 12 856,188 kroków pętli zastępuje 10,103,868 sprawdzeń pól. Kod w R tworzy naraz cały wiersz częściowych plansz, zamiast używać rekurencji.

Algorytm

Ustaw full = (1 << n) - 1.
count(cols, left, right): jeśli cols == full, zwróć 1.
Oblicz free = ~(cols | left | right) & full.
Dopóki free nie jest równe 0, pobierz bit = free & -free, usuń je z free i dodaj count(cols | bit, ((left | bit) << 1) & full, (right | bit) >> 1) do sumy.
Zwróć sumę. Odpowiedzią jest count(0, 0, 0).

def totalNQueens(n):
    full = (1 << n) - 1  # bit c stands for column c of the current row

    def count(cols, left, right):
        # cols: columns taken. left, right: squares of this row hit along a diagonal.
        if cols == full:
            return 1  # every column used: n queens placed
        total = 0
        free = full & ~(cols | left | right)
        while free:
            bit = free & -free  # the lowest free square
            free -= bit
            # Moving down a row shifts each diagonal attack one column over.
            total += count(cols | bit, ((left | bit) << 1) & full, (right | bit) >> 1)
        return total

    return count(0, 0, 0)

Pułapki i przypadki brzegowe

Indeksowanie anti za pomocą row - c bez dodania n-1. Java zgłasza wyjątek, C odczytuje dane spoza tablicy, a Python po cichu odczytuje flagę innej przekątnej za pomocą anti[-2].
Ustawianie rozmiaru tablic przekątnych na n zamiast 2n-1. row + c osiąga wartość 2n-2.
Niezerowanie flag po wywołaniu rekurencyjnym. W kolejnych gałęziach widoczne są hetmany, których już nie ma, przez co licznik maleje.
Pominięcie & full w free. ~x ustawia bity powyżej kolumny n-1, więc pętla wybiera pola spoza szachownicy; w Pythonie lub Ruby free staje się ujemne, a pętla nigdy się nie kończy.

Najczęstsze pytania3

Jaka jest złożoność czasowa problemu N-hetmanów II?

Backtracking jest ograniczony przez O(n!): w pierwszym wierszu jest n możliwości, w następnym najwyżej n-1 i tak dalej. Przycinanie znacznie zmniejsza rzeczywistą pracę — do 856,189 częściowych plansz dla n = 12. Złożoność pamięciowa wynosi O(n).

Czym różnią się N-Queens i N-Queens II?

N-Queens zwraca każdą planszę narysowaną wierszami tekstu; N-Queens II zwraca tylko ich liczbę. Wyszukiwanie jest takie samo, ale zliczanie nie przechowuje plansz, co pasuje do wersji z maską bitową.

Czy możesz wykorzystać symetrię, aby przyspieszyć rozwiązanie problemu N-hetmanów II?

Odbicie planszy od lewej do prawej daje inną poprawną planszę, więc policz plansze, na których pierwsza hetman znajduje się w kolumnach od 0 do n/2 - 1, a następnie podwój tę liczbę. Dla nieparzystego n dodaj jeden raz plansze, na których pierwszy hetman znajduje się w środkowej kolumnie.

def totalNQueens(n):
    # Wpisz kod tutaj

Test #1

Test #2

Argument

n = 4

Oczekiwany wynik

N-Queens II

Funkcja

Ograniczenia

Przykłady

Podpowiedzi

Rozwiązanie

Wypróbuj każde ustawienie, umieszczając jedną hetmanę w każdym wierszu

Przeszukiwanie z nawrotami z wykorzystaniem zbiorów kolumn i przekątnych

Backtracking z użyciem masek bitowych

Pułapki i przypadki brzegowe

Najczęstsze pytania3

Podobne zadania