N-regine e propagazione dei vincoli
Posizioni N regine su una scacchiera N×N usando insiemi per colonne e diagonali, così da verificare i vincoli in O(1), e analizzi la differenza tra contare ed enumerare le soluzioni.
N-regine e propagazione dei vincoli è una lezione DSA Interview Prep gratuita su CoddyKit. Questa è la lezione 4 di 4. Puoi leggere la lezione completa qui gratuitamente — poi esercitati direttamente nel browser con un editor di codice integrato e un tutor IA disponibile 24/7. Fa parte del percorso di apprendimento DSA Interview Prep, e i tuoi progressi si sincronizzano tra il web e l'app CoddyKit. Il corso DSA Interview Prep include 4 lezioni in totale.
Il problema delle N regine
Il problema delle N-Queens (LeetCode 51/52) chiede di posizionare N regine su una scacchiera N×N in modo che nessuna coppia di regine possa attaccare l'altra. Le regine attaccano lungo le righe, le colonne e entrambe le diagonali. Per N=4 esistono esattamente 2 soluzioni. Per N=8, la versione classica, esistono 92 soluzioni. Questo è il problema canonico del backtracking con verifica dei vincoli, che riduce drasticamente lo spazio di ricerca.
# 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)Posizionare una regina per riga
Poiché due regine non possono condividere la stessa riga, si posiziona esattamente una regina per riga. Il backtracking procede ricorsivamente riga per riga, scegliendo una colonna per ogni riga. Questo riduce lo spazio di ricerca da N² possibilità per regina a sole N colonne per riga, con N^N rami iniziali; tuttavia, i vincoli lo riducono drasticamente. La profondità della ricorsione è N, un livello per ogni riga, e il fattore di ramificazione è al massimo 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') # 92Verifica dei vincoli O(1) con gli insiemi
Verificare la validità scorrendo tutte le regine già posizionate ha costo O(N) per candidato, portando l'algoritmo complessivo a O(N² × N!) nel caso peggiore. È possibile ridurre ogni verifica di validità a O(1) mantenendo tre insiemi: cols (colonne occupate), diag (valori riga-colonna delle diagonali dall'alto a sinistra verso il basso a destra) e anti_diag (valori riga+colonna delle diagonali dall'alto a destra verso il basso a sinistra). Le regine sulla stessa diagonale condividono lo stesso valore riga-colonna; quelle sulla stessa anti-diagonale condividono lo stesso valore riga+colonna.
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))) # 92Spiegazione dell'invariante delle diagonali
L'idea chiave sulle diagonali è che tutte le celle sulla stessa diagonale dall'alto a sinistra verso il basso a destra hanno lo stesso valore di row - col. Ad esempio, (0,0), (1,1), (2,2) hanno tutte row-col=0. Tutte le celle sulla stessa anti-diagonale hanno lo stesso valore di row + col: (0,2), (1,1), (2,0) hanno tutte row+col=2. Questi invarianti a tempo costante consentono di verificare i conflitti sulle diagonali con una ricerca in un insieme in O(1), invece di eseguire una scansione lineare in 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 2Conteggio delle soluzioni: N-Queens II
N-Queens II (LeetCode 52) chiede solo il conteggio, non le scacchiere. Questo consente una piccola ottimizzazione: si salta la costruzione della scacchiera e si incrementa semplicemente un contatore. L'utilizzo di maschere di bit invece degli insiemi può velocizzare ulteriormente il conteggio, portandolo vicino a O(1) per operazione. Il numero di soluzioni cresce in modo non monotono: 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 con maschere di bit per maggiore velocità
Per valori di N molto grandi, un'implementazione con maschere di bit è significativamente più veloce. Si utilizzano tre interi come maschere di bit: cols, left_diag (scorre a sinistra a ogni riga) e right_diag (scorre a destra a ogni riga). Le colonne disponibili sono ((1<<n)-1) & ~(cols|left_diag|right_diag). Si estrae ogni colonna disponibile con bit = available & -available (il bit impostato meno significativo), quindi si procede ricorsivamente. In questo modo si ottiene una verifica dei vincoli O(1) tramite operazioni bitwise.
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)}')Concetto di propagazione dei vincoli
La propagazione dei vincoli va oltre la semplice potatura: dopo aver posizionato una regina, deduce immediatamente ed elimina tutte le posizioni non valide nelle righe successive. È un approccio più aggressivo rispetto al controllo della validità per ogni candidato: restringe proattivamente lo spazio di ricerca prima della biforcazione. L'esempio più famoso è la Arc Consistency nei risolutori SAT e nei risolutori di Sudoku, dove il posizionamento di una cifra elimina le opzioni nella stessa riga, colonna e casella 3×3.
# 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 0Risolutore di Sudoku
Il Sudoku è il problema classico della propagazione dei vincoli. In ogni cella vuota, le cifre valide sono quelle che non compaiono già nella stessa riga, colonna o casella 3×3. Il risolutore con backtracking segue questi passaggi: individua la prima cella vuota, prova ogni cifra valida e richiama ricorsivamente la procedura. Se raggiunge una contraddizione, cioè una cella vuota senza alcuna cifra valida, torna indietro. I buoni risolutori di Sudoku applicano inoltre la propagazione dei vincoli, sotto forma di annotazioni a matita, prima del 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')Euristica della variabile più vincolata
Un'ottimizzazione fondamentale per i problemi di soddisfacimento dei vincoli consiste nello scegliere sempre per prima la variabile più vincolata, cioè la cella con il minor numero di scelte valide. Nel Sudoku, se una cella ha una sola cifra valida, inserirla immediatamente è obbligatorio: non è necessario alcun backtracking. Scegliere per prime queste celle riduce drasticamente la profondità dell'albero di ricerca. Questa è l'euristica Minimum Remaining Values (MRV) della programmazione a vincoli nell'IA.
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 boardTabella del numero di soluzioni di N-Queens
Il numero di soluzioni di N-Queens segue questa sequenza ben nota: 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. Non è nota alcuna formula in forma chiusa; il numero deve essere calcolato. Per N=27 esistono circa 2,34 × 10^17 soluzioni. Nei colloqui tecnici, le domande riguardano generalmente N ≤ 9. Comprendere la crescita esponenziale spiega perché l'ottimizzazione con bitmask è importante per valori di N maggiori.
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]Costruzione della scacchiera di N-Queens
Quando durante un colloquio tecnico Le viene chiesto di restituire le scacchiere effettive (LeetCode 51), costruisca ogni scacchiera a partire dalla lista queens, dove queens[r] indica la colonna della regina nella riga r. Costruzione della stringa: '.' * col + 'Q' + '.' * (n - col - 1) per ogni riga. Questa costruzione O(n²) viene eseguita solo nelle foglie dell'albero delle ricorsioni, quando tutte le N regine sono state posizionate, quindi non influisce sulla complessità complessiva.
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()Verifica rapida
Metta alla prova la Sua comprensione dei concetti di Data Structures & Algorithms — Coding Interview Prep presentati in questa lezione.
Riepilogo della lezione
In questa lezione ha imparato che: N-Queens posiziona una regina per riga e usa insiemi per le colonne, le diagonali (riga-colonna) e le antidiagonali (riga+colonna), così da verificare i vincoli in O(1); le bitmask accelerano ulteriormente i controlli dei vincoli e consentono di esplorare tutti i posizionamenti con un costo vicino a O(1) per operazione; inoltre, la propagazione dei vincoli, tramite l'euristica MRV, riduce la ricerca scegliendo sempre per prima la variabile più vincolata. Nella prossima lezione confronteremo gli approcci Greedy e DP e impareremo quando applicare ciascuno di essi.
Domande Frequenti
La lezione «N-regine e propagazione dei vincoli» è gratuita?
Sì — il testo completo di «N-regine e propagazione dei vincoli» è gratuito qui sul web. Per esercitarvi in modo interattivo (un editor di codice integrato e un tutor IA 24/7) e sbloccare il resto del corso DSA Interview Prep, passa a CoddyKit PRO. Il corso DSA Interview Prep include 4 lezioni in totale.
Cosa imparerò in «N-regine e propagazione dei vincoli»?
Posizioni N regine su una scacchiera N×N usando insiemi per colonne e diagonali, così da verificare i vincoli in O(1), e analizzi la differenza tra contare ed enumerare le soluzioni. Eserciti DSA Interview Prep con codice pratico che esegui direttamente nel browser, e un tutor IA 24/7 risponde alle tue domande mentre lavori sulla lezione.
Ho bisogno di esperienza per iniziare DSA Interview Prep?
Non è richiesta alcuna esperienza precedente. DSA Interview Prep su CoddyKit è strutturato per principianti e studenti avanzati, quindi puoi iniziare da qui o dall'inizio e procedere al tuo ritmo. Questa è la lezione 4 di 4.
Quanto tempo richiede la lezione «N-regine e propagazione dei vincoli»?
La maggior parte delle lezioni CoddyKit richiede circa 5–10 minuti. Ogni lezione è breve e interattiva, quindi fai progressi costanti e riprendi esattamente da dove hai lasciato su web e app.
Posso scrivere ed eseguire codice in questa lezione DSA Interview Prep?
Sì. Ogni lezione DSA Interview Prep include un editor di codice integrato, quindi scrivi ed esegui codice reale direttamente nel tuo browser e ricevi feedback istantaneo dall'IA — nessuna configurazione locale necessaria.
Tutte le lezioni di questo corso
- Schema del backtracking: scegliere, esplorare, annullare la scelta
- Sottoinsiemi e insieme delle parti
- Permutazioni e combinazioni
- N-regine e propagazione dei vincoli