N-Queens II

Q: Wie hoch ist die Zeitkomplexität von N-Queens II?

Backtracking ist durch O(n!) beschränkt: In der ersten Zeile gibt es n Möglichkeiten, in der nächsten höchstens n-1 und so weiter. Durch das Beschneiden sinkt der tatsächliche Aufwand deutlich auf 856,189 unvollständige Bretter für n = 12 . Der Speicherbedarf beträgt O(n) .

SchwerBacktracking

+10

Eine Dame greift jedes Feld in ihrer Zeile, ihrer Spalte und auf beiden Diagonalen an, egal wie weit entfernt. Gib bei einer ganzen Zahl n die Anzahl der Möglichkeiten zurück, n Damen auf einem n × n-Brett so zu platzieren, dass sich keine zwei Damen gegenseitig angreifen.

Bretter, die sich in irgendeinem Feld unterscheiden, werden getrennt gezählt, einschließlich Spiegelbildern.

Funktion

totalNQueens(n: integer) → integer

ninteger: die Größe des Bretts und die Anzahl der Damen
Gibt zurückinteger: die Anzahl der Möglichkeiten, die Damen so zu platzieren, dass keine Dame eine andere angreift

Einschränkungen

1 ≤ n ≤ 12
Die Antwort für n = 12 ist 14.200, also passt sie in eine 32-Bit-Ganzzahl.

Beispiele

Eingabe: n = 4
Ausgabe: 2
Erklärung: Schreibt man die Spalte der Dame jeder Zeile von oben nach unten auf, erhält man die Bretter 1, 3, 0, 2 und 2, 0, 3, 1: Spiegelbilder, die als zwei gezählt werden. Bei jeder anderen Wahl stehen zwei Damen in derselben Spalte oder auf derselben Diagonale.

Weiterführende Frage

Kannst du nur die Bretter zählen, die nach Drehungen und Spiegelungen des Bretts noch verschieden sind? Für n = 8 lassen sich die 92 Bretter in 12 solcher Gruppen einteilen.

Tipps

Öffne sie nacheinander. Jeder verrät ein bisschen mehr.

0 von 3 geöffnet

Lösung

Zwei Damen in derselben Zeile greifen sich immer an, daher wird ein Brett durch eine Spalte pro Zeile dargestellt: n^n Listen, bei n = 12 etwa 8.9 × 10^12. Baue das Brett stattdessen zeilenweise auf, verwerfe ein unvollständiges Brett, sobald eine Dame angegriffen wird, und markiere die belegten Spalten und Diagonalen, sodass die Prüfung eines Feldes drei Nachschlagevorgänge kostet.

Probiere jede Platzierung mit einer Dame pro Zeile aus

Korrekt, wird aber bei den größten Tests nicht fertig

Idee

Schreibe eine Platzierung als Liste cols, die Spalte der Dame jeder Zeile, und gehe wie bei einem Kilometerzähler alle n^n Listen durch. Damen in den Zeilen i < j greifen sich an, wenn cols[i] == cols[j] oder |cols[i] - cols[j]| == j - i, da eine Diagonale sich pro Zeile um eine Spalte verschiebt. Jede Liste wird genau einmal geprüft, sodass kein Brett ausgelassen oder doppelt gezählt wird.

Nichts bricht vorzeitig ab: Ein Konflikt in den ersten beiden Zeilen lässt immer noch n^(n-2) Listen übrig. Für n = 8 sind das 16,777,216 Listen für 92 Bretter; für n = 12 sind es 8.9 × 10^12, also etwa 2.5 Stunden bei einer Nanosekunde pro Liste.

Algorithmus

Beginne mit cols, die alle den Wert 0 haben.
Erhöhe den Zähler um 1, wenn kein Zeilenpaar i < j die Bedingung cols[i] == cols[j] oder |cols[i] - cols[j]| == j - i erfüllt.
Gehe wie bei einem Kilometerzähler vor: Setze von der letzten Zeile aus jeden Eintrag mit dem Wert n-1 auf 0 zurück und erhöhe dann den ersten Eintrag unter n-1 um 1.
Beende den Vorgang und gib den Zähler zurück, wenn jeder Eintrag den Wert n-1 hatte.

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

Backtracking mit Spalten- und Diagonalensätzen

Idee

Platziere die Damen Zeile für Zeile und überprüfe jede, sobald du sie platzierst. Das Füllen der darunterliegenden Zeilen kann eine angegriffene Dame nicht retten, also überspringe dieses Feld. Eine sichere Dame führt rekursiv zur nächsten Zeile und wird entfernt, wenn der Aufruf zurückkehrt; das Erreichen der Zeile n zählt ein Brett.

Nur drei Linien können das Feld (row, c) angreifen: seine Spalte, seine /-Diagonale, auf der row + c konstant ist, und seine \-Diagonale, auf der row - c konstant ist (addiere n-1, um sie ab 0 zu indizieren). Markierungsarrays cols, diag und anti machen aus der Sicherheitsprüfung drei Nachschlagevorgänge. Jede Linie enthält höchstens eine Dame, daher stellt das Zurücksetzen der Markierungen bei der Rückkehr die Arrays exakt wieder her.

Zeile k bietet höchstens n - k Spalten, daher ist die Suche durch O(n!) begrenzt und benötigt O(n) Speicherplatz.

Algorithmus

Erstelle Flag-Arrays cols der Größe n und diag und anti der Größe 2n-1, alle auf aus.
place(row): Wenn row == n, gib 1 zurück.
Überspringe jede Spalte c, wenn cols[c], diag[row + c] oder anti[row - c + n - 1] eingeschaltet ist.
Schalte andernfalls die drei Flags ein, addiere place(row + 1) zur Summe und schalte sie wieder aus.
Gib die Summe zurück. Die Antwort ist 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 mit Bitmasken

Idee

Bei der Suche mit Flags werden weiterhin alle n Spalten jeder Zeile geprüft; Bitmasken springen direkt zu den freien. Bit c ist die Spalte c der gerade gefüllten Zeile: cols enthält die belegten Spalten und left und right die Felder, die entlang der jeweiligen Diagonale angegriffen werden. Dann gilt free = ~(cols | left | right) & full, wobei full die unteren n Bits enthält, und free & -free ist das am weitesten rechts liegende freie Feld. Eine Zeile tiefer bleibt eine Spalte belegt, und jeder diagonale Angriff verschiebt sich um eine Spalte.

Bei n = 4 und einer ersten Dame auf bit = 0010 ergibt sich für Zeile 1 free = 1000: Spalte 3, gefunden, ohne die anderen zu prüfen. Bei n = 12 ersetzen 856,188 Schleifendurchläufe 10,103,868 Feldprüfungen. Der R-Code erweitert auf einmal eine ganze Zeile partieller Bretter, statt rekursiv aufzurufen.

Algorithmus

Setze full = (1 << n) - 1.
count(cols, left, right): Wenn cols == full, gib 1 zurück.
Berechne free = ~(cols | left | right) & full.
Solange free nicht 0 ist, nimm bit = free & -free, entferne es aus free und addiere count(cols | bit, ((left | bit) << 1) & full, (right | bit) >> 1) zur Summe.
Gib die Summe zurück. Die Antwort ist 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)

Stolperfallen und Grenzfälle

Indizierung von anti mit row - c, ohne n-1 hinzuzufügen. Java wirft eine Ausnahme, C liest außerhalb des Arrays, und Pythons anti[-2] liest unbemerkt das Flag einer anderen Diagonale.
Die Diagonal-Arrays auf n statt auf 2n-1 dimensionieren. row + c erreicht 2n-2.
Die Flags nach dem rekursiven Aufruf nicht zurücksetzen. Spätere Zweige sehen Damen, die nicht mehr da sind, und die Anzahl sinkt.
& full bei free weglassen. ~x setzt die Bits oberhalb von Spalte n-1, sodass die Schleife Felder außerhalb des Bretts auswählt; in Python oder Ruby wird free negativ und die Schleife endet nie.

Häufige Fragen3

Wie hoch ist die Zeitkomplexität von N-Queens II?

Backtracking ist durch O(n!) beschränkt: In der ersten Zeile gibt es n Möglichkeiten, in der nächsten höchstens n-1 und so weiter. Durch das Beschneiden sinkt der tatsächliche Aufwand deutlich auf 856,189 unvollständige Bretter für n = 12. Der Speicherbedarf beträgt O(n).

Was ist der Unterschied zwischen N-Queens und N-Queens II?

N-Queens gibt jedes Brett als Textzeilen aus; N-Queens II gibt nur zurück, wie viele es gibt. Die Suche ist dieselbe, aber beim Zählen werden keine Bretter gespeichert, was zur Bitmasken-Version passt.

Kannst du Symmetrie nutzen, um N-Queens II zu beschleunigen?

Durch Spiegelung eines Bretts von links nach rechts erhält man ein weiteres gültiges Brett. Zähle daher die Bretter, bei denen die erste Dame in den Spalten 0 bis n/2 - 1 steht, und verdopple diese Anzahl. Bei ungeradem n addiere einmal die Bretter, bei denen die erste Dame in der mittleren Spalte steht.

def totalNQueens(n):
    # Schreibe hier den Code

Test #1

Test #2

Argument

n = 4

Erwartete Ausgabe

N-Queens II

Funktion

Einschränkungen

Beispiele

Tipps

Lösung

Probiere jede Platzierung mit einer Dame pro Zeile aus

Backtracking mit Spalten- und Diagonalensätzen

Backtracking mit Bitmasken

Stolperfallen und Grenzfälle

Häufige Fragen3

Ähnliche Aufgaben