N-dronninger og begrænsningsformidling
Placér N dronninger på et N×N-bræt ved hjælp af kolonne- og diagonalsæt til begrænsningskontrol i O(1), og gennemgå forskellen på at tælle og enumerere løsninger.
N-dronninger og begrænsningsformidling er en gratis DSA Interview Prep-lektion på CoddyKit. Dette er lektion 4 af 4. Du kan læse alle 3 lektioner i dette læringsspor gratis i deres fulde længde — derefter låser CoddyKit PRO alle lektioner op samt praktiske øvelser med en indbygget kodeeditor og en AI-underviser døgnet rundt. Den er en del af læringsforløbet i DSA Interview Prep, og dine fremskridt synkroniseres på tværs af nettet og CoddyKit-appen. DSA Interview Prep-kurset indeholder 4 lektioner i alt.
N-dronningeproblemet
Problemet med N-dronninger (LeetCode 51/52) beder dig placere N dronninger på et N×N-skakbræt, så ingen to dronninger angriber hinanden. Dronninger angriber langs rækker, kolonner og begge diagonaler. For N=4 findes der præcis 2 løsninger. For N=8, den klassiske version, findes der 92 løsninger. Det er det klassiske backtracking-problem med kontrol af begrænsninger, som beskærer søgerummet markant.
# 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)Placering af én dronning pr. række
Da to dronninger ikke kan dele en række, placerer vi præcis én dronning pr. række. Backtracking rekurserer række for række og vælger en kolonne for hver række. Det reducerer søgerummet fra N² valgmuligheder pr. dronning til kun N kolonner pr. række, hvilket giver N^N indledende grene — men begrænsningerne reducerer dette markant. Rekursionsdybden er N, én niveau pr. række, og forgreningsfaktoren er højst 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)-kontrol af begrænsninger med sæt
Hvis du kontrollerer gyldigheden ved at gennemgå alle placerede dronninger, tager hver kandidat O(N), så den samlede algoritme i værste fald bliver O(N² × N!). Du kan reducere hver gyldighedskontrol til O(1) ved at vedligeholde tre sæt: cols (optagne kolonner), diag (række-kolonne-værdier for diagonaler fra øverst til venstre) og anti_diag (række+kolonne-værdier for diagonaler fra øverst til højre). Dronninger på den samme diagonal har samme række-kolonne-værdi, og på den samme antidiagonal har de samme række+kolonne-værdi.
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))) # 92Forklaring af diagonalinvarianten
Indsigten om diagonaler er, at alle felter på den samme diagonal fra øverst til venstre til nederst til højre har den samme værdi af row - col. For eksempel har (0,0), (1,1) og (2,2) alle row-col=0. Alle felter på den samme antidiagonal har den samme row + col: (0,2), (1,1) og (2,0) har alle row+col=2. Det er invarianter med konstant tid, som gør det muligt at kontrollere diagonal-konflikter med opslag i et sæt på O(1) i stedet for en lineær gennemgang på O(N).
# 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 2Optælling af løsninger: N-dronninger II
N-dronninger II (LeetCode 52) beder kun om antallet, ikke om brætterne. Det gør det muligt at optimere en smule: Spring konstruktionen af brættet over, og øg blot en tæller. Hvis du bruger bitmasker i stedet for sæt, kan du yderligere gøre optællingen næsten O(1) pr. operation. Antallet af løsninger vokser ikke monotont: 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')Bitmaske til N-dronninger for højere hastighed
Ved meget store N kører en implementering med bitmasker betydeligt hurtigere. Brug tre heltal som bitmasker: cols, left_diag (flyttes til venstre for hver række) og right_diag (flyttes til højre for hver række). De tilgængelige kolonner er ((1<<n)-1) & ~(cols|left_diag|right_diag). Udtræk hver tilgængelig kolonne med bit = available & -available (den laveste satte bit), og rekursér derefter. Det giver O(1) pr. kontrol af begrænsninger ved hjælp af bitvise operationer.
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)}')Begrebet begrænsningspropagering
Begrænsningspropagering går videre end simpel beskæring: Når du har placeret en dronning, udleder og fjerner du straks alle ugyldige placeringer i fremtidige rækker. Det er mere aggressivt end at kontrollere gyldigheden af hver kandidat – du indsnævrer proaktivt søgerummet, før du forgrener. Det mest berømte eksempel er buekonsistens i SAT-løsere og Sudoku-løsere, hvor placeringen af ét ciffer fjerner muligheder i samme række, kolonne og 3×3-felt.
# 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-løser
Sudoku er det klassiske problem for begrænsningspropagering. I hver tom celle er de gyldige cifre dem, der ikke allerede findes i samme række, kolonne eller 3×3-felt. Tilbagesporingsløseren finder den første tomme celle, prøver hvert gyldigt ciffer og kalder sig selv rekursivt. Hvis den når frem til en modstrid (en tom celle uden noget gyldigt ciffer), går den tilbage. Gode Sudoku-løsere anvender også begrænsningspropagering (kandidatmarkeringer), før de bruger tilbagesporing.
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')Heuristikken for den mest begrænsede variabel
En vigtig optimering til problemer, hvor begrænsninger skal opfyldes: Vælg altid den mest begrænsede variabel som den næste (cellen med færrest gyldige valgmuligheder). I Sudoku er det tvunget at udfylde en celle med kun ét gyldigt ciffer med det samme – der er ikke brug for tilbagesporing. Hvis du vælger sådanne celler først, reducerer du søgetræets dybde markant. Dette er heuristikken Minimum resterende værdier (MRV) fra AI-baseret begrænsningsprogrammering.
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 boardTabel over antal løsninger på N-dronninger
Antallet af løsninger på N-dronninger følger denne velkendte talfølge: 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. Der kendes ingen lukket formel; antallet skal beregnes. For N=27 findes der cirka 2,34 × 10^17 løsninger. Interviewspørgsmål handler typisk om N ≤ 9. En forståelse af den eksponentielle vækst forklarer, hvorfor bitmaskeoptimeringen er vigtig for større N.
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 af brætter til N-dronninger
Når intervieweren beder dig returnere de faktiske brætter (LeetCode 51), skal du bygge hvert bræt ud fra listen queens, hvor queens[r] er dronningens kolonne i række r. Konstruktion af strenge: '.' * col + 'Q' + '.' * (n - col - 1) for hver række. Denne konstruktion i O(n²) kaldes kun ved bladene i rekursionstræet (når alle N dronninger er placeret), så den påvirker ikke den samlede kompleksitet.
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()Hurtigt tjek
Test din forståelse af begreberne fra Data Structures & Algorithms — Coding Interview Prep i denne lektion.
Opsummering af lektionen
I denne lektion lærte du: N-dronninger placerer én dronning pr. række og bruger sæt til kolonner, diagonaler (række-kolonne) og moddiagonaler (række+kolonne) for at kontrollere begrænsninger i O(1), bitmasker gør kontrollen af begrænsninger endnu hurtigere og gør det muligt at undersøge alle placeringer med næsten O(1) pr. operation, og begrænsningspropagering (MRV-heuristikken) reducerer søgningen ved altid at vælge den mest begrænsede variabel som den næste. Næste gang sammenligner vi grådige metoder med DP-metoder og lærer, hvornår du skal bruge hver af dem.
Lær Python med en AI-underviser — gratis
Skriv og kør rigtig kode i din browser, få øjeblikkelig hjælp fra en AI-underviser døgnet rundt, og fortsæt, hvor du slap, på web eller i appen.
- Kurser
- 30
- Lektioner
- 120
Ofte stillede spørgsmål
Er lektionen “N-dronninger og begrænsningsformidling” gratis?
Ja — alle 3 lektioner i læringssporet DSA Interview Prep, inklusive “N-dronninger og begrænsningsformidling”, kan læses gratis i deres fulde længde her på webstedet. Derefter låser CoddyKit PRO alle lektioner op samt interaktive øvelser med en indbygget kodeeditor og en AI-underviser døgnet rundt. DSA Interview Prep-kurset indeholder 4 lektioner i alt.
Hvad lærer jeg i “N-dronninger og begrænsningsformidling”?
Placér N dronninger på et N×N-bræt ved hjælp af kolonne- og diagonalsæt til begrænsningskontrol i O(1), og gennemgå forskellen på at tælle og enumerere løsninger. Du øver dig i DSA Interview Prep med praktisk kode, som du kører direkte i browseren, og en AI-vejleder døgnet rundt besvarer dine spørgsmål, mens du arbejder dig gennem lektionen.
Skal jeg have erfaring for at begynde på DSA Interview Prep?
Der kræves ingen tidligere erfaring. DSA Interview Prep på CoddyKit er tilrettelagt for både begyndere og øvede, så du kan starte her eller fra begyndelsen og lære i dit eget tempo. Dette er lektion 4 af 4.
Hvor lang tid tager lektionen “N-dronninger og begrænsningsformidling”?
De fleste CoddyKit-lektioner tager cirka 5–10 minutter. Hver lektion er kort og interaktiv, så du gør løbende fremskridt og kan fortsætte, hvor du slap – på både web og app.
Kan jeg skrive og køre kode i denne DSA Interview Prep-lektion?
Ja. Alle DSA Interview Prep-lektioner har en indbygget kodeeditor, så du kan skrive og køre rigtig kode direkte i din browser og få øjeblikkelig feedback fra AI – uden lokal opsætning.
Alle lektioner i dette kursus
- Backtracking-skabelon: vælg, udforsk, fortryd
- Delmængder og potensmængden
- Permutationer og kombinationer
- N-dronninger og begrænsningsformidling