N-rainhas e propagação de restrições
Posicione N rainhas em um tabuleiro N×N usando conjuntos de colunas e diagonais para verificar restrições em O(1) e discuta como contar ou enumerar soluções.
N-rainhas e propagação de restrições é uma aula grátis de DSA Interview Prep no CoddyKit. Esta é a aula 4 de 4. Você pode ler a aula completa abaixo gratuitamente — depois pratica ao vivo no navegador com um editor de código integrado e um tutor de IA 24/7. Faz parte do caminho de aprendizado de DSA Interview Prep, e seu progresso é sincronizado entre a web e o app CoddyKit. O curso de DSA Interview Prep inclui 4 aulas no total.
O problema das N-Rainhas
O problema das N-Rainhas (LeetCode 51/52) pede que você coloque N rainhas em um tabuleiro de xadrez N×N de modo que nenhuma delas ataque outra. As rainhas atacam ao longo das linhas, colunas e de ambas as diagonais. Para N=4, existem exatamente 2 soluções. Para N=8 (a versão clássica), existem 92 soluções. Este é o problema clássico de busca com retrocesso, com verificação de restrições que reduz drasticamente o espaço de busca.
# 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)Colocando uma rainha por linha
Como duas rainhas não podem compartilhar uma linha, colocamos exatamente uma rainha por linha. A busca com retrocesso faz a recursão linha por linha, escolhendo uma coluna para cada linha. Isso reduz o espaço de busca de N² escolhas por rainha para apenas N colunas por linha, produzindo N^N ramos iniciais — mas as restrições reduzem esse número drasticamente. A profundidade da recursão é N (um nível por linha), e o fator de ramificação é, no máximo, 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ção de restrições O(1) com conjuntos
Verificar a validade percorrendo todas as rainhas colocadas custa O(N) por candidato, fazendo com que o algoritmo total tenha custo O(N² × N!) no pior caso. Podemos reduzir cada verificação de validade para O(1) mantendo três conjuntos: cols (colunas ocupadas), diag (valores de linha menos coluna para as diagonais do canto superior esquerdo) e anti_diag (valores de linha mais coluna para as diagonais do canto superior direito). As rainhas na mesma diagonal compartilham o mesmo valor de linha menos coluna; na mesma antidiagonal, compartilham o mesmo valor de linha mais coluna.
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))) # 92Explicação do invariante diagonal
A ideia central das diagonais é que todas as células na mesma diagonal do canto superior esquerdo ao canto inferior direito têm o mesmo valor de row - col. Por exemplo, (0,0), (1,1) e (2,2) têm linha menos coluna = 0. Todas as células na mesma antidiagonal têm o mesmo valor de row + col: (0,2), (1,1) e (2,0) têm linha mais coluna = 2. Esses são os invariantes de tempo constante que permitem verificar conflitos diagonais com uma consulta a conjunto O(1), em vez de uma varredura linear 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 2Contando soluções: N-Rainhas II
N-Rainhas II (LeetCode 52) pede apenas a contagem, não os tabuleiros. Isso permite uma pequena otimização: ignore a etapa de construção do tabuleiro e apenas incremente um contador. Usar máscaras de bits em vez de conjuntos pode acelerar ainda mais a contagem, chegando perto de O(1) por operação. O número de soluções cresce de forma não monotônica: 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-Rainhas com máscara de bits para obter velocidade
Para N muito grande, uma implementação com máscara de bits é significativamente mais rápida. Use três inteiros como máscaras de bits: cols, left_diag (desloca-se para a esquerda a cada linha) e right_diag (desloca-se para a direita a cada linha). As colunas disponíveis são ((1<<n)-1) & ~(cols|left_diag|right_diag). Extraia cada coluna disponível com bit = available & -available (o bit definido mais baixo) e faça a recursão. Isso proporciona O(1) por verificação de restrição, usando operações bit a 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)}')Conceito de propagação de restrições
A propagação de restrições vai além da simples poda: depois de posicionar uma rainha, deduza e elimine imediatamente todas as posições inválidas nas linhas futuras. Isso é mais agressivo do que verificar a validade de cada candidato — você reduz proativamente o espaço de busca antes de ramificar. O exemplo mais famoso é a consistência de arco em resolvedores de SAT e de Sudoku, nos quais posicionar um dígito elimina opções na mesma linha, coluna e caixa 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 0Resolvedor de Sudoku
Sudoku é o problema canônico de propagação de restrições. Em cada célula vazia, as opções de dígitos válidas são aquelas que ainda não aparecem na mesma linha, coluna ou caixa 3×3. O solucionador por retrocesso faz o seguinte: encontra a primeira célula vazia, tenta cada dígito válido e faz uma chamada recursiva. Se chega a uma contradição (célula vazia sem nenhum dígito válido), faz backtrack. Bons resolvedores de Sudoku também aplicam propagação de restrições (marcas de lápis) antes do retrocesso.
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')Heurística da variável mais restrita
Uma otimização importante para problemas de satisfação de restrições: escolha sempre primeiro a variável mais restrita (a célula com menos opções válidas). No Sudoku, se uma célula tiver apenas 1 dígito válido, preenchê-la imediatamente é obrigatório — não é necessário fazer retrocesso. Escolher essas células primeiro reduz drasticamente a profundidade da árvore de busca. Essa é a heurística de valores mínimos restantes (MRV), usada na programação de restrições em 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 boardTabela da contagem de soluções de N-Rainhas
O número de soluções de N-Rainhas segue esta sequência conhecida: 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. Não se conhece nenhuma fórmula fechada; a contagem precisa ser calculada. Para N=27, existem cerca de 2,34 × 10^17 soluções. Em entrevistas, normalmente são usados valores de N ≤ 9. Entender o crescimento exponencial justifica a importância da otimização por máscaras de bits para valores maiores 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]Construção do tabuleiro de N-Rainhas
Quando o entrevistador pede que você retorne os tabuleiros reais (LeetCode 51), construa cada tabuleiro a partir da lista queens, na qual queens[r] é a coluna da rainha na linha r. Construção da cadeia de caracteres: '.' * col + 'Q' + '.' * (n - col - 1) para cada linha. Essa construção O(n²) só é executada nas folhas da árvore de recursão (quando todas as N rainhas foram posicionadas), portanto não afeta a complexidade geral.
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ção rápida
Verifique sua compreensão dos conceitos de Estruturas de Dados & Algoritmos — Preparação para entrevistas de programação desta lição.
Recapitulação da lição
Nesta lição, você aprendeu: N-Rainhas posiciona uma rainha por linha e usa conjuntos para colunas, diagonais (linha-coluna) e antidiagonais (linha+coluna), permitindo verificar restrições em O(1); as máscaras de bits aceleram ainda mais as verificações de restrições e permitem explorar todos os posicionamentos em quase O(1) por operação; e a propagação de restrições (heurística MRV) reduz a busca ao escolher sempre primeiro a variável mais restrita. A seguir, compararemos as abordagens gulosa e DP e aprenderemos quando aplicar cada uma.
Perguntas Frequentes
A aula “N-rainhas e propagação de restrições” é grátis?
Sim — o texto completo de “N-rainhas e propagação de restrições” é grátis para ler aqui na web. Para praticá-la interativamente (um editor de código integrado e um tutor de IA 24/7) e desbloquear o restante do curso de DSA Interview Prep, atualize para CoddyKit PRO. O curso de DSA Interview Prep inclui 4 aulas no total.
O que vou aprender em “N-rainhas e propagação de restrições”?
Posicione N rainhas em um tabuleiro N×N usando conjuntos de colunas e diagonais para verificar restrições em O(1) e discuta como contar ou enumerar soluções. Você pratica DSA Interview Prep com código prático que executa diretamente no navegador, e um tutor de IA 24/7 responde suas dúvidas enquanto trabalha na aula.
Preciso ter experiência prévia para começar DSA Interview Prep?
Nenhuma experiência prévia é necessária. DSA Interview Prep no CoddyKit é estruturado para alunos iniciantes até avançados, então você pode começar aqui ou desde o início e aprender no seu ritmo. Esta é a aula 4 de 4.
Quanto tempo leva a aula “N-rainhas e propagação de restrições”?
A maioria das aulas CoddyKit leva cerca de 5–10 minutos. Cada uma é compacta e interativa, então você faz progresso constante e retoma exatamente de onde parou entre web e app.
Posso escrever e executar código nesta aula de DSA Interview Prep?
Sim. Cada aula de DSA Interview Prep inclui um editor de código integrado, então você escreve e executa código real direto no navegador e recebe feedback de IA instantaneamente — nenhuma configuração local necessária.
Todas as aulas deste curso
- Modelo de Retrocesso: Escolher, Explorar, Desfazer
- Subconjuntos e conjunto das partes
- Permutações e combinações
- N-rainhas e propagação de restrições