Divide y vencerás trocea, greedy apuesta, la programación dinámica recuerda. Pero hay problemas donde nada de eso basta: problemas de restricciones, donde la solución es una combinación de decisiones que deben ser compatibles entre sí — asignar conductores a turnos, cuadrar horarios, generar rutas de inspección válidas — y donde no hay recurrencia ni criterio voraz que valga. Para ellos existe la cuarta estrategia del módulo: el backtracking (vuelta atrás), una exploración sistemática del espacio de soluciones que avanza decisión a decisión y, en cuanto detecta un callejón sin salida, deshace el último paso y prueba otra alternativa. Es la más costosa de las cuatro estrategias — su coste es exponencial en el peor caso — pero, bien podada, resuelve problemas ante los que las demás se encogen de hombros. Con ella cerraremos el módulo comparando cara a cara las cuatro estrategias de diseño.

1. La idea: explorar un árbol de decisiones con marcha atrás
2. El esquema general: elegir, explorar, deshacer
3. Ejemplo RutaBus: asignar conductores a turnos con incompatibilidades
4. La poda: por qué importa tanto
5. N-Reinas: el clásico compacto
6. Backtracking vs fuerza bruta vs PD — y las cuatro estrategias frente a frente
7. El coste exponencial

Imagina que construyes la solución por etapas: primera decisión, segunda decisión, tercera... Cada secuencia posible de decisiones es una rama de un árbol de decisiones; las hojas son soluciones candidatas completas. La fuerza bruta genera todas las hojas y comprueba cuáles valen. El backtracking es más listo:

• Recorre el árbol en profundidad, tomando una decisión cada vez (la pila de recursión de 01-02 y 02-02 lleva la cuenta del camino actual).
• En cada nodo comprueba si la solución parcial todavía puede llevar a una solución válida. Si no puede, poda: abandona esa rama entera sin generarla.
• Al agotar las alternativas de un nodo, retrocede (backtrack) al nodo anterior y prueba la siguiente opción.

La diferencia con greedy es radical: greedy toma una decisión y no vuelve jamás; backtracking se reserva siempre el derecho a arrepentirse. La diferencia con la fuerza bruta es la poda: no se examinan combinaciones cuyo fracaso ya está garantizado a mitad de construcción.

Casi todo backtracking se escribe con la misma plantilla de tres tiempos. Merece la pena memorizarla:

Comentemos las piezas clave:

• es_completa: el equivalente al caso base de la recursión (01-02). Aquí una solución completa no corta el algoritmo: se registra y se sigue buscando otras (salvo que solo queramos una: entonces se puede devolver True y propagar el corte).
• es_valido: la función de poda. Comprueba restricciones sobre la solución parcial; cuanto antes detecte la inviabilidad, más árbol se ahorra.
• append / pop: la pareja sagrada. Todo lo que el paso "elegir" modifique, el paso "deshacer" debe restaurarlo exactamente. Trabajamos sobre una única estructura compartida (referencia, no copia — recuerda 02-02) que se va tejiendo y destejiendo.
• El estado del camino vive en la pila de llamadas: al retornar de la recursión estamos, automáticamente, un nivel más arriba del árbol.

El problema. RutaBus debe cubrir mañana los tres turnos de la línea L1 — Mañana, Tarde y Noche — con sus tres conductores de plantilla: Ana, Bruno y Carla. Cada conductor hace exactamente un turno, pero hay restricciones de disponibilidad:

• Ana no puede hacer el turno de noche (cuidado familiar).
• Bruno no puede hacer el de mañana (termina hoy a las 23:00: descanso legal).
• Carla no puede hacer el de tarde (formación obligatoria).

Queremos todas las asignaciones válidas (planificación necesita alternativas por si alguien enferma).

Detalles de implementación que separan un backtracking correcto de uno traicionero:

• soluciones.append(dict(asignacion)): guardamos una copia. Si guardáramos la referencia, el posterior del la vaciaría — el clásico error de copias vs referencias de 02-02.
• La decisión de cada nivel es "qué conductor hace el turno k": el árbol tiene profundidad 3 (una por turno) y hasta 3 ramas por nodo.
• La poda es doble: conductor ya ocupado (libre) y restricción de disponibilidad (compatible).

El árbol de búsqueda completo, con las podas marcadas:

Sigue la rama derecha con el dedo: tras asignar Mañana=Carla y Tarde=Bruno, el único conductor libre para Noche es Ana — pero Ana no hace noches. La rama muere, el algoritmo deshace Tarde=Bruno, prueba la siguiente alternativa (ya no hay), deshace Mañana=Carla... y como tampoco quedan opciones en la raíz, termina con las 2 soluciones encontradas. Ese movimiento de retroceso es literalmente la ejecución del del asignacion[turno] al volver de la recursión.

Sin podas, habríamos generado las 3! = 6 permutaciones completas y descartado 4. Aquí el ahorro es modesto; con 20 turnos y 20 conductores, 20! ≈ 2,4 × 10¹⁸ permutaciones hacen la diferencia entre "imposible" y "al instante" — si las podas cortan pronto.

La poda es la diferencia entre backtracking y suicidio combinatorio. Dos principios:

• Podar cuanto antes. Una restricción comprobada en el nivel 2 elimina subárboles enteros; la misma restricción comprobada en la hoja solo elimina una hoja. Por eso es_valido opera sobre la solución parcial, no sobre la completa.
• Ordenar las decisiones para fallar pronto. Conviene decidir primero la variable más restringida (el turno con menos conductores posibles): los fracasos afloran arriba del árbol, donde podar es barato. Es una heurística de orden, no cambia la corrección.

Conviene ser honestos: la poda no cambia el peor caso. Un adversario puede fabricar instancias donde casi nada se poda. El backtracking pertenece a la familia O(2ⁿ)/O(n!) de la jerarquía de 01-03, y ninguna poda lo saca de ahí en general; lo que hace es volverlo practicable en las instancias reales, que rara vez son adversarias.

El problema de las N reinas — colocar N reinas en un tablero N×N sin que ninguna se ataque (misma fila, columna o diagonal) — es el "hola mundo" del backtracking, y podemos permitírnoslo aquí porque no pertenece a ningún otro módulo. Decisión por nivel: en qué columna va la reina de la fila k.

Fíjate en el truco de representación: guardar solo la columna por fila elimina de raíz los conflictos de fila (cada fila tiene exactamente una reina) — elegir bien la estructura de la solución parcial es en sí mismo una forma de poda. Para n = 8, la fuerza bruta sobre las 8⁸ ≈ 16,7 millones de colocaciones (o las 8! = 40 320 permutaciones, con la representación buena) se queda en unos ~2 000 nodos explorados con poda: ese es el orden de magnitud del ahorro.

Primero el duelo directo:

La regla del pulgar: si puedes definir un subproblema y una recurrencia, la PD convierte el árbol exponencial en una tabla polinómica — hazlo. El backtracking es para cuando los estados no se repiten o no se dejan resumir (cada solución parcial es única, como una asignación concreta de conductores): ahí no hay nada que memoizar y solo queda buscar con inteligencia.

Y el cierre del módulo — las cuatro estrategias frente a frente:

Ante un problema nuevo de RutaBus, este es el orden de interrogatorio recomendado: ¿greedy demostrable? (lo más barato); si no, ¿hay recurrencia con solapamiento? (PD); ¿se parte en mitades independientes? (divide y vencerás); ¿nada de lo anterior pero hay restricciones comprobables? (backtracking). Y si ni siquiera eso, quizá toque una heurística asumida como tal — como nuestro veterano recorrido_supervisor.

Analicemos el backtracking con las herramientas del Módulo 2. En el peor caso, el árbol de decisiones tiene ramificación b (alternativas por nivel) y profundidad n (decisiones): hasta bⁿ nodos. Para asignaciones tipo permutación, el árbol sin podar tiene n! hojas. Es la cima de la jerarquía de 01-03, la zona donde sumar un elemento multiplica el tiempo.

• Tiempo: O(bⁿ) o O(n!) en el peor caso, multiplicado por el coste de es_valido en cada nodo (¡mantenlo barato: idealmente O(1) u O(n) como en N-Reinas!).
• Espacio: sorprendentemente modesto — O(n) para la solución parcial más O(n) de pila de recursión (02-02). El backtracking no guarda el árbol: lo recorre. Por eso puede atacar espacios de búsqueda astronómicos con memoria de bolsillo.
• El caso mejor y el promedio (02-03) dependen brutalmente de las podas y del orden de exploración: dos implementaciones correctas del mismo problema pueden diferir en factores de miles. En backtracking, la ingeniería de la poda es el rendimiento.

• Deshacer a medias. Si "elegir" toca dos estructuras (la asignación y un conjunto de ocupados), "deshacer" debe restaurar las dos. Cualquier asimetría corrompe silenciosamente las ramas siguientes. Revisa que cada append/add/asignación tenga su pop/remove/del espejo.
• Guardar referencias en vez de copias. soluciones.append(asignacion) guarda un objeto que seguirá mutando; al final tendrás una lista de soluciones vacías o todas iguales. Copia (dict(asignacion), lista[:]) al registrar — el matiz de 02-02 atacando de nuevo.
• Podar tarde. Comprobar la validez solo en las hojas convierte el backtracking en fuerza bruta con pasos extra. Pregúntate qué restricciones puedes evaluar con la solución a medias.
• Olvidar el retorno tras registrar. Sin el return al completar la solución, el bucle sigue "extendiendo" una solución ya completa, con errores de índice o soluciones fantasma.
• Recalcular es_valido desde cero. En N-Reinas, valida es O(n); mantener conjuntos de columnas y diagonales ocupadas lo baja a O(1) por consulta a cambio de algo de memoria — el trade-off de 02-02, otra vez. (Y añade dos estructuras más que elegir/deshacer debe mantener en espejo.)
• Usar backtracking donde hay recurrencia. Si detectas subproblemas repetidos, estás pagando precio exponencial por algo que la PD resuelve en polinómico. Repasa la tabla comparativa antes de escribir una línea.

Se incorpora un cuarto turno ("Refuerzo") y un cuarto conductor ("David"), con estas restricciones adicionales: David solo puede hacer Refuerzo o Noche, y Bruno tampoco puede hacer Refuerzo. Adapta asignar_turnos (basta con actualizar las constantes) y calcula a mano, dibujando el árbol, cuántas soluciones válidas hay. Comprueba después con el código.

Escribe rutas_inspeccion(red, origen, k) que genere todas las rutas de inspección de exactamente k paradas que empiecen en origen, sin repetir parada, moviéndose solo entre paradas conectadas. La red es un diccionario de adyacencia, por ejemplo:

En n_reinas, la función valida recorre las reinas ya colocadas: O(n) por comprobación. Reescribe el algoritmo manteniendo tres conjuntos — columnas ocupadas, diagonales fila − col y diagonales fila + col — para que la comprobación sea O(1). No olvides el espejo elegir/deshacer sobre los tres conjuntos.

Solución 1

Constantes nuevas:

Árbol: para Mañana solo caben Ana o Carla. (a) Mañana=Ana → Tarde ∈ {Bruno} (Carla no hace tardes, David tampoco) → Noche ∈ {Carla, David}: con Noche=Carla queda Refuerzo=David ✔; con Noche=David queda Refuerzo=Carla ✔. (b) Mañana=Carla → Tarde ∈ {Ana, Bruno}. Con Tarde=Ana → Noche ∈ {Bruno, David}: Noche=Bruno deja Refuerzo=David ✔; Noche=David deja Refuerzo=Bruno ✘ (Bruno no hace refuerzos: poda y retroceso). Con Tarde=Bruno → Noche ∈ {David} (Ana no hace noches) → Refuerzo=Ana ✔. Total: 4 soluciones. Si tu recuento manual difiere del código, gana el código — y el ejercicio pasa a ser encontrar la rama que contaste mal.

Solución 2

La plantilla de tres tiempos, intacta; solo cambian los candidatos (vecinas en la red) y la poda (no repetir). El vecina not in ruta es una búsqueda en lista O(k) (coste oculto de 02-01); con un set paralelo bajaría a O(1). Esta función es, además, nuestra primera exploración de la red de RutaBus como grafo — una semilla de lo que viene en el Módulo 4.

Solución 3

Las diagonales "descendentes" comparten el valor fila − col y las "ascendentes" el valor fila + col; tres consultas a conjuntos O(1) sustituyen el bucle O(n). El precio: cuatro estructuras que elegir/deshacer deben mantener perfectamente sincronizadas — comprueba que cada add tiene su remove.

El backtracking completa nuestro repertorio: construir la solución por etapas, podar las ramas sin futuro y deshacer para explorar alternativas, con la plantilla elegir–explorar–deshacer como esqueleto universal y la disciplina del espejo (todo lo que se hace se deshace) como regla de oro. Lo hemos aplicado a la asignación de conductores de RutaBus, a las rutas de inspección sobre la red — nuestro primer paseo por ella como grafo — y al clásico N-Reinas, y hemos asumido su naturaleza: coste exponencial en el peor caso que solo la calidad de las podas vuelve practicable. Con esto, el Módulo 3 queda completo: divide y vencerás para subproblemas independientes, greedy para decisiones locales demostrablemente seguras, programación dinámica para subproblemas solapados con recurrencia, y backtracking para restricciones que exigen buscar con vuelta atrás — cuatro moldes, cuatro preguntas de diagnóstico, y el juicio del Módulo 2 para someter a análisis cualquier diseño que salga de ellos. En el Módulo 4 recogeremos la cosecha: los algoritmos clásicos que nacieron de estas estrategias — la búsqueda binaria y los ordenamientos merge sort y quick sort como hijos de divide y vencerás, Dijkstra como el greedy que sí es óptimo, Floyd-Warshall como programación dinámica sobre grafos — implementados y analizados pieza a pieza, empezando por la joya de la eficiencia logarítmica: la búsqueda binaria.