N-Queens II

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

Backtracking ist durch O(n!) begrenzt: In der ersten Zeile gibt es n Möglichkeiten, in der nächsten höchstens n-1 und so weiter. Die Diagonalprüfungen reduzieren die Anzahl weit unter diese Grenze, auf 856.189 unvollständige Bretter für n = 12 . Es ist keine polynomielle Methode zum Zählen der Lösungen bekannt, daher ist eine solche Suche die übliche Lösung. Der Speicherbedarf beträgt O(n) .

Q: Woran erkennst du, auf welcher Diagonale sich ein Quadrat befindet?

Ein Schritt entlang einer / -Diagonale addiert 1 zur Zeile und subtrahiert 1 von der Spalte, daher ändert sich row + col nie. Ein Schritt entlang einer \ -Diagonale addiert 1 zu beiden, daher ändert sich row - col nie. Jede Summe bezeichnet eine Diagonale, und wenn man zur Differenz n-1 addiert, erhält man einen Array-Index von 0 bis 2n-2 .

SchwerBacktracking

+10

Eine Dame auf einem Schachbrett greift jedes Feld in ihrer Reihe, in ihrer Spalte und entlang beider Diagonalen an, egal wie weit entfernt es ist. Du erhältst eine ganze Zahl n. Gib die Anzahl der Möglichkeiten zurück, n Damen auf einem n × n-Brett so zu platzieren, dass sich keine zwei Damen gegenseitig angreifen.

Zwei Möglichkeiten sind unterschiedlich, wenn auf einem Feld in der einen eine Dame steht und es in der anderen leer ist. Daher zählen ein Brett und sein Spiegelbild als zwei Möglichkeiten, auch wenn sie gleich aussehen.

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 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, lauten die beiden Bretter 1, 3, 0, 2 und 2, 0, 3, 1. Jedes ist das Spiegelbild des anderen, und sie zählen als zwei Lösungen. Jede andere Wahl platziert zwei Damen in derselben Spalte oder auf derselben Diagonale.

+10 versteckte Tests beim Einreichen

Weiterführende Frage

Kannst du nur die Bretter zählen, die nach dem Drehen und Spiegeln des Bretts unterschiedlich bleiben? Für n = 8 fallen die 92 Bretter in 12 solcher Gruppen.

Tipps

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

0 von 3 geöffnet

Lösung

Eine Platzierung wird festgelegt, indem für jede Zeile eine Spalte ausgewählt wird, da sich zwei Damen in derselben Zeile immer gegenseitig bedrohen. Das sind immer noch n^n Möglichkeiten, etwa 8.9 × 10^12 für n = 12, daher kannst du sie nicht alle auflisten. Zwei Ideen lösen das Problem. Baue das Brett Zeile für Zeile auf und verwerfe ein unvollständiges Brett sofort, sobald eine Dame bedroht wird. Dadurch sinkt die Suche für n = 12 auf weniger als eine Million unvollständige Bretter. Halte außerdem fest, welche Spalten und Diagonalen belegt sind, sodass das Prüfen eines Feldes drei Nachschläge statt einer Überprüfung aller bisher gesetzten Damen kostet.

Probiere jede Platzierung mit einer Dame pro Zeile aus

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

Idee

Jede Zeile muss genau eine Dame enthalten. Daher ist eine Platzierung eine Liste cols, wobei cols[r] die Spalte der Dame in Zeile r ist. Jeder Eintrag kann eine beliebige der n Spalten sein, also gibt es n^n Listen. Durchlaufe sie wie ein Kilometerzähler: Erhöhe den letzten Eintrag um eins. Wenn er n-1 überschreitet, setze ihn auf 0 zurück und übertrage den Übertrag auf den vorherigen Eintrag.

Vergleiche für jede Liste jedes Zeilenpaar i < j. Die beiden Damen greifen einander an, wenn sie dieselbe Spalte teilen, cols[i] == cols[j], oder sich auf einer Diagonale befinden. Auf einer Diagonale bewegt man sich beim Abwärtsgehen um eine Zeile um eine Spalte nach links oder rechts. Daher befinden sich zwei Damen genau dann auf derselben Diagonale, wenn der Spaltenabstand dem Zeilenabstand entspricht: |cols[i] - cols[j]| == j - i. Eine Liste, die jede Prüfung besteht, entspricht einem gültigen Brett. Da jede Liste überprüft wird, wird keine ausgelassen und keine doppelt gezählt.

Das Verfahren ist langsam, weil es nie vorzeitig abbricht. Zwei Damen auf derselben Diagonale in den ersten beiden Zeilen machen das Brett bereits ungültig, doch der Kilometerzähler versucht trotzdem alle n^(n-2) Möglichkeiten, die übrigen Zeilen zu füllen. Für n = 8 sind das 16,777,216 Listen, um 92 Bretter zu finden. Für n = 12 sind es etwa 8.9 × 10^12 Listen. Selbst bei einer Nanosekunde pro Liste dauert das etwa 2,5 Stunden.

Algorithmus

Beginne mit cols, das nur Nullen enthält: Jede Dame steht in Spalte 0.
Prüfe jedes Paar von Zeilen i < j: Die Liste ist ungültig, wenn cols[i] == cols[j] oder |cols[i] - cols[j]| == j - i gilt.
Wenn kein Paar sich gegenseitig bedroht, erhöhe den Zähler um 1.
Erhöhe cols wie einen Kilometerzähler: Gehe von der letzten Zeile aus nach oben und setze jeden Eintrag mit dem Wert n-1 auf 0 zurück. Erhöhe dann den ersten Eintrag, auf den das nicht zutrifft, um 1.
Wenn jeder Eintrag den Wert n-1 hatte, wurden alle n^n Listen betrachtet: Gib den Zähler zurück.

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 Diagonalensets

Idee

Platziere die Damen Reihe für Reihe von oben nach unten und prüfe jede neue Dame sofort, sobald du sie platzierst. Wird sie angegriffen, kann keine Belegung der darunterliegenden Reihen das beheben, also überspringe das Feld sofort. Ist sie sicher, fahre rekursiv mit der nächsten Reihe fort. Wenn dieser Aufruf zurückkehrt, entferne die Dame und probiere die nächste Spalte aus. Ein Aufruf, der Reihe n erreicht, hat n sichere Damen platziert und zählt ein Brett. Das ist Backtracking, und es schneidet den Suchraum stark ab: Für n = 12 besucht es 856,189 partielle Bretter statt 8.9 × 10^12 vollständiger Bretter.

Die andere Hälfte besteht darin, ein Feld schnell zu prüfen. Die Reihen darunter sind leer, und in der Reihe der neuen Dame steht keine andere Dame, also können nur drei Linien das Feld (row, c) angreifen: seine Spalte, seine /-Diagonale und seine \-Diagonale. Jedes Feld auf derselben /-Diagonale hat denselben Wert für row + c, von 0 bis 2n-2. Jedes Feld auf derselben \-Diagonale hat denselben Wert für row - c, von -(n-1) bis n-1. Addiere also n-1, um einen Index von 0 bis 2n-2 zu erhalten. Verwende drei Flag-Arrays: cols mit der Größe n sowie diag und anti mit der Größe 2n-1. Das Feld ist genau dann sicher, wenn alle drei Flags ausgeschaltet sind: drei Zugriffe, O(1). Ein Vergleich mit jeder bisher platzierten Dame würde dagegen O(n) kosten.

Eine Linie kann höchstens eine Dame enthalten. Wenn du eine Dame platzierst, schaltest du ihre drei Flags ein; wenn du sie entfernst, schaltest du sie wieder aus, sodass die Arrays genau ihren vorherigen Zustand haben. Auf dem 4-mal-4-Brett setzt eine Dame auf (0, 0) die Flags cols[0], diag[0] und anti[3]. In Reihe 1 liegt Spalte 1 auf anti[3] und wird daher übersprungen, ohne die Dame selbst zu prüfen.

Die erste Reihe bietet n Spalten, die zweite höchstens n-1 und so weiter. Daher ist die Suche durch O(n!) begrenzt, und die Diagonalen reduzieren sie deutlich weiter. Für n = 12 prüfen die Schleifen insgesamt 10,103,868 Felder. Die Rekursion ist n Aufrufe tief, und die Arrays enthalten etwa 5n Flags. Der Speicherbedarf beträgt also O(n).

Algorithmus

Erstelle drei Flag-Arrays, die alle ausgeschaltet sind: cols mit n Einträgen sowie diag und anti mit jeweils 2n-1 Einträgen.
Schreibe place(row). Wenn row == n gilt, gib 1 zurück: Jede Zeile enthält eine sichere Dame.
Andernfalls überspringe jede Spalte c, wenn cols[c], diag[row + c] oder anti[row - c + n - 1] eingeschaltet ist.
Schalte bei einer sicheren Spalte die drei Flags ein, addiere place(row + 1) zur Gesamtsumme und schalte sie dann wieder aus.
Gib die Gesamtsumme 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

Die Suche mit Mengen ist schnell, aber in jeder Zeile prüft sie weiterhin alle n Spalten, von denen die meisten angegriffen sind. Mit einer Bitmaske kannst du direkt zu den freien Feldern springen. Das Bit c einer Ganzzahl steht für Spalte c der Zeile, die du gerade füllen willst. Verwende drei Masken: cols für die bereits belegten Spalten, left für die Felder dieser Zeile, die von einer Diagonalrichtung angegriffen werden, und right für die Felder, die von der anderen angegriffen werden.

Die freien Felder ergeben sich dann mit einem einzigen Ausdruck: free = ~(cols | left | right) & full, wobei bei full die niedrigsten n Bits gesetzt sind. free & -free isoliert das niedrigste freie Feld; durch Subtrahieren geht es zum nächsten weiter. Wenn du eine Dame auf bit setzt und eine Zeile nach unten gehst, bleibt ihre Spalte belegt, während jeder diagonale Angriff um eine Spalte weiterrückt. Die nächste Zeile erhält also cols | bit, ((left | bit) << 1) & full und (right | bit) >> 1. Es gibt nichts rückgängig zu machen: Jeder Aufruf erhält seine eigenen drei Ganzzahlen. Wenn cols == full gilt, sind alle n Damen gesetzt.

Nimm n = 4 und eine erste Dame in Spalte 1, bit = 0010, wobei Spalte 0 als rechtestes Bit geschrieben wird. Zeile 1 erhält cols = 0010, left = 0100 und right = 0001, also ist free = 1000: Spalte 3 ist die einzige Möglichkeit und wird gefunden, ohne die Spalten 0, 1 oder 2 zu prüfen.

Die Suche besucht dieselben unvollständigen Bretter wie die Version mit Mengen, aber jeder Schleifendurchlauf setzt nun eine Dame. Für n = 12 sind das 856,188 Schritte statt 10,103,868 Feldprüfungen, wobei jeder Schritt nur einige Ganzzahloperationen umfasst. Die Laufzeit ist weiterhin durch O(n!) beschränkt, und die Rekursion ist n Aufrufe tief. Der R-Code führt dieselben Masken ohne Rekursion aus: Er hält alle unvollständigen Bretter einer Zeile in einem Vektor und erweitert sie alle zeilenweise, sodass er eine ganze Ebene von Brettern im Speicher hält statt n Aufrufen.

Algorithmus

Setze full = (1 << n) - 1, die Maske aller n Spalten.
Schreibe 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

Die Suche selbst ist kurz. Die meisten Fehler stecken in der Diagonalberechnung und beim Zurücksetzen.

row - c als Index verwenden, ohne n-1 zu addieren. In Java führt das zu einem Fehler, in C wird Speicher außerhalb des Arrays gelesen, und in Python liest anti[-2] stillschweigend das Flag einer anderen Diagonale, sodass die Anzahl ohne Fehlermeldung falsch ist.
Die Diagonalarrays mit n Einträgen dimensionieren. Ein n × n-Brett hat in jeder Richtung 2n-1 Diagonalen.
Nur eine Diagonalrichtung oder nur die Spalten prüfen. Beide Diagonalrichtungen greifen an.
Vergessen, die Flags auszuschalten, nachdem der rekursive Aufruf zurückgekehrt ist. Jeder spätere Zweig sieht dann Damen, die nicht mehr auf dem Brett stehen, und die Anzahl sinkt.
& full beim Berechnen von free weglassen. ~x setzt auch jedes Bit oberhalb der Spalte n-1, sodass die Schleife Felder außerhalb des Bretts auswählt. In Python oder Ruby, deren Ganzzahlen keine feste Breite haben, wird free negativ und die Schleife endet nie.
Spiegelbilder als dasselbe Brett behandeln. Das Problem zählt sie getrennt: n = 4 hat 2 Bretter, und sie sind Spiegelbilder voneinander.
Kleine Bretter falsch als Sonderfälle behandeln. n = 1 hat 1 Brett, während n = 2 und n = 3 keines haben. Die Suche liefert für alle drei die richtige Anzahl, ganz ohne Sonderfall.

Häufige Fragen4

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

Backtracking ist durch O(n!) begrenzt: In der ersten Zeile gibt es n Möglichkeiten, in der nächsten höchstens n-1 und so weiter. Die Diagonalprüfungen reduzieren die Anzahl weit unter diese Grenze, auf 856.189 unvollständige Bretter für n = 12. Es ist keine polynomielle Methode zum Zählen der Lösungen bekannt, daher ist eine solche Suche die übliche Lösung. Der Speicherbedarf beträgt O(n).

Woran erkennst du, auf welcher Diagonale sich ein Quadrat befindet?

Ein Schritt entlang einer /-Diagonale addiert 1 zur Zeile und subtrahiert 1 von der Spalte, daher ändert sich row + col nie. Ein Schritt entlang einer \-Diagonale addiert 1 zu beiden, daher ändert sich row - col nie. Jede Summe bezeichnet eine Diagonale, und wenn man zur Differenz n-1 addiert, erhält man einen Array-Index von 0 bis 2n-2.

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

N-Queens fragt nach jedem Brett, dargestellt als Textzeilen. N-Queens II fragt nur, wie viele es gibt. Die Suche verwendet dieselbe Backtracking-Methode, aber zum Zählen muss kein Brett im Speicher gehalten werden, sondern nur die Mengen der Spalten und Diagonalen. Dadurch ist sie schneller und benötigt weniger Speicher. Deshalb bietet sich hier auch die Bitmasken-Version an.

Kannst du Symmetrie nutzen, um N-Queens II schneller zu lösen?

Ja. Das Spiegeln eines Bretts von links nach rechts ergibt ein weiteres gültiges Brett. Daher entspricht die Anzahl der Bretter, bei denen die erste Dame in der linken Hälfte steht, der Anzahl der Bretter, bei denen sie in der rechten Hälfte steht. Zähle die Bretter, bei denen die erste Dame in den Spalten 0 bis n/2 - 1 steht, und verdopple diese Anzahl. Wenn n ungerade ist, addiere einmal die Bretter, bei denen die erste Dame in der mittleren Spalte steht. Dadurch halbiert sich der Suchaufwand.

Python

def totalNQueens(n):
    # Schreibe hier den Code

Testfälle

Fall 1

Fall 2

Eingabe

n = 4

Erwartet

N-Queens II

Funktion

Einschränkungen

Beispiele

Tipps

Lösung

Probiere jede Platzierung mit einer Dame pro Zeile aus

Backtracking mit Spalten- und Diagonalensets

Backtracking mit Bitmasken

Stolperfallen und Grenzfälle

Häufige Fragen4

Ähnliche Aufgaben