Permutationen und die N-Queens-Idee
Platzieren Sie Elemente und gehen Sie bei Konflikten zurück
Permutationen und die N-Queens-Idee ist eine kostenlose Competitive Programming Academy-Lektion auf CoddyKit. Dies ist Lektion 3 von 4. Du kannst die komplette Lektion unten kostenlos lesen – dann übst du sie direkt im Browser mit einem integrierten Code-Editor und einem KI-Tutor rund um die Uhr. Sie ist Teil des Competitive Programming Academy-Lernpfads, und dein Fortschritt wird über Web und CoddyKit-App synchronisiert. Der Competitive Programming Academy-Kurs umfasst insgesamt 4 Lektionen.
Von Teilmengen zu Anordnungen
Eine Permutation ist eine Anordnung aller Elemente in einer bestimmten Reihenfolge. Das Erzeugen von Permutationen ist nach Teilmengen die nächste Backtracking-Fähigkeit.
Wie viele Permutationen gibt es
Es gibt n Fakultät Permutationen von n Elementen, weil der erste Platz n Möglichkeiten hat, der nächste n minus eins und so weiter. Die Anzahl wächst schnell.
Ein Element nach dem anderen platzieren
Die Rekursion füllt die Positionen von links nach rechts. Bei jedem Schritt wählen Sie ein ungenutztes Element aus, platzieren es und wenden die Rekursion auf den Rest an.
Verfolgen, was bereits verwendet wird
Ein boolesches used-Array markiert, welche Elemente bereits platziert wurden, sodass jedes Element in jeder Permutation genau einmal vorkommt.
Permutationen im Code
Dieses Backtracking platziert einen ungenutzten Wert, führt die Rekursion aus und gibt ihn anschließend für den nächsten Zweig wieder frei.
def perm(cur):
if len(cur) == n:
out.append(cur[:]); return
for x in a:
if x not in cur:
perm(cur + [x])Verwenden Sie itertools, wenn es erlaubt ist
Für schnelle Wettbewerbsaufgaben liefert Python's itertools.permutations jede Anordnung, ohne dass Sie die Rekursion selbst schreiben müssen.
from itertools import permutations
for p in permutations(a):
print(p)Das N-Queens-Problem
Bei N-Queens sollen Sie n Damen auf einem n mal n großen Brett platzieren, sodass keine Dame eine andere angreift. Es ist das klassische Backtracking-Rätsel. 👑
Eine Dame pro Zeile
Da sich keine zwei Damen dieselbe Zeile teilen, platzieren Sie genau eine Dame pro Zeile und wählen nur ihre Spalte aus. Dadurch wird der Suchraum erheblich kleiner.
Die drei Konfliktarten prüfen
Lehnen Sie vor dem Platzieren jede bereits belegte Spalte oder Diagonale ab. Verfolgen Sie belegte Spalten und beide Diagonalrichtungen in Mengen.
if c in cols or r-c in d1 or r+c in d2:
continueAn einer Sackgasse zurückgehen
Wenn in einer Zeile keine Spalte funktioniert, scheitert der Zweig. Sie gehen per Backtracking zurück, entfernen die letzte Dame und probieren ihre nächste Möglichkeit.
Das gemeinsame Muster
Permutationen und N-Queens haben dieselbe Struktur: auswählen, rekursiv aufrufen, rückgängig machen. Sobald Sie das erkennen, lassen sich die meisten Platzierungsrätsel mit derselben Vorlage lösen.
Kurze Überprüfung
Warum wird bei N-Queens nur eine Dame pro Zeile platziert?
Zusammenfassung: Auswählen, rekursiv aufrufen, rückgängig machen
Sie haben Permutationen erzeugt, indem Sie ungenutzte Elemente platziert haben, und gelernt, dass N-Queens dasselbe Muster aus Auswählen, rekursivem Aufruf und Rückgängigmachen mit Konfliktprüfungen verwendet. 🎯
Häufig gestellte Fragen
Ist die Lektion „Permutationen und die N-Queens-Idee“ kostenlos?
Ja — der vollständige Text von „Permutationen und die N-Queens-Idee“ ist hier im Web kostenlos zu lesen. Um sie interaktiv zu üben (integrierter Code-Editor und 24/7 KI-Tutor) und den Rest des Competitive Programming Academy-Kurses freizuschalten, upgrade auf CoddyKit PRO. Der Competitive Programming Academy-Kurs umfasst insgesamt 4 Lektionen.
Was lerne ich in „Permutationen und die N-Queens-Idee“?
Platzieren Sie Elemente und gehen Sie bei Konflikten zurück Du übst Competitive Programming Academy mit praktischem Code, den du direkt im Browser ausführst, und ein 24/7 KI-Tutor beantwortet deine Fragen während du die Lektion bearbeitest.
Brauche ich Erfahrung, um Competitive Programming Academy zu starten?
Keine Vorkenntnisse erforderlich. Competitive Programming Academy auf CoddyKit ist für Anfänger bis fortgeschrittene Lernende strukturiert, sodass du hier starten oder von Anfang an beginnen und in deinem eigenen Tempo voranschreiten kannst. Dies ist Lektion 3 von 4.
Wie lange dauert die Lektion „Permutationen und die N-Queens-Idee“?
Die meisten CoddyKit-Lektionen dauern etwa 5–10 Minuten. Jede ist kompakt und interaktiv, sodass du stetig Fortschritte machst und genau dort weitermachst, wo du aufgehört hast – im Web und in der App.
Kann ich in dieser Competitive Programming Academy-Lektion Code schreiben und ausführen?
Ja. Jede Competitive Programming Academy-Lektion enthält einen integrierten Code-Editor, sodass du echten Code direkt in deinem Browser schreibst und ausführst und sofort KI-Feedback erhältst — ohne lokale Einrichtung erforderlich.
Alle Lektionen in diesem Kurs
- Rekursiv denken: Basisfall und Rekursion
- Alle Teilmengen erzeugen
- Permutationen und die N-Queens-Idee
- Mit Beschneiden das Zeitlimit einhalten