N-Queens II

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

Przeszukiwanie z nawrotami ma złożoność ograniczoną przez O(n!) : pierwszy wiersz ma n możliwości, następny co najwyżej n-1 i tak dalej. Sprawdzanie przekątnych znacznie ogranicza liczbę przypadków, do 856,189 częściowych plansz dla n = 12 . Nie jest znana żadna metoda wielomianowa zliczania rozwiązań, więc takie przeszukiwanie jest standardowym podejściem. Złożoność pamięciowa wynosi O(n) .

Q: Jak rozpoznać, na której przekątnej znajduje się kwadrat?

Przesunięcie o jeden krok po przekątnej / zwiększa numer wiersza o 1 i zmniejsza numer kolumny o 1, więc row + col nigdy się nie zmienia. Przesunięcie po przekątnej \ zwiększa obie wartości o 1, więc row - col nigdy się nie zmienia. Każda suma wskazuje jedną przekątną, a dodanie n-1 do różnicy zamienia ją w indeks tablicy z zakresu od 0 do 2n-2 .

TrudneNawroty

+10

Hetmańka na szachownicy atakuje każde pole w swoim wierszu, w swojej kolumnie i wzdłuż obu przekątnych, niezależnie od odległości. Otrzymujesz liczbę całkowitą n. Zwróć liczbę sposobów rozmieszczenia n hetmanek na szachownicy o wymiarach n × n, tak aby żadne dwie hetmanki się nie atakowały.

Dwa sposoby różnią się, gdy na jakimś polu w jednym z nich znajduje się hetmanka, a w drugim jest ono puste. Dlatego szachownica i jej odbicie lustrzane liczą się jako dwa sposoby, mimo że wyglądają podobnie.

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 kolumnę hetmana w każdym wierszu od góry do dołu, otrzymujemy plansze 1, 3, 0, 2 i 2, 0, 3, 1. Każda z nich jest lustrzanym odbiciem drugiej i liczą się jako dwa rozwiązania. Każdy inny wybór umieszcza dwa hetmany w tej samej kolumnie lub na tej samej przekątnej.

+10 ukrytych testów przy wysłaniu

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

Ustawienie jest określone przez wybór jednej kolumny dla każdego wiersza, ponieważ dwie hetmany w tym samym wierszu zawsze się atakują. Nadal daje to n^n możliwości, około 8.9 × 10^12 dla n = 12, więc nie możesz wypisać ich wszystkich. Dwa pomysły rozwiązują ten problem. Buduj planszę wiersz po wierszu i porzucaj częściową planszę, gdy tylko hetman zostanie zaatakowany. Dzięki temu liczba przeszukiwanych częściowych plansz dla n = 12 spada poniżej miliona. Zapisuj też, które kolumny i przekątne są zajęte, dzięki czemu sprawdzenie pola wymaga trzech odczytów zamiast skanowania wszystkich dotychczas ustawionych hetmanów.

Wypróbuj każde ustawienie, umieszczając po jednej hetmanie w każdym wierszu

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

Intuicja

Każdy wiersz musi zawierać dokładnie jedną hetmankę, więc rozmieszczenie to lista cols, w której cols[r] oznacza kolumnę hetmanki w wierszu r. Każdy element może być dowolną z n kolumn, więc istnieje n^n list. Przechodź przez wszystkie tak, jak licznik przebiegu: zwiększ ostatni element o jeden, a gdy przekroczy n-1, ustaw go z powrotem na 0 i przenieś zwiększenie na poprzedni element.

Dla każdej listy porównaj każdą parę wierszy i < j. Dwie hetmanki atakują się wzajemnie, gdy zajmują tę samą kolumnę, cols[i] == cols[j], lub tę samą przekątną. Na przekątnej ruch w dół o jeden wiersz oznacza przesunięcie o jedną kolumnę w lewo lub w prawo, więc dwie hetmanki leżą na tej samej przekątnej dokładnie wtedy, gdy różnica kolumn jest równa różnicy wierszy: |cols[i] - cols[j]| == j - i. Lista, która spełnia warunki dla każdej pary, opisuje poprawną planszę. Ponieważ sprawdzana jest każda lista, żadna nie zostaje pominięta ani policzona dwukrotnie.

To działa wolno, ponieważ algorytm nigdy nie kończy sprawdzania wcześniej. Dwie hetmanki na tej samej przekątnej w pierwszych dwóch wierszach przekreślają planszę, a mimo to licznik nadal próbuje wszystkich n^(n-2) sposobów wypełnienia pozostałych wierszy. Dla n = 8 oznacza to sprawdzenie 16,777,216 list, aby znaleźć 92 plansze. Dla n = 12 to około 8.9 × 10^12 list. Nawet przy jednej nanosekundzie na listę zajęłoby to około 2,5 godziny.

Algorytm

Rozpocznij od cols składającego się z samych zer: każda hetmanka znajduje się w kolumnie 0.
Sprawdź każdą parę wierszy i < j: lista jest nieprawidłowa, jeśli cols[i] == cols[j] lub |cols[i] - cols[j]| == j - i.
Jeśli żadna para się nie atakuje, zwiększ licznik o 1.
Zwiększaj cols jak licznik: zaczynając od ostatniego wiersza i idąc w górę, ustawiaj na 0 każdy element o wartości n-1, a następnie zwiększ o 1 pierwszy element, którego nie wyzerowano.
Gdy każdy element miał wartość n-1, oznacza to, że sprawdzono wszystkie n^n listy: zwróć licznik.

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

Cofanie się z użyciem zbiorów kolumn i przekątnych

Intuicja

Ustawiaj hetmany wiersz po wierszu, od góry, i sprawdzaj każdego nowego hetmana w chwili, gdy go ustawiasz. Jeśli jest atakowany, żaden sposób wypełnienia niższych wierszy tego nie naprawi, więc od razu pomiń to pole. Jeśli jest bezpieczny, rekurencyjnie przejdź do następnego wiersza, a gdy to wywołanie się zakończy, usuń hetmana i spróbuj następnej kolumny. Wywołanie, które osiąga wiersz n, ustawiło n bezpiecznych hetmanów i oznacza jedną planszę. To jest nawrotowe przeszukiwanie i mocno przycina przestrzeń: dla n = 12 odwiedza 856,189 częściowych plansz zamiast 8.9 × 10^12 kompletnych.

Druga część polega na szybkim sprawdzaniu pola. Niższe wiersze są puste, a w wierszu nowego hetmana nie ma innych hetmanów, więc pole (row, c) mogą atakować tylko trzy linie: jego kolumna, przekątna / i przekątna \. Wszystkie pola na tej samej przekątnej / mają tę samą wartość row + c, od 0 do 2n-2. Wszystkie pola na tej samej przekątnej \ mają tę samą wartość row - c, od -(n-1) do n-1, więc dodaj n-1, aby uzyskać indeks od 0 do 2n-2. Przechowuj trzy tablice flag: cols o rozmiarze n oraz diag i anti o rozmiarze 2n-1. Pole jest bezpieczne dokładnie wtedy, gdy wszystkie trzy flagi są wyłączone: trzy odczyty, O(1), podczas gdy porównanie z każdym dotychczas ustawionym hetmanem kosztowałoby O(n).

Na jednej linii może stać najwyżej jeden hetman, więc ustawienie hetmana włącza jego trzy flagi, a jego usunięcie ponownie je wyłącza, przywracając tablice do poprzedniego stanu. Na planszy 4 na 4 hetman na polu (0, 0) ustawia cols[0], diag[0] i anti[3]. W wierszu 1 kolumna 1 leży na anti[3], więc zostaje pominięta bez sprawdzania samego hetmana.

Pierwszy wiersz oferuje n kolumn, drugi najwyżej n-1 i tak dalej, więc przeszukiwanie jest ograniczone przez O(n!), a przekątne zmniejszają tę wartość znacznie poniżej tego ograniczenia. Dla n = 12 pętle sprawdzają łącznie 10,103,868 pól. Rekurencja ma głębokość n wywołań, a tablice przechowują około 5n flag, więc złożoność pamięciowa wynosi O(n).

Algorytm

Utwórz trzy tablice flag, wszystkie wyłączone: cols z n elementami, a diag i anti po 2n-1 elementów każda.
Napisz place(row). Jeśli row == n, zwróć 1: w każdym wierszu znajduje się bezpieczna hetman.
W przeciwnym razie dla każdej kolumny c pomiń ją, jeśli cols[c], diag[row + c] lub anti[row - c + n - 1] jest włączona.
Dla bezpiecznej kolumny 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)

Wycofywanie z użyciem masek bitowych

Intuicja

Wyszukiwanie z użyciem zbiorów jest szybkie, ale w każdym wierszu nadal sprawdza wszystkie n kolumn, z których większość jest atakowana. Maska bitowa pozwala od razu przejść do wolnych pól. Niech bit c liczby całkowitej oznacza kolumnę c w wierszu, który zaraz wypełnisz, i użyj trzech masek: cols — kolumn już zajętych, left — pól tego wiersza atakowanych w jednym kierunku po przekątnej oraz right — pól atakowanych w drugim kierunku.

Wolne pola można więc uzyskać za pomocą jednego wyrażenia: free = ~(cols | left | right) & full, gdzie full ma ustawione n najmłodszych bitów. free & -free wyodrębnia najniższy wolny bit, a odjęcie go pozwala przejść do następnego. Gdy umieszczasz hetmana na bit i przechodzisz o jeden wiersz niżej, jego kolumna pozostaje zajęta, a każdy atak po przekątnej przesuwa się o jedną kolumnę. Dlatego następny wiersz otrzymuje cols | bit, ((left | bit) << 1) & full oraz (right | bit) >> 1. Nie trzeba niczego cofać: każde wywołanie ma własne trzy liczby całkowite. Gdy cols == full, wszystkie n hetmanów są już umieszczone.

Weźmy n = 4 i pierwszego hetmana w kolumnie 1, bit = 0010, zapisując kolumnę 0 jako skrajny prawy bit. Wiersz 1 otrzymuje cols = 0010, left = 0100 i right = 0001, więc free = 1000: kolumna 3 jest jedynym wyborem i zostaje znaleziona bez sprawdzania kolumn 0, 1 ani 2.

Wyszukiwanie odwiedza te same częściowo wypełnione plansze co wersja ze zbiorami, ale teraz każdy krok pętli umieszcza hetmana. Dla n = 12 oznacza to 856,188 kroków zamiast 10,103,868 testów pól, przy kilku operacjach na liczbach całkowitych w każdym kroku. Czas działania nadal jest ograniczony przez O(n!), a rekurencja ma głębokość n wywołań. Kod R wykonuje te same operacje na maskach bez rekurencji: przechowuje w wektorze każdą częściowo wypełnioną planszę danego wiersza i rozbudowuje je wszystkie, po jednym wierszu naraz, więc trzyma w pamięci cały poziom plansz zamiast n wywołań.

Algorytm

Ustaw full = (1 << n) - 1, czyli maskę wszystkich n kolumn.
Napisz count(cols, left, right). Jeśli cols == full, zwróć 1.
Oblicz free = ~(cols | left | right) & full.
Gdy 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

Samo wyszukiwanie jest krótkie. Większość błędów dotyczy arytmetyki przekątnych i kroku cofania.

Używanie row - c jako indeksu bez dodania n-1. W Javie powoduje to wyjątek, w C odczytuje pamięć poza tablicą, a w Pythonie anti[-2] po cichu odczytuje znacznik innej przekątnej, więc wynik jest błędny i nie pojawia się żaden błąd.
Tworzenie tablic przekątnych z n elementami. Plansza n × n ma 2n-1 przekątnych w każdym kierunku.
Sprawdzanie tylko jednego kierunku przekątnych albo tylko kolumn. Hetmany atakują w obu kierunkach po przekątnych.
Zapominanie o wyłączeniu znaczników po powrocie z wywołania rekurencyjnego. Każda kolejna gałąź widzi wtedy hetmany, których nie ma już na planszy, a liczba rozwiązań maleje.
Pominięcie & full podczas obliczania free. ~x ustawia również wszystkie bity powyżej kolumny n-1, więc pętla wybiera pola poza planszą, a w Pythonie lub Ruby, gdzie liczby całkowite nie mają stałej szerokości, free staje się ujemne i pętla nigdy się nie kończy.
Traktowanie odbić lustrzanych jako tej samej planszy. Zadanie liczy je osobno: dla n = 4 są 2 plansze i są one swoimi odbiciami lustrzanymi.
Błędne uwzględnianie wyjątków dla małych plansz. Dla n = 1 jest 1 plansza, a dla n = 2 i n = 3 nie ma żadnej. Wyszukiwanie poprawnie obsługuje wszystkie trzy przypadki bez wyjątków.

Najczęstsze pytania4

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

Przeszukiwanie z nawrotami ma złożoność ograniczoną przez O(n!): pierwszy wiersz ma n możliwości, następny co najwyżej n-1 i tak dalej. Sprawdzanie przekątnych znacznie ogranicza liczbę przypadków, do 856,189 częściowych plansz dla n = 12. Nie jest znana żadna metoda wielomianowa zliczania rozwiązań, więc takie przeszukiwanie jest standardowym podejściem. Złożoność pamięciowa wynosi O(n).

Jak rozpoznać, na której przekątnej znajduje się kwadrat?

Przesunięcie o jeden krok po przekątnej / zwiększa numer wiersza o 1 i zmniejsza numer kolumny o 1, więc row + col nigdy się nie zmienia. Przesunięcie po przekątnej \ zwiększa obie wartości o 1, więc row - col nigdy się nie zmienia. Każda suma wskazuje jedną przekątną, a dodanie n-1 do różnicy zamienia ją w indeks tablicy z zakresu od 0 do 2n-2.

Jaka jest różnica między N-Queens a N-Queens II?

Problem N hetmanów wymaga znalezienia każdej planszy przedstawionej jako wiersze tekstu. Problem N hetmanów II pyta tylko o ich liczbę. W obu przypadkach wyszukiwanie opiera się na tym samym nawrotowym przeszukiwaniu, ale do zliczania nie trzeba przechowywać planszy w pamięci — wystarczą zbiory kolumn i przekątnych, dzięki czemu rozwiązanie jest szybsze i wymaga mniej pamięci. To właśnie sprawia, że wersja z maską bitową jest tu naturalnym wyborem.

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

Tak. Odbicie planszy w poziomie daje inną poprawną planszę, więc plansze, na których pierwsza hetman znajduje się w lewej połowie, odpowiadają tym, na których znajduje się w prawej połowie. Policz plansze, na których pierwszy hetman znajduje się w kolumnach od 0 do n/2 - 1, i podwój tę liczbę. Gdy n jest nieparzyste, dodaj raz plansze, na których pierwszy hetman znajduje się w środkowej kolumnie. To zmniejsza zakres wyszukiwania o połowę.

Python

def totalNQueens(n):
    # Napisz kod tutaj

Przypadki testowe

Przypadek 1

Przypadek 2

Wejście

n = 4

Oczekiwane

N-Queens II

Funkcja

Ograniczenia

Przykłady

Podpowiedzi

Rozwiązanie

Wypróbuj każde ustawienie, umieszczając po jednej hetmanie w każdym wierszu

Cofanie się z użyciem zbiorów kolumn i przekątnych

Wycofywanie z użyciem masek bitowych

Pułapki i przypadki brzegowe

Najczęstsze pytania4

Podobne zadania