N-Damen und Constraint Propagation
Platzieren Sie N Damen auf einem N×N-Brett und verwenden Sie Mengen für Spalten und Diagonalen zur Constraint-Prüfung in O(1). Erörtern Sie außerdem, wie sich Lösungen zählen und enumerieren lassen.
N-Damen und Constraint Propagation ist eine kostenlose Coding Interview Prep-Lektion auf CoddyKit. Dies ist Lektion 4 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 Coding Interview Prep-Lernpfads, und dein Fortschritt wird über Web und CoddyKit-App synchronisiert. Der Coding Interview Prep-Kurs umfasst insgesamt 4 Lektionen.
Das N-Queens-Problem
Beim N-Queens-Problem (LeetCode 51/52) sollen Sie N Damen auf einem N×N-Schachbrett so platzieren, dass keine zwei Damen einander angreifen. Damen greifen entlang von Zeilen, Spalten und beiden Diagonalen an. Für N=4 gibt es genau 2 Lösungen. Für N=8, die klassische Variante, gibt es 92 Lösungen. Dies ist das klassische Backtracking-Problem mit einer Prüfung der Bedingungen, die den Suchraum drastisch verkleinert.
# N-Queens constraints:
# 1. Exactly one queen per row
# 2. No two queens in the same column
# 3. No two queens on the same diagonal (top-left to bottom-right)
# 4. No two queens on the same anti-diagonal (top-right to bottom-left)
# For N=4, the 2 solutions:
sol1 = ['.Q..', '...Q', 'Q...', '..Q.']
sol2 = ['..Q.', 'Q...', '...Q', '.Q..']
print('N=4 solutions:')
for row in sol1: print(row)
print()
for row in sol2: print(row)Eine Dame pro Zeile platzieren
Da sich keine zwei Damen eine Zeile teilen dürfen, platzieren wir genau eine Dame pro Zeile. Das Backtracking arbeitet Zeile für Zeile und wählt für jede Zeile eine Spalte aus. Dadurch wird der Suchraum von N² Möglichkeiten pro Dame auf nur N Spalten pro Zeile reduziert, was zunächst N^N Ausgangszweige ergibt — die Bedingungen verringern diese Zahl jedoch drastisch. Die Rekursionstiefe beträgt N (eine Ebene pro Zeile), und der Verzweigungsfaktor beträgt höchstens N.
def solve_n_queens(n):
results = []
queens = [] # queens[row] = column of queen in that row
def backtrack(row):
if row == n:
# Build the board representation
board = []
for r in range(n):
board.append('.' * queens[r] + 'Q' + '.' * (n - queens[r] - 1))
results.append(board)
return
for col in range(n):
if is_valid(row, col):
queens.append(col) # CHOOSE
backtrack(row + 1) # EXPLORE
queens.pop() # UNCHOOSE
def is_valid(row, col):
for r, c in enumerate(queens):
if c == col: return False # same column
if abs(row - r) == abs(col - c): return False # diagonal
return True
backtrack(0)
return results
print(len(solve_n_queens(4)), 'solutions for N=4') # 2
print(len(solve_n_queens(8)), 'solutions for N=8') # 92O(1)-Prüfung von Bedingungen mit Mengen
Wenn die Gültigkeit durch das Durchsuchen aller bereits platzierten Damen geprüft wird, kostet jeder Kandidat O(N), wodurch der Gesamtalgorithmus im ungünstigsten Fall O(N² × N!) benötigt. Wir können jede Gültigkeitsprüfung auf O(1) reduzieren, indem wir drei Mengen verwalten: cols (besetzte Spalten), diag (Zeile-Spalte-Werte für Diagonalen von oben links nach unten rechts) und anti_diag (Zeile+Spalte-Werte für Diagonalen von oben rechts nach unten links). Damen auf derselben Diagonale haben denselben Wert für Zeile-Spalte; auf derselben Gegendiagonale haben sie denselben Wert für Zeile+Spalte.
def solve_n_queens_fast(n):
results = []
cols = set() # occupied columns
diag = set() # row - col (positive diagonal)
anti = set() # row + col (negative diagonal)
queens = []
def backtrack(row):
if row == n:
board = ['.' * c + 'Q' + '.' * (n-c-1) for c in queens]
results.append(board)
return
for col in range(n):
if col in cols or (row-col) in diag or (row+col) in anti:
continue # PRUNE: constraint violated
# CHOOSE
cols.add(col); diag.add(row-col); anti.add(row+col); queens.append(col)
backtrack(row + 1) # EXPLORE
# UNCHOOSE
cols.remove(col); diag.remove(row-col); anti.remove(row+col); queens.pop()
backtrack(0)
return results
print(len(solve_n_queens_fast(8))) # 92Die Diagonalinvariante erklärt
Die entscheidende Erkenntnis zu Diagonalen: Alle Zellen auf derselben Diagonale von oben links nach unten rechts haben denselben Wert für row - col. Beispielsweise haben (0,0), (1,1) und (2,2) alle row-col=0. Alle Zellen auf derselben Gegendiagonale haben denselben Wert für row + col: (0,2), (1,1) und (2,0) haben alle row+col=2. Diese Invarianten ermöglichen es, Konflikte auf Diagonalen mit einer O(1)-Suche in einer Menge statt mit einer linearen Suche von O(N) zu prüfen.
# Visualise the diagonal invariants for a 4x4 board
n = 4
print('row-col values (same diagonal):')
for r in range(n):
print([r-c for c in range(n)])
print('row+col values (same anti-diagonal):')
for r in range(n):
print([r+c for c in range(n)])
# Verify: (0,0) and (2,2) share diag value 0
print('(0,0) diag:', 0-0, '| (2,2) diag:', 2-2) # both 0
# Verify: (0,2) and (2,0) share anti-diag value 2
print('(0,2) anti:', 0+2, '| (2,0) anti:', 2+0) # both 2Lösungen zählen: N-Queens II
N-Queens II (LeetCode 52) verlangt nur die Anzahl der Lösungen, nicht die Bretter. Dadurch lässt sich ein kleiner Optimierungsschritt vornehmen: Überspringen Sie die Erstellung des Bretts und erhöhen Sie einfach einen Zähler. Durch die Verwendung von Bitmasken anstelle von Mengen lässt sich die Zählung pro Operation auf nahezu O(1) beschleunigen. Die Anzahl der Lösungen wächst nicht monoton: 1(N=1), 0(N=2), 0(N=3), 2(N=4), 10(N=5), 4(N=6), 40(N=7), 92(N=8).
def total_n_queens(n):
count = [0]
cols = set(); diag = set(); anti = set()
def backtrack(row):
if row == n:
count[0] += 1
return
for col in range(n):
if col in cols or (row-col) in diag or (row+col) in anti:
continue
cols.add(col); diag.add(row-col); anti.add(row+col)
backtrack(row + 1)
cols.remove(col); diag.remove(row-col); anti.remove(row+col)
backtrack(0)
return count[0]
for n in range(1, 11):
print(f'N={n}: {total_n_queens(n)} solutions')Bitmasken für schnelles N-Queens
Für sehr große N ist eine Implementierung mit Bitmasken deutlich schneller. Verwenden Sie drei Ganzzahlen als Bitmasken: cols, left_diag (wird in jeder Zeile nach links verschoben) und right_diag (wird nach rechts verschoben). Die verfügbaren Spalten sind ((1<<n)-1) & ~(cols|left_diag|right_diag). Ermitteln Sie jede verfügbare Spalte mit bit = available & -available (niedrigstes gesetztes Bit) und fahren Sie anschließend mit der Rekursion fort. Dadurch wird die Prüfung der Bedingungen mit bitweisen Operationen auf O(1) pro Schritt reduziert.
def total_n_queens_bitmask(n):
full = (1 << n) - 1 # all n columns set
count = [0]
def bt(cols, left_diag, right_diag):
if cols == full:
count[0] += 1
return
available = full & ~(cols | left_diag | right_diag)
while available:
bit = available & -available # lowest set bit
available &= available - 1 # remove lowest bit
bt(cols | bit,
(left_diag | bit) << 1,
(right_diag | bit) >> 1)
bt(0, 0, 0)
return count[0]
for n in range(1, 13):
print(f'N={n}: {total_n_queens_bitmask(n)}')Konzept der Constraint-Propagation
Constraint-Propagation geht über einfaches Pruning hinaus: Nachdem Sie eine Dame platziert haben, leiten Sie sofort alle ungültigen Positionen in den künftigen Zeilen ab und entfernen sie. Das ist aggressiver, als bei jedem Kandidaten nur die Gültigkeit zu prüfen – Sie schränken den Suchraum proaktiv ein, bevor Sie Verzweigungen erzeugen. Das bekannteste Beispiel ist Arc Consistency in SAT- und Sudoku-Solvern: Sobald Sie eine Ziffer platzieren, werden die entsprechenden Optionen in derselben Zeile, Spalte und 3×3-Box entfernt.
# Constraint propagation in Sudoku:
# After placing 5 in cell (0,0):
# - Row 0: no other cell can have 5
# - Column 0: no other cell can have 5
# - Box (0,0)-(2,2): no other cell can have 5
# This is propagated BEFORE branching further
# Simple demo: remaining valid columns after placing queens
def remaining_columns(n, queens):
cols = set(q for q in queens)
diags = set(r - q for r, q in enumerate(queens))
anti_diags = set(r + q for r, q in enumerate(queens))
row = len(queens)
return [c for c in range(n)
if c not in cols
and (row-c) not in diags
and (row+c) not in anti_diags]
print(remaining_columns(8, [0])) # valid cols for row 1 after placing col 0 in row 0Sudoku-Solver
Sudoku ist das klassische Problem für Constraint-Propagation. Für jede leere Zelle sind genau die Ziffern gültige Auswahlmöglichkeiten, die noch nicht in derselben Zeile, Spalte oder 3×3-Box vorkommen. Der Backtracking-Solver geht folgendermaßen vor: Finden Sie die erste leere Zelle, probieren Sie jede gültige Ziffer aus und rufen Sie sich rekursiv auf. Wenn ein Widerspruch erreicht wird (eine leere Zelle hat keine gültige Ziffer), gehen Sie beim Backtracking einen Schritt zurück. Gute Sudoku-Solver wenden vor dem Backtracking außerdem Constraint-Propagation (Kandidaten-Notizen) an.
def solve_sudoku(board):
def is_valid(r, c, num):
for i in range(9):
if board[r][i] == num: return False # row
if board[i][c] == num: return False # col
br, bc = (r//3)*3, (c//3)*3
for i in range(3):
for j in range(3):
if board[br+i][bc+j] == num: return False # box
return True
def backtrack():
for r in range(9):
for c in range(9):
if board[r][c] == '.':
for d in '123456789':
if is_valid(r, c, d):
board[r][c] = d
if backtrack(): return True
board[r][c] = '.'
return False # no valid digit found
return True # no empty cells: solved
backtrack()
return board
# Mini test with a solvable board (simplified)
print('Sudoku solver implemented')Heuristik der am stärksten eingeschränkten Variable
Eine wichtige Optimierung für Constraint-Satisfaction-Probleme: Wählen Sie als Nächstes immer die am stärksten eingeschränkte Variable (die Zelle mit den wenigsten gültigen Auswahlmöglichkeiten). Wenn eine Zelle im Sudoku nur eine gültige Ziffer hat, ist das sofortige Ausfüllen erzwungen – Backtracking ist nicht erforderlich. Wenn Sie solche Zellen zuerst auswählen, wird die Tiefe des Suchbaums erheblich reduziert. Dies ist die Minimum Remaining Values (MRV)-Heuristik aus der Constraint-Programmierung in der KI.
def solve_sudoku_mrv(board):
'''Find cell with fewest valid choices (MRV heuristic).'''
def valid_choices(r, c):
nums = set('123456789')
for i in range(9):
nums.discard(board[r][i])
nums.discard(board[i][c])
br, bc = (r//3)*3, (c//3)*3
for i in range(3):
for j in range(3):
nums.discard(board[br+i][bc+j])
return nums
def find_mrv():
best = (10, -1, -1, set()) # (choices_count, r, c, choices)
for r in range(9):
for c in range(9):
if board[r][c] == '.':
choices = valid_choices(r, c)
if len(choices) < best[0]:
best = (len(choices), r, c, choices)
return best[1], best[2], best[3]
def backtrack():
r, c, choices = find_mrv()
if r == -1: return True # no empty cells
for d in choices:
board[r][c] = d
if backtrack(): return True
board[r][c] = '.'
return False
backtrack()
return boardTabelle der Lösungsanzahl für N-Damen
Die Anzahl der Lösungen des N-Damen-Problems folgt dieser bekannten Folge: N=1: 1, N=2: 0, N=3: 0, N=4: 2, N=5: 10, N=6: 4, N=7: 40, N=8: 92, N=9: 352, N=10: 724. Es ist keine geschlossene Formel bekannt; die Anzahl muss berechnet werden. Für N=27 gibt es etwa 2,34 × 10^17 Lösungen. In Interviews wird typischerweise nach N ≤ 9 gefragt. Das Verständnis des exponentiellen Wachstums erklärt, warum die Optimierung mit Bitmasken für größere N wichtig ist.
def count_queens(n):
'''O(1) per constraint check using sets.'''
count = [0]
cols = set(); diag = set(); anti = set()
def bt(row):
if row == n: count[0] += 1; return
for col in range(n):
if col in cols or (row-col) in diag or (row+col) in anti: continue
cols.add(col); diag.add(row-col); anti.add(row+col)
bt(row+1)
cols.discard(col); diag.discard(row-col); anti.discard(row+col)
bt(0)
return count[0]
sequence = [count_queens(n) for n in range(1, 12)]
print('N-Queens counts:', sequence)
# [1, 0, 0, 2, 10, 4, 40, 92, 352, 724, 2680]Konstruktion des N-Damen-Bretts
Wenn die interviewende Person Sie auffordert, die tatsächlichen Bretter zurückzugeben (LeetCode 51), erstellen Sie jedes Brett aus der Liste queens, wobei queens[r] die Spalte der Dame in Zeile r angibt. String-Konstruktion: '.' * col + 'Q' + '.' * (n - col - 1) für jede Zeile. Diese O(n²)-Konstruktion wird nur an den Blättern des Rekursionsbaums aufgerufen (wenn alle N Damen platziert sind), sodass sie die Gesamtkomplexität nicht beeinflusst.
def n_queens_boards(n):
results = []
queens = []
cols = set(); diag = set(); anti = set()
def build_board():
return ['.' * c + 'Q' + '.' * (n-c-1) for c in queens]
def bt(row):
if row == n:
results.append(build_board())
return
for col in range(n):
if col in cols or (row-col) in diag or (row+col) in anti: continue
cols.add(col); diag.add(row-col); anti.add(row+col); queens.append(col)
bt(row+1)
cols.remove(col); diag.remove(row-col); anti.remove(row+col); queens.pop()
bt(0)
return results
for board in n_queens_boards(4):
for row in board: print(row)
print()Kurzer Wissenstest
Testen Sie Ihr Verständnis der Konzepte aus Data Structures & Algorithms — Coding Interview Prep aus dieser Lektion.
Zusammenfassung der Lektion
In dieser Lektion haben Sie gelernt: Beim N-Damen-Problem wird eine Dame pro Zeile platziert; für Spalten, Diagonalen (Zeile minus Spalte) und Gegendiagonalen (Zeile plus Spalte) werden Mengen verwendet, um Constraints in O(1) zu prüfen, Bitmasken beschleunigen die Constraint-Prüfungen zusätzlich und ermöglichen es, alle Platzierungen mit nahezu O(1) pro Operation zu untersuchen und Constraint-Propagation (MRV-Heuristik) reduziert die Suche, indem als Nächstes immer die am stärksten eingeschränkte Variable ausgewählt wird. Als Nächstes vergleichen wir Greedy- und DP-Ansätze und lernen, wann welcher Ansatz eingesetzt wird.
Häufig gestellte Fragen
Ist die Lektion „N-Damen und Constraint Propagation“ kostenlos?
Ja — der vollständige Text von „N-Damen und Constraint Propagation“ ist hier im Web kostenlos zu lesen. Um sie interaktiv zu üben (integrierter Code-Editor und 24/7 KI-Tutor) und den Rest des Coding Interview Prep-Kurses freizuschalten, upgrade auf CoddyKit PRO. Der Coding Interview Prep-Kurs umfasst insgesamt 4 Lektionen.
Was lerne ich in „N-Damen und Constraint Propagation“?
Platzieren Sie N Damen auf einem N×N-Brett und verwenden Sie Mengen für Spalten und Diagonalen zur Constraint-Prüfung in O(1). Erörtern Sie außerdem, wie sich Lösungen zählen und enumerieren lassen. Du übst Coding Interview Prep 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 Coding Interview Prep zu starten?
Keine Vorkenntnisse erforderlich. Coding Interview Prep 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 4 von 4.
Wie lange dauert die Lektion „N-Damen und Constraint Propagation“?
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 Coding Interview Prep-Lektion Code schreiben und ausführen?
Ja. Jede Coding Interview Prep-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
- Backtracking-Schema: Auswählen, Erkunden, Auswahl zurücknehmen
- Teilmengen und Potenzmenge
- Permutationen und Kombinationen
- N-Damen und Constraint Propagation