Backtracking: N reinas, subconjuntos, permutaciones
Construye un candidato de forma incremental; abandónalo en cuanto esté condenado.
Búsqueda en profundidad + PODA.
El movimiento: prueba — recursa — deshaz
- Toma una decisión; recursa para tomar la siguiente; deshazla si la recursión falla
- N reinas: coloca una reina por columna, sáltate las filas atacadas (poda)
- Columna sin salida → regrésate, quita una reina, prueba una fila más arriba
- Los subconjuntos y las permutaciones son el mismo esqueleto
Míralo buscar
♛ verde = colocada en una casilla segura · rojo = atacada → podada · naranja = backtrack (deshacer).
Cada casilla roja descarta una rama entera sin examinarla.
Poda vs fuerza bruta
N=12: fuerza bruta 8.9 billones de arreglos, backtracking 10 millones de nodos → 880,000× menos.
La poda es el algoritmo
- Un conflicto en la columna 3 poda TODOS los arreglos del resto — sin examinarlos
- Poda más fuerte: forward checking, propagación de restricciones, ordenamiento de variables
- Este esqueleto + poda inteligente = solvers SAT, programación con restricciones
- Sigue siendo exponencial en el peor caso — tratable en la práctica, no polinomial
Para llevar
No preguntes "cómo genero todos los candidatos" — pregunta "qué tan temprano puedo rechazar uno".
Deja el DESHACER perfectamente bien, o las ramas posteriores van a ver estado corrupto.
Siguiente: dos punteros y ventana deslizante — recorridos O(n²) → pasadas O(n).