Problème des N reines et propagation des contraintes
Placez N reines sur un échiquier N×N à l’aide d’ensembles de colonnes et de diagonales pour vérifier les contraintes en O(1), puis examinez la différence entre compter et énumérer les solutions.
Problème des N reines et propagation des contraintes est une leçon DSA Interview Prep gratuite sur CoddyKit. Ceci est la leçon 4 sur 4. Tu peux lire la leçon complète ci-dessous gratuitement — puis la pratiquer en direct dans le navigateur avec un éditeur de code intégré et un tuteur IA 24/7. Elle fait partie du parcours d'apprentissage DSA Interview Prep, et ta progression se synchronise sur le web et l'application CoddyKit. Le cours DSA Interview Prep comprend 4 leçons au total.
Le problème des N reines
Le problème des N reines (LeetCode 51/52) vous demande de placer N reines sur un échiquier N×N de sorte qu'aucune paire de reines ne puisse s'attaquer. Les reines attaquent selon les lignes, les colonnes et les deux diagonales. Pour N=4, il existe exactement 2 solutions. Pour N=8 (la version classique), il existe 92 solutions. Il s'agit du problème de retour arrière par excellence, avec une vérification des contraintes qui réduit considérablement l'espace de recherche.
# 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)Placer une reine par ligne
Puisque deux reines ne peuvent pas partager une ligne, nous plaçons exactement une reine par ligne. Le retour arrière progresse ligne par ligne en choisissant une colonne pour chaque ligne. Cela réduit l'espace de recherche, qui passe de N² choix par reine à seulement N colonnes par ligne, ce qui donne N^N branches initiales — mais les contraintes réduisent considérablement ce nombre. La profondeur de récursion est N (un niveau par ligne) et le facteur de branchement est au plus égal à 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') # 92Vérification des contraintes en O(1) avec des ensembles
Vérifier la validité en parcourant toutes les reines déjà placées prend O(N) pour chaque candidate, ce qui donne au total O(N² × N!) dans le pire des cas. Nous pouvons réduire chaque vérification de validité à O(1) en maintenant trois ensembles : cols (colonnes occupées), diag (valeurs row-col pour les diagonales allant du coin supérieur gauche au coin inférieur droit) et anti_diag (valeurs row+col pour les diagonales allant du coin supérieur droit au coin inférieur gauche). Les reines situées sur une même diagonale partagent la même valeur row-col ; sur une même anti-diagonale, elles partagent la même valeur 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))) # 92Explication de l'invariant diagonal
L'idée essentielle concernant les diagonales est la suivante : toutes les cases d'une même diagonale allant du coin supérieur gauche au coin inférieur droit ont la même valeur row - col. Par exemple, (0,0), (1,1) et (2,2) ont toutes la valeur row-col=0. Toutes les cases d'une même anti-diagonale ont la même valeur row + col : (0,2), (1,1) et (2,0) ont toutes la valeur row+col=2. Ces invariants en temps constant nous permettent de vérifier les conflits sur les diagonales avec une recherche dans un ensemble en O(1), plutôt qu'avec un parcours linéaire en 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 2Compter les solutions : N reines II
N reines II (LeetCode 52) demande uniquement le nombre de solutions, et non les échiquiers. Cela permet une légère optimisation : ignorez la construction de l'échiquier et incrémentez simplement un compteur. L'utilisation de masques binaires à la place des ensembles peut accélérer encore le comptage, jusqu'à atteindre un coût proche de O(1) par opération. Le nombre de solutions augmente de manière non monotone : 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 reines avec masque binaire pour plus de rapidité
Pour les valeurs très élevées de N, une implémentation utilisant des masques binaires s'exécute nettement plus rapidement. Utilisez trois entiers comme masques binaires : cols, left_diag (décalé vers la gauche à chaque ligne) et right_diag (décalé vers la droite à chaque ligne). Les colonnes disponibles sont ((1<<n)-1) & ~(cols|left_diag|right_diag). Extrayez chaque colonne disponible avec bit = available & -available (le bit positionné de poids faible), puis poursuivez la récursion. Cette méthode atteint O(1) par vérification de contrainte grâce aux opérations bit à bit.
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)}')Concept de propagation des contraintes
La propagation des contraintes va au-delà du simple élagage : après avoir placé une reine, déduisez immédiatement et éliminez toutes les positions invalides dans les lignes suivantes. Cette approche est plus agressive que la vérification de la validité de chaque candidat : vous réduisez proactivement l’espace de recherche avant d’effectuer une bifurcation. L’exemple le plus célèbre est la cohérence d’arc dans les solveurs SAT et de Sudoku, où le placement d’un chiffre élimine des possibilités dans la même ligne, la même colonne et le même bloc 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 0Solveur de Sudoku
Le Sudoku est le problème classique de propagation des contraintes. Dans chaque case vide, les chiffres valides sont ceux qui ne figurent pas déjà dans la même ligne, la même colonne ou le même bloc 3×3. Le solveur par retour arrière consiste à trouver la première case vide, à essayer chaque chiffre valide, puis à poursuivre récursivement. En cas de contradiction (une case vide sans chiffre valide), effectuez un backtrack. Les bons solveurs de Sudoku appliquent également la propagation des contraintes (notations au crayon) avant le retour arrière.
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')Heuristique de la variable la plus contrainte
Une optimisation essentielle pour les problèmes de satisfaction de contraintes consiste à toujours choisir ensuite la variable la plus contrainte (la case qui possède le moins de choix valides). Dans un Sudoku, si une case ne possède qu’un seul chiffre valide, son remplissage est immédiatement imposé : aucun retour arrière n’est nécessaire. Le fait de choisir ces cases en priorité réduit considérablement la profondeur de l’arbre de recherche. Il s’agit de l’heuristique des valeurs restantes minimales (MRV) utilisée en programmation par contraintes et en intelligence artificielle.
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 boardTableau du nombre de solutions des N-reines
Le nombre de solutions du problème des N-reines suit cette suite bien connue : 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. Aucune formule de forme fermée n’est connue ; le nombre de solutions doit être calculé. Pour N=27, il existe environ 2,34 × 10^17 solutions. Les questions d’entretien portent généralement sur N ≤ 9. Comprendre la croissance exponentielle explique pourquoi l’optimisation par masques de bits est importante pour les grandes valeurs de 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]Construction du plateau des N-reines
Lorsque l’intervieweur vous demande de renvoyer les plateaux réels (LeetCode 51), construisez chaque plateau à partir de la liste queens, où queens[r] indique la colonne de la reine dans la ligne r. Construction de la chaîne : '.' * col + 'Q' + '.' * (n - col - 1) pour chaque ligne. Cette construction en O(n²) n’est effectuée qu’aux feuilles de l’arbre de récursion (lorsque les N reines sont toutes placées), et n’affecte donc pas la complexité globale.
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()Vérification rapide
Vérifiez votre compréhension des concepts de structures de données & algorithmes — préparation aux entretiens de programmation abordés dans cette leçon.
Récapitulatif de la leçon
Dans cette leçon, vous avez appris : le problème des N-reines place une reine par ligne et utilise des ensembles pour les colonnes, les diagonales (ligne-colonne) et les antidiagonales (ligne+colonne), afin de vérifier les contraintes en O(1) ; les masques de bits accélèrent encore la vérification des contraintes et permettent d’explorer tous les placements en quasi-O(1) par opération ; et la propagation des contraintes (heuristique MRV) réduit la recherche en choisissant toujours ensuite la variable la plus contrainte. La prochaine étape consiste à comparer les approches gloutonne et DP et à apprendre quand appliquer chacune d’elles.
Questions Fréquemment Posées
La leçon « Problème des N reines et propagation des contraintes » est-elle gratuite ?
Oui — le texte complet de « Problème des N reines et propagation des contraintes » est gratuit à lire ici sur le web. Pour la pratiquer de manière interactive (un éditeur de code intégré et un tuteur IA 24/7) et déverrouiller le reste du cours DSA Interview Prep, passe à CoddyKit PRO. Le cours DSA Interview Prep comprend 4 leçons au total.
Qu'est-ce que j'apprendrai dans « Problème des N reines et propagation des contraintes » ?
Placez N reines sur un échiquier N×N à l’aide d’ensembles de colonnes et de diagonales pour vérifier les contraintes en O(1), puis examinez la différence entre compter et énumérer les solutions. Tu pratiques DSA Interview Prep avec du code pratique que tu exécutes directement dans le navigateur, et un tuteur IA 24/7 répond à tes questions au fur et à mesure que tu avances dans la leçon.
Dois-je avoir de l'expérience pour commencer DSA Interview Prep ?
Aucune expérience préalable n'est requise. DSA Interview Prep sur CoddyKit est structuré pour les débutants jusqu'aux apprenants avancés, donc tu peux commencer ici ou depuis le début et avancer à ton rythme. Ceci est la leçon 4 sur 4.
Combien de temps prend la leçon « Problème des N reines et propagation des contraintes » ?
La plupart des leçons CoddyKit prennent environ 5–10 minutes. Chacune est courte et interactive, tu progresses régulièrement et tu repiques exactement où tu t'es arrêté sur le web et l'app.
Peux-tu écrire et exécuter du code dans cette leçon DSA Interview Prep ?
Oui. Chaque leçon DSA Interview Prep inclut un éditeur de code intégré, tu écris et exécutes du vrai code directement dans ton navigateur et tu reçois des retours IA instantanés — aucune configuration locale requise.
Toutes les leçons de ce cours
- Modèle de retour sur trace : choisir, explorer, annuler
- Sous-ensembles et ensemble des parties
- Permutations et combinaisons
- Problème des N reines et propagation des contraintes