N reinas y propagación de restricciones
Coloque N reinas en un tablero de N×N usando conjuntos de columnas y diagonales para comprobar restricciones en O(1), y analice cómo contar las soluciones frente a enumerarlas.
N reinas y propagación de restricciones es una lección gratuita de DSA Interview Prep en CoddyKit. Esta es la lección 4 de 4. Puedes leer la lección completa abajo gratuitamente — luego la practicas en el navegador con un editor de código integrado y un tutor de IA 24/7. Forma parte de la ruta de aprendizaje de DSA Interview Prep, y tu progreso se sincroniza en la web y la app de CoddyKit. El curso de DSA Interview Prep incluye 4 lecciones en total.
El problema de las N reinas
El problema de las N reinas (LeetCode 51/52) consiste en colocar N reinas en un tablero de ajedrez de N×N de modo que ninguna pareja de reinas pueda atacarse. Las reinas atacan a lo largo de las filas, las columnas y ambas diagonales. Para N=4, existen exactamente 2 soluciones. Para N=8 (la versión clásica), existen 92 soluciones. Este es el problema de backtracking por excelencia, con comprobación de restricciones que poda drásticamente el espacio de búsqueda.
# 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)Colocación de una reina por fila
Como dos reinas no pueden compartir una fila, colocamos exactamente una reina por fila. El backtracking avanza fila por fila y elige una columna para cada fila. Esto reduce el espacio de búsqueda: pasa de N² opciones por reina a solo N columnas por fila, lo que produce N^N ramas iniciales; sin embargo, las restricciones lo reducen drásticamente. La profundidad de la recursión es N (un nivel por fila) y el factor de ramificación es como 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') # 92Comprobación de restricciones en O(1) con conjuntos
Comprobar la validez recorriendo todas las reinas colocadas cuesta O(N) por candidato, lo que hace que el algoritmo completo tenga una complejidad O(N² × N!) en el peor caso. Podemos reducir cada comprobación de validez a O(1) manteniendo tres conjuntos: cols (columnas ocupadas), diag (valores de fila-columna para las diagonales de arriba a la izquierda) y anti_diag (valores de fila+columna para las diagonales de arriba a la derecha). Las reinas de una misma diagonal comparten el mismo valor de fila-columna; las de una misma antidiagonal comparten el mismo valor de fila+columna.
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))) # 92Explicación del invariante diagonal
La idea clave de las diagonales es que todas las celdas de una misma diagonal, desde la esquina superior izquierda hasta la inferior derecha, tienen el mismo valor de row - col. Por ejemplo, (0,0), (1,1) y (2,2) tienen row-col=0. Todas las celdas de una misma antidiagonal tienen el mismo valor de row + col: (0,2), (1,1) y (2,0) tienen row+col=2. Estos son los invariantes de tiempo constante que permiten comprobar los conflictos diagonales mediante una búsqueda O(1) en un conjunto, en lugar de recorrer linealmente los elementos 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 2Recuento de soluciones: N-Queens II
N-Queens II (LeetCode 52) solo solicita el recuento, no los tableros. Esto permite una ligera optimización: se omite la construcción del tablero y simplemente se incrementa un contador. Usar máscaras de bits en lugar de conjuntos puede acelerar aún más el recuento, hasta alcanzar un coste cercano a O(1) por operación. El número de soluciones no crece de forma monótona: 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 máscaras de bits para mayor velocidad
Para valores muy grandes de N, una implementación con máscaras de bits es considerablemente más rápida. Use tres enteros como máscaras de bits: cols, left_diag (se desplaza a la izquierda en cada fila) y right_diag (se desplaza a la derecha en cada fila). Las columnas disponibles son ((1<<n)-1) & ~(cols|left_diag|right_diag). Extraiga cada columna disponible con bit = available & -available (el bit activado de menor valor) y, después, continúe con la recursión. Así se consigue una comprobación de restricciones O(1) mediante operaciones a nivel de bits.
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)}')Concepto de propagación de restricciones
La propagación de restricciones va más allá de la poda simple: después de colocar una reina, deduce y elimina inmediatamente todas las posiciones no válidas de las filas futuras. Este enfoque es más agresivo que comprobar la validez de cada candidato: reduce de forma proactiva el espacio de búsqueda antes de ramificar. El ejemplo más conocido es la consistencia de arco en los solucionadores SAT y de Sudoku, donde colocar un dígito elimina opciones de la misma fila, columna y región de 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 0Solucionador de Sudoku
El Sudoku es el problema canónico de propagación de restricciones. En cada celda vacía, las opciones de dígitos válidas son aquellas que aún no aparecen en la misma fila, columna o región de 3×3. El solucionador mediante backtracking hace lo siguiente: encuentra la primera celda vacía, prueba cada dígito válido y continúa recursivamente. Si llega a una contradicción (una celda vacía sin ningún dígito válido), retrocede. Los buenos solucionadores de Sudoku también aplican propagación de restricciones (anotaciones a lápiz) antes 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')Heurística de la variable más restringida
Una optimización clave para los problemas de satisfacción de restricciones: elija siempre a continuación la variable más restringida (la celda con menos opciones válidas). En Sudoku, si una celda solo tiene 1 dígito válido, rellenarla inmediatamente es obligatorio: no hace falta retroceder. Elegir primero estas celdas reduce drásticamente la profundidad del árbol de búsqueda. Esta es la heurística de valores mínimos restantes (MRV) de la programación de restricciones en 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 boardTabla del número de soluciones de N reinas
El número de soluciones del problema de las N reinas sigue esta conocida secuencia: 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. No se conoce ninguna fórmula cerrada; el número debe calcularse. Para N=27, existen aproximadamente 2.34 × 10^17 soluciones. En las entrevistas normalmente se pregunta por N ≤ 9. Comprender el crecimiento exponencial permite justificar por qué la optimización con máscaras de bits es importante para valores mayores 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]Construcción del tablero de N reinas
Cuando el entrevistador le pida devolver los tableros reales (LeetCode 51), construya cada tablero a partir de la lista queens, donde queens[r] es la columna de la reina en la fila r. Construcción de la cadena: '.' * col + 'Q' + '.' * (n - col - 1) para cada fila. Esta construcción O(n²) solo se ejecuta en las hojas del árbol de recursión (cuando se han colocado las N reinas), por lo que no afecta a la complejidad general.
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()Comprobación rápida
Compruebe su comprensión de los conceptos de Data Structures & Algorithms — Coding Interview Prep de esta lección.
Resumen de la lección
En esta lección ha aprendido que: N-Queens coloca una reina por fila y utiliza conjuntos para las columnas, las diagonales (fila-columna) y las antidiagonales (fila+columna), lo que permite comprobar las restricciones en O(1); las máscaras de bits aceleran aún más las comprobaciones de restricciones y permiten explorar todas las colocaciones con un coste cercano a O(1) por operación; y la propagación de restricciones (heurística MRV) reduce la búsqueda al elegir siempre a continuación la variable más restringida. A continuación, compararemos los enfoques voraz y de programación dinámica, y aprenderemos cuándo aplicar cada uno.
Preguntas frecuentes
¿La lección «N reinas y propagación de restricciones» es gratis?
Sí — el texto completo de «N reinas y propagación de restricciones» es gratis para leer aquí en la web. Para practicarla de forma interactiva (editor de código integrado y tutor de IA 24/7) y desbloquear el resto del curso de DSA Interview Prep, actualiza a CoddyKit PRO. El curso de DSA Interview Prep incluye 4 lecciones en total.
¿Qué aprenderé en «N reinas y propagación de restricciones»?
Coloque N reinas en un tablero de N×N usando conjuntos de columnas y diagonales para comprobar restricciones en O(1), y analice cómo contar las soluciones frente a enumerarlas. Practicas DSA Interview Prep con código real que ejecutas directamente en el navegador, y un tutor de IA 24/7 responde tus preguntas mientras trabajas en la lección.
¿Necesito experiencia previa para empezar DSA Interview Prep?
No se requiere experiencia previa. DSA Interview Prep en CoddyKit está estructurado para principiantes hasta estudiantes avanzados, así que puedes empezar aquí o desde el inicio y avanzar a tu ritmo. Esta es la lección 4 de 4.
¿Cuánto tiempo toma la lección «N reinas y propagación de restricciones»?
La mayoría de las lecciones de CoddyKit toman alrededor de 5–10 minutos. Cada una es compacta e interactiva, así que avanzas constantemente y retomas exactamente por donde dejaste en la web y la app.
¿Puedo escribir y ejecutar código en esta lección de DSA Interview Prep?
Sí. Cada lección de DSA Interview Prep incluye un editor de código integrado, así que escribes y ejecutas código real directamente en tu navegador y obtienes retroalimentación instantánea de IA — sin configuración local necesaria.
Todas las lecciones de este curso
- Plantilla de backtracking: elegir, explorar y deshacer
- Subconjuntos y conjunto potencia
- Permutaciones y combinaciones
- N reinas y propagación de restricciones