Sesión 38: CTCI Capítulo 8 (Parte 2) — Backtracking Avanzado: Permutaciones con/sin Duplicados y N-Reinas (CTCI 8.7, 8.8 & 8.12)#
Navegación rápida:
- ← Sesión 37: CTCI Ch8 — Backtracking: Subconjuntos y Paréntesis
- Sesión 39: CTCI Ch8 — DP: Triple Step y Robot en Grilla →
- Glosario Maestro
- Guía de Diagramas de Arquitectura
- Tiempo estimado de estudio: 60-75 minutos.
- Código fuente compilado y probado:
practica-rust/dia_38.rs
1. Diccionario de Conceptos del Día (Desde Cero para Junior / Trainee)#
En esta sesión profundizamos en el espacio de búsqueda factorial (N!) y en el control de colisiones geométricas multidimensionales en tiempo constante O(1). Consulta el Glosario Maestro y la Guía de Diagramas.
Espacio de Búsqueda Factorial (N!)#
- (a) En palabras simples (intuición): Organizar a N personas en una fila para tomarse una foto. Para el primer puesto hay N personas posibles; para el segundo quedan N-1; para el tercero N-2, hasta que para el último puesto solo queda 1 persona.
- (b) Definición técnica paso a paso: Cardinalidad de ordenamientos posibles de N elementos distintos:
N! = N × (N-1) × (N-2) × … × 1
Crece a una velocidad astronómica superior a las funciones exponenciales (N! gg 2^N). Para N = 10, 10! ≈ 3.6 × 10⁶; para N = 12, 12! ≈ 4.79 × 10⁸. Requiere control estricto de memoria para evitar congelar el procesador.
- (c) Cómo funciona en Rust (memoria y tipos): Se implementa gestionando un arreglo booleano de elementos activos
used: &mut [bool]o intercambios (swaps) in-place sobre un único vector. - (d) Error típico de Junior: Intentar generar permutaciones creando y filtrando subconjuntos; los subconjuntos ignoran el orden posicional, mientras que las permutaciones dependen críticamente de la secuencia.
Arreglo de Ocupación Booleana (used)#
- (a) En palabras simples (intuición): Una lista de asistencia con casillas de verificación. Cuando asignas a una persona a un puesto de trabajo, marcas su casilla con una palomita verde (True). Cuando termina la jornada y retrocedes a probar otra combinación, borras la marca (False) para que quede disponible nuevamente.
- (b) Definición técnica paso a paso: Vector o rebanada de booleanos
used: Vec<bool>de longitud N. Permite verificar en tiempo O(1) si el elemento en el índice i ya está participando en el camino actual del árbol de búsqueda, previniendo reutilizaciones ilegales. - (c) Cómo funciona en Rust (memoria y tipos): Se asigna una sola vez como
vec![false; n]y se pasa como referencia mutable&mut [bool]. - (d) Error típico de Junior: Usar un vector dinámico y hacer
current.contains(&num)en cada paso; esto agrega una búsqueda lineal O(N) en cada nodo del árbol, degradando la complejidad de O(N · N!) a O(N² · N!).
Invariantes Diagonales en Tiempo Constante O(1) (N-Queens)#
- (a) En palabras simples (intuición): Rayos láser invisibles que cruzan el tablero de ajedrez en diagonal. En lugar de mirar casilla por casilla a lo largo de toda la línea oblicua para ver si hay una reina, cada diagonal tiene un número de identificación grabado en el suelo: si el sensor de ese número ya está activado, sabes que esa diagonal está amenazada en un solo nanosegundo.
- (b) Definición técnica paso a paso: Propiedad geométrica invariable sobre una cuadrícula N × N:
- Diagonal Principal (searrow): Todos los casilleros que pertenecen a la misma diagonal comparten el valor constante de su diferencia de coordenadas: r - c = cte (o normalizado con offset: r + (N - 1) - c).
- Anti-Diagonal (swarrow): Todos los casilleros que pertenecen a la misma diagonal inversa comparten el valor constante de su suma de coordenadas: r + c = cte.
- (c) Cómo funciona en Rust (memoria y tipos): Se implementa con dos vectores booleanos planos
diag1: Vec<bool>ydiag2: Vec<bool>de tamaño 2N - 1. - (d) Error típico de Junior: Escanear el tablero hacia las 4 direcciones diagonales con bucles
while (r >= 0 && c >= 0)en cada intento de colocación de reina, añadiendo una penalización de O(N) por paso.
Poda de Ramas Hermanas con Duplicados (!used[i - 1])#
- (a) En palabras simples (intuición): Tienes dos gemelos idénticos: Juan A y Juan B. Si ya exploraste todas las fotos familiares donde Juan A va en la primera posición de la fila, no tiene ningún sentido empezar de nuevo y poner a Juan B en la primera posición: las fotos resultantes serían visualmente indistinguibles.
- (b) Definición técnica paso a paso: Regla de poda en Permutaciones II (LC 47). Tras ordenar el arreglo numérico:
if i > 0 land nums[i] == nums[i - 1] land neg used[i - 1] ⟹ continue
Si el elemento idéntico anterior no está en uso (!used[i - 1]), significa que ya fue seleccionado, exploró todo su subárbol a este mismo nivel y fue liberado por el pop(). Repetir la exploración con el elemento actual generaría ramas idénticas duplicadas.
- (c) Cómo funciona en Rust (memoria y tipos): Requiere ordenar previamente con
sorted.sort_unstable(). - (d) Error típico de Junior: Escribir
used[i - 1]en lugar de!used[i - 1]; esto podaría las combinaciones legítimas donde ambos gemelos aparecen juntos en distintas posiciones de la misma foto.
2. Desglose Conceptual desde Primeros Principios (Sin Asumir Nada)#
La Matemática de las Diagonales de un Tablero N × N#
Consideremos un tablero de ajedrez de 4 × 4:
TEXT
col=0 col=1 col=2 col=3
r=0 (0,0) (0,1) (0,2) (0,3)
r=1 (1,0) (1,1) (1,2) (1,3)
r=2 (2,0) (2,1) (2,2) (2,3)
r=3 (3,0) (3,1) (3,2) (3,3)1. Anti-Diagonales (swarrow): Suma Constante r + c#
- Casillas
(0, 0): 0 + 0 = 0 - Casillas
(0, 1), (1, 0): 0+1 = 1+0 = 1 - Casillas
(0, 2), (1, 1), (2, 0): 0+2 = 1+1 = 2+0 = 2 - Casillas
(0, 3), (1, 2), (2, 1), (3, 0): 0+3 = 1+2 = 2+1 = 3+0 = 3 - Casillas
(1, 3), (2, 2), (3, 1): 1+3 = 2+2 = 3+1 = 4 - Casillas
(2, 3), (3, 2): 2+3 = 3+2 = 5 - Casillas
(3, 3): 3+3 = 6
El rango posible de la suma es [0 … 2N - 2]. ¡Hay exactamente 2N - 1 anti-diagonales en todo el tablero!
2. Diagonales Principales (searrow): Resta Constante r - c#
- Casillas
(0, 3): 0 - 3 = -3 - Casillas
(0, 2), (1, 3): 0-2 = 1-3 = -2 - Casillas
(0, 1), (1, 2), (2, 3): 0-1 = 1-2 = 2-3 = -1 - Casillas
(0, 0), (1, 1), (2, 2), (3, 3): 0-0 = 1-1 = 2-2 = 3-3 = 0 - Casillas
(1, 0), (2, 1), (3, 2): 1-0 = 2-1 = 3-2 = 1 - Casillas
(2, 0), (3, 1): 2-0 = 3-1 = 2 - Casillas
(3, 0): 3-0 = 3
El rango de la resta va desde -(N - 1) hasta +(N - 1). Para mapear este índice negativo a un arreglo estándar de Rust 0..2N - 1, aplicamos un desplazamiento constante (offset):
Índice en arreglo = (r - c) + (N - 1) = r + (N - 1) - c
¡Ambas consultas toman una sola operación de indexación en memoria en O(1)!
3. Visualización Paso a Paso y Gráfica de Memoria en Rust#
Diagramas de Arquitectura#
- Gráfico SVG vectorial:
 - Código fuente del diagrama: Fuente Mermaid
Flujo de Backtracking y Poda en N-Queens#
DIAGRAMA MERMAID
flowchart TD
ROW["Fila row = 0"] --> COL_LOOP["Probar col en 0..N"]
COL_LOOP --> CHK{"¿cols[col] O diag1[d1] O diag2[d2] activados?"}
CHK -->|Sí (Amenazada)| PRUNE["Poda O(1): Omitir casilla"]
PRUNE --> NEXT_COL{"¿Más columnas?"}
CHK -->|No (Segura)| PLACE["Marcar cols, diag1, diag2 = true<br/>queens_col[row] = col<br/>Descender: backtrack(row + 1)"]
PLACE --> POP["Deshacer: cols, diag1, diag2 = false"]
POP --> NEXT_COL
NEXT_COL -->|Sí| COL_LOOP
NEXT_COL -->|No| RET["Retornar a fila anterior"]Visualización Cuadro por Cuadro de Memoria en Rust (Stack vs Heap)#
Ejecución de permute_unique(&[1, 2, 3]) con búfer y arreglo used:
TEXT
STACK HEAP
+-------------------------------+ +--------------------------------------+
| Frame permute_unique | | path: Vec<i32> |
| nums: &[1, 2, 3] | | Capacidad: 3 |
| path: Vec<i32> -------------+-------------->| [ 1, 2, 3 ] (en una hoja) |
| used: Vec<bool> ------------+------+ +--------------------------------------+
| results: Vec<Vec<i32>> -----+---+ +------->| used: [ true, true, true ] |
+-------------------------------+ | +--------------------------------------+
+---------->| results: Vec<Vec<i32>> |
| [ [1, 2, 3], ... ] |
+--------------------------------------+
Paso 1: Fila 0 elige nums[0] = 1.
- used[0] = true, path.push(1) -> path: [1].
- Llama a backtrack().
Paso 2: Fila 1 elige nums[1] = 2 (used[0] está activo, no puede elegirse 1).
- used[1] = true, path.push(2) -> path: [1, 2].
- Llama a backtrack().
Paso 3: Fila 2 elige nums[2] = 3 (used[0] y used[1] activos).
- used[2] = true, path.push(3) -> path: [1, 2, 3].
- Llama a backtrack().
Paso 4: path.len() == 3 (Hoja alcanzada):
- results.push(path.clone()) -> Almacena [1, 2, 3]. Retorna.
Paso 5: Deshacer decisión en Fila 2:
- path.pop() -> path: [1, 2]. used[2] = false.
- Retorna a Fila 1.
Paso 6: Deshacer decisión en Fila 1:
- path.pop() -> path: [1]. used[1] = false.
- Fila 1 continúa bucle con i=2: elige nums[2] = 3.
- used[2] = true, path.push(3) -> path: [1, 3]...
¡El búfer y el vector `used` permanecen fijos en memoria, evitando allocation churn!4. Las 3 Trampas Clásicas en Entrevistas#
- La Confusión de
used[i - 1]en Permutaciones II: - Escribirif i > 0 && nums[i] == nums[i-1] && used[i-1] continue. Esta condición es exactamente la contraria a la correcta: siused[i-1]es verdadero, significa que el elemento anterior está participando activamente en un nivel superior de la misma permutación, por lo que usar el segundo elemento idéntico es totalmente legítimo. La poda debe actuar cuando!used[i - 1](ramas hermanas). - Generar Duplicados y Filtrar con
HashSetal Final: - Generar N! permutaciones idénticas cuando el arreglo tiene elementos repetidos (como[1, 1, 1, 1, 1]) y luego deduplicar con unHashSetdispara el tiempo a O(N · N!). La poda canónica reduce el tiempo a una sola rama lineal. - Validación Ineficiente de Diagonales en N-Queens: - Escanear el tablero 2D con bucles direccionales añade un factor O(N) por cada casilla evaluada. Utilizar los arreglos booleanos de r + c y r - c evalúa la seguridad en tiempo constante O(1) directo.
5. Implementación Canónica en Rust + Comparativa con Python#
Implementación Canónica en Rust (practica-rust/dia_38.rs)#
RUST
//! Día 38: Backtracking Avanzado: Permutaciones y N-Reinas en Rust.
/// LeetCode 46: Permutaciones de números sin duplicados en O(N * N!).
pub fn permute_unique(nums: &[i32]) -> Vec<Vec<i32>> {
let n = nums.len();
let mut results = Vec::new();
let mut current_path = Vec::with_capacity(n);
let mut used = vec![false; n];
fn backtrack(nums: &[i32], used: &mut [bool], path: &mut Vec<i32>, res: &mut Vec<Vec<i32>>) {
if path.len() == nums.len() {
res.push(path.clone());
return;
}
for i in 0..nums.len() {
if !used[i] {
used[i] = true;
path.push(nums[i]);
backtrack(nums, used, path, res);
path.pop();
used[i] = false;
}
}
}
backtrack(nums, &mut used, &mut current_path, &mut results);
results
}
/// LeetCode 47: Permutaciones con duplicados y poda canónica de ramas hermanas.
pub fn permute_with_dup(nums: &[i32]) -> Vec<Vec<i32>> {
let mut sorted = nums.to_vec();
sorted.sort_unstable();
let mut results = Vec::new();
let mut current_path = Vec::with_capacity(sorted.len());
let mut used = vec![false; sorted.len()];
fn backtrack(nums: &[i32], used: &mut [bool], path: &mut Vec<i32>, res: &mut Vec<Vec<i32>>) {
if path.len() == nums.len() {
res.push(path.clone());
return;
}
for i in 0..nums.len() {
if used[i] {
continue;
}
if i > 0 && nums[i] == nums[i - 1] && !used[i - 1] {
continue; // Poda de rama hermana duplicada
}
used[i] = true;
path.push(nums[i]);
backtrack(nums, used, path, res);
path.pop();
used[i] = false;
}
}
backtrack(&sorted, &mut used, &mut current_path, &mut results);
results
}
/// LeetCode 51: N-Queens I con verificación de diagonales en O(1).
pub fn solve_n_queens(n: usize) -> Vec<Vec<String>> {
let mut results = Vec::new();
let mut queens_col = vec![0usize; n];
let mut cols = vec![false; n];
let mut diag1 = vec![false; 2 * n];
let mut diag2 = vec![false; 2 * n];
fn backtrack(
row: usize,
n: usize,
queens_col: &mut [usize],
cols: &mut [bool],
diag1: &mut [bool],
diag2: &mut [bool],
results: &mut Vec<Vec<String>>,
) {
if row == n {
let mut board = Vec::with_capacity(n);
for r in 0..n {
let c = queens_col[r];
let mut row_str = String::with_capacity(n);
for col_idx in 0..n {
row_str.push(if col_idx == c { 'Q' } else { '.' });
}
board.push(row_str);
}
results.push(board);
return;
}
for col in 0..n {
let d1 = row + col;
let d2 = row + (n - 1) - col;
if !cols[col] && !diag1[d1] && !diag2[d2] {
cols[col] = true;
diag1[d1] = true;
diag2[d2] = true;
queens_col[row] = col;
backtrack(row + 1, n, queens_col, cols, diag1, diag2, results);
cols[col] = false;
diag1[d1] = false;
diag2[d2] = false;
}
}
}
backtrack(0, n, &mut queens_col, &mut cols, &mut diag1, &mut diag2, &mut results);
results
}Implementación Canónica en Python (practica/dia_38_backtracking_permutations_n_queens.py)#
PYTHON
from typing import List, Set
def permute_with_duplicates(nums: List[int]) -> List[List[int]]:
"""CTCI 8.8: Permutaciones con poda canónica de duplicados."""
result: List[List[int]] = []
current: List[int] = []
sorted_nums = sorted(nums)
used = [False] * len(sorted_nums)
def backtrack() -> None:
if len(current) == len(sorted_nums):
result.append(list(current))
return
for i in range(len(sorted_nums)):
if used[i]:
continue
if i > 0 and sorted_nums[i] == sorted_nums[i - 1] and not used[i - 1]:
continue
used[i] = True
current.append(sorted_nums[i])
backtrack()
current.pop()
used[i] = False
backtrack()
return result
def solve_n_queens(n: int) -> List[List[str]]:
"""CTCI 8.12: N-Queens con verificación de diagonales en O(1)."""
result: List[List[str]] = []
queens_col = [-1] * n
cols: Set[int] = set()
diag1: Set[int] = set() # r - c
diag2: Set[int] = set() # r + c
def backtrack(row: int) -> None:
if row == n:
board = ["." * c + "Q" + "." * (n - c - 1) for c in queens_col]
result.append(board)
return
for col in range(n):
if col in cols or (row - col) in diag1 or (row + col) in diag2:
continue
cols.add(col)
diag1.add(row - col)
diag2.add(row + col)
queens_col[row] = col
backtrack(row + 1)
cols.remove(col)
diag1.remove(row - col)
diag2.remove(row + col)
backtrack(0)
return result6. Preguntas de Comprensión Profunda y Diagnóstico Socrático#
Pregunta 1: En Permutaciones II (LeetCode 47), ¿por qué ordenar el arreglo es un requisito preliminar no negociable para que la condición de poda funcione?
Respuesta Técnica Detallada: Porque la comprobación de ramas hermanas idénticas: sorted_nums[i] == sorted_nums[i - 1] asume como precondición fundamental que todos los elementos con valores equivalentes se encuentran contiguos en memoria. Si el arreglo no estuviese ordenado (por ejemplo, [2, 1, 2]), al procesar el segundo 2 en el índice 2, el elemento anterior en el índice 1 es 1. La comparación nums[2] == nums[1] evaluaría a falso, impidiendo que la poda se active. Como consecuencia, el algoritmo exploraría ambas ramas y generaría permutaciones duplicadas como [2, 1, 2] repetidas. Ordenar el arreglo en O(N log N) garantiza la contigüidad física indispensable para la poda en O(1).
Pregunta 2: ¿Cómo se optimiza el algoritmo de N-Queens utilizando operaciones a nivel de bits (Bitmasks) para lograr una ejecución hasta 10 veces más rápida?
Respuesta Técnica Detallada: En lugar de arreglos booleanos o tablas hash, representamos el estado de las amenazas en tres enteros de 32 bits (cols, diag1, diag2):
- Las posiciones ocupadas en la fila actual son la unión de bits:
occupied = cols | diag1 | diag2. - Las posiciones disponibles son el complemento acotado a N bits:
available = ((1 << n) - 1) & ~occupied. - Para extraer la siguiente columna libre en O(1), usamos la clásica operación de silicio:
bit = available & (-available)(aísla el bit menos significativo en 1 instrucción de CPU). - Al descender a la siguiente fila:
- La columna se propaga idéntica:
cols | bit. - La diagonal principal se desplaza a la izquierda:(diag1 | bit) << 1. - La anti-diagonal se desplaza a la derecha:(diag2 | bit) >> 1.
Esto elimina todos los accesos a memoria RAM y ejecuta toda la verificación en registros directos de la CPU.
Pregunta 3: ¿Por qué en N-Queens no necesitamos un arreglo booleano para rastrear filas amenazadas (rows[r])?
Respuesta Técnica Detallada: Porque la estructura misma del árbol de recursión impone la restricción de filas de forma inherente: La función de Backtracking avanza incrementando la fila de uno en uno: backtrack(row + 1). En cada nivel de la recursión se coloca exactamente una sola reina en la fila row, y el algoritmo no vuelve a intentar colocar ninguna otra reina en esa misma fila. Por diseño topológico, cada fila del tablero aloja como máximo y como mínimo una reina, haciendo que cualquier verificación de colisión sobre las filas sea totalmente redundante.
Pregunta 4: ¿Cuál es la diferencia de consumo de memoria física entre resolver Permutaciones con used: Vec<bool> frente a resolverlo mediante intercambios in-place (Swapping)?
Respuesta Técnica Detallada:
- Con arreglo
used: - Requiere un vector auxiliar de booleanos de tamaño N en memoria RAM.
- Preserva el orden lexicográfico natural de generación de permutaciones.
- Es extremadamente legible y fácil de podar ante duplicados.
- *Con intercambios in-place (Swapping)*:
- Aplica
nums.swap(start, i)antes de la llamada ynums.swap(start, i)al volver. - Memoria auxiliar estricta: O(1) (cero arreglos adicionales, opera directamente sobre el arreglo original).
- Desventaja: No genera las permutaciones en orden lexicográfico y la poda de duplicados es considerablemente más compleja de implementar sin usar un set por nivel.
Pregunta 5: ¿Cómo se adapta el algoritmo de N-Queens para resolver el juego de Sudoku (LeetCode 37)?
Respuesta Técnica Detallada: Sudoku es una generalización multidimensional directa del principio de N-Queens:
- En N-Queens verificamos 3 restricciones: columna, diagonal principal y anti-diagonal.
- En Sudoku verificamos 3 restricciones para cada número d ∈ [1 … 9]:
- Fila:
rows[r][d]- Columna:cols[c][d]- Subcuadrícula 3 × 3:boxes[box_index][d], donde boxᵢndex = (r / 3) × 3 + (c / 3). - Al encontrar una celda vacía, iteramos dígitos del 1 al 9, verificamos las 3 restricciones en O(1), marcamos como ocupado, descendemos en recursión, y si ninguna rama concluye con éxito, desmarcamos (Backtracking) y restauramos la celda a vacío.
7. Puente a LeetCode y Práctica de Código#
- LeetCode 46 — Permutations (Medium):
- Permutaciones de números distintos con búfer mutable y arreglo
used. - LeetCode 47 — Permutations II (Medium): - Poda canónica de ramas hermanas idénticas con duplicados.
- LeetCode 51 — N-Queens (Hard): - Generación de tableros con verificación de diagonales en O(1).
- LeetCode 52 — N-Queens II (Hard): - Conteo de soluciones mediante bitmasks ultra-rápidas.
8. Tarea en Papel para Hoy#
Dibuja un tablero de 4 × 4 en tu hoja cuadriculada:
- Aplica el algoritmo de N-Queens a mano colocando la primera reina en la casilla (0, 0).
- Comprueba qué casillas de la fila 1 quedan invalidadas por columna o diagonal.
- Continúa el descenso y documenta el primer callejón sin salida (Backtracking) donde la fila 2 no tiene ninguna casilla legal disponible.
- Llega a la primera solución válida para N = 4 anotando las coordenadas definitivas de las 4 reinas.
Navegación: