N-drottningar och constraint propagation
Placera N drottningar på ett N×N-bräde med hjälp av mängder för kolumner och diagonaler, vilket ger O(1)-kontroll av begränsningar, och diskutera hur lösningar kan räknas respektive enumereras.
N-drottningar och constraint propagation är en gratis lektion i Förberedelse inför kodningsintervjuer på CoddyKit. Detta är lektion 4 av 4. Ni kan läsa hela lektionen gratis nedan och sedan öva praktiskt i webbläsaren med en inbyggd kodredigerare och en AI-handledare som är tillgänglig dygnet runt. Den ingår i lärvägen för Förberedelse inför kodningsintervjuer, och Era framsteg synkroniseras mellan webben och CoddyKit-appen. Kursen i Förberedelse inför kodningsintervjuer innehåller totalt 4 lektioner.
N-damproblemet
Problemet med N-Queens (LeetCode 51/52) går ut på att placera N damer på ett N×N-schackbräde så att inga två damer kan angripa varandra. Damer angriper längs rader, kolumner och båda diagonalerna. För N=4 finns exakt 2 lösningar. För N=8, den klassiska versionen, finns 92 lösningar. Detta är det klassiska backtrackingproblemet där kontroll av begränsningar beskär sökrymden kraftigt.
# 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)Placera en dam per rad
Eftersom inga två damer kan dela en rad placerar vi exakt en dam per rad. Backtracking går rekursivt rad för rad och väljer en kolumn för varje rad. Detta minskar sökrymden från N² val per dam till endast N kolumner per rad, vilket ger N^N startgrenar — men begränsningarna minskar detta antal kraftigt. Rekursionsdjupet är N, alltså en nivå per rad, och förgreningsfaktorn är högst 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)-kontroll av begränsningar med mängder
Att kontrollera giltighet genom att gå igenom alla placerade damer är O(N) per kandidat, vilket ger O(N² × N!) totalt i värsta fall. Vi kan minska varje giltighetskontroll till O(1) genom att upprätthålla tre mängder: cols (upptagna kolumner), diag (row-col-värden för diagonaler från övre vänster) och anti_diag (row+col-värden för diagonaler från övre höger). Damer på samma diagonal har samma row-col; på samma antidiagonal har de samma row+col.
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))) # 92Förklaring av diagonalinvarianten
Diagonalinsikten är följande: alla rutor på samma diagonal från övre vänster till nedre höger har samma värde för row - col. Till exempel har (0,0), (1,1) och (2,2) alla row-col=0. Alla rutor på samma antidiagonal har samma row + col: (0,2), (1,1) och (2,0) har alla row+col=2. Dessa invariansvillkor, som kan kontrolleras på konstant tid, gör att vi kan kontrollera diagonalkonflikter med en mängduppslagning i O(1) i stället för en linjär genomsökning i 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 2Räkna lösningar: N-Queens II
N-Queens II (LeetCode 52) frågar bara efter antalet, inte efter brädena. Det gör en mindre optimering möjlig: hoppa över steget att bygga brädet och öka bara en räknare. Genom att använda bitmasker i stället för mängder kan räkningen dessutom snabbas upp till nästan O(1) per operation. Antalet lösningar växer inte 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')N-Queens med bitmasker för högre hastighet
För mycket stora N körs en bitmaskimplementation betydligt snabbare. Använd tre heltal som bitmasker: cols, left_diag (skiftas åt vänster för varje rad) och right_diag (skiftas åt höger för varje rad). Tillgängliga kolumner är ((1<<n)-1) & ~(cols|left_diag|right_diag). Plocka ut varje tillgänglig kolumn med bit = available & -available (den lägsta satta biten) och fortsätt sedan rekursivt. Detta ger O(1) per begränsningskontroll med bitvisa 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)}')Konceptet constraint propagation
Constraint propagation går längre än enkel beskärning: efter att en dam placerats drar man omedelbart slutsatser om och eliminerar alla ogiltiga positioner i kommande rader. Detta är mer aggressivt än att kontrollera giltigheten för varje kandidat – sökutrymmet begränsas proaktivt innan förgrening. Det mest kända exemplet är Arc Consistency i SAT-lösare och Sudokolösare, där placeringen av en siffra eliminerar alternativ i samma rad, kolumn och 3×3-ruta.
# 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 0Sudokolösare
Sudoku är det klassiska problemet för constraint propagation. I varje tom cell är de giltiga sifferalternativen de som ännu inte finns i samma rad, kolumn eller 3×3-ruta. Backtracking-lösaren hittar den första tomma cellen, provar varje giltig siffra och anropar sig själv rekursivt. Om en motsägelse uppstår (en tom cell utan giltig siffra) går lösaren tillbaka. Bra Sudokolösare använder också constraint propagation (kandidatmarkeringar) före backtracking.
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')Heuristiken för den mest begränsade variabeln
En viktig optimering för constraint satisfaction-problem: välj alltid den mest begränsade variabeln (cellen med minst antal giltiga alternativ) härnäst. I Sudoku innebär en cell med bara 1 giltig siffra att den måste fyllas i direkt – ingen backtracking behövs. Genom att välja sådana celler först minskar sökträdets djup dramatiskt. Detta är heuristiken Minimum Remaining Values (MRV) inom AI-baserad constraint programming.
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 boardTabell över antal lösningar för N-Queens
Antalet lösningar för N-queens följer denna välkända talföljd: 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. Ingen sluten formel är känd; antalet måste beräknas. För N=27 finns cirka 2.34 × 10^17 lösningar. Intervjufrågor gäller vanligtvis N ≤ 9. Förståelsen av den exponentiella tillväxten visar varför bitmaskoptimeringen är viktig för 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 av N-Queens-bräden
När intervjuaren ber er returnera de faktiska brädena (LeetCode 51) bygger ni varje bräde utifrån listan queens, där queens[r] är kolumnen för damen på rad r. Strängkonstruktion: '.' * col + 'Q' + '.' * (n - col - 1) för varje rad. Denna konstruktion i O(n²) anropas endast vid löv i rekursionsträdet (när alla N damer har placerats), så den påverkar inte den totala komplexiteten.
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()Snabbtest
Testa era kunskaper om koncepten i Data Structures & Algorithms — Coding Interview Prep från den här lektionen.
Lektionssammanfattning
I den här lektionen har ni lärt er: N-Queens placerar en dam per rad och använder mängder för kolumner, diagonaler (rad-kolumn) och antidiagonaler (rad+kolumn) för kontroll av begränsningar i O(1), bitmasker snabbar upp kontrollen av begränsningar ytterligare och gör det möjligt att utforska alla placeringar med nästan O(1) per operation, och constraint propagation (MRV-heuristiken) minskar sökningen genom att alltid välja den mest begränsade variabeln härnäst. Härnäst jämför vi Greedy- och DP-metoder och lär oss när de ska användas.
Lär dig Förberedelse inför kodningsintervjuer med en AI-lärare – gratis
Skriv och kör riktig kod i webbläsaren, få omedelbar hjälp av en AI-lärare dygnet runt och fortsätt där du slutade – på webben eller i appen.
- Kurser
- 90
- Lektioner
- 360
Vanliga frågor
Är lektionen ”N-drottningar och constraint propagation” gratis?
Ja – hela texten till ”N-drottningar och constraint propagation” kan läsas gratis här på webben. Om Ni vill öva interaktivt med en inbyggd kodredigerare och en AI-handledare som är tillgänglig dygnet runt och låsa upp resten av kursen i Förberedelse inför kodningsintervjuer, kan Ni uppgradera till CoddyKit PRO. Kursen i Förberedelse inför kodningsintervjuer innehåller totalt 4 lektioner.
Vad lär jag mig i ”N-drottningar och constraint propagation”?
Placera N drottningar på ett N×N-bräde med hjälp av mängder för kolumner och diagonaler, vilket ger O(1)-kontroll av begränsningar, och diskutera hur lösningar kan räknas respektive enumereras. Ni övar på Förberedelse inför kodningsintervjuer med praktisk kod som körs direkt i webbläsaren, medan en AI-handledare som är tillgänglig dygnet runt svarar på Era frågor under lektionen.
Behöver jag någon erfarenhet för att börja lära mig Förberedelse inför kodningsintervjuer?
Du behöver inga förkunskaper. Utbildningen i Förberedelse inför kodningsintervjuer på CoddyKit är upplagd för allt från nybörjare till avancerade elever, så att du kan börja här eller från början och gå fram i din egen takt. Detta är lektion 4 av 4.
Hur lång tid tar lektionen ”N-drottningar och constraint propagation”?
De flesta CoddyKit-lektioner tar cirka 5–10 minuter. Varje lektion är kort och interaktiv, så att du gör stadiga framsteg och kan fortsätta precis där du slutade – på webben eller i appen.
Kan jag skriva och köra kod i den här Förberedelse inför kodningsintervjuer-lektionen?
Ja. Varje Förberedelse inför kodningsintervjuer-lektion innehåller en inbyggd kodredigerare, så att du kan skriva och köra riktig kod direkt i webbläsaren och få omedelbar AI-feedback – utan lokal installation.
Alla lektioner i den här kursen
- Backtracking-mall: välj, utforska, välj bort
- Delmängder och potensmängd
- Permutationer och kombinationer
- N-drottningar och constraint propagation