AALIE

Backtracking

Modelado de soluciones como n-tuplas, exploración DFS, poda por factibilidad y ejemplo completo de N-Reinas.

Backtracking: idea central

Backtracking es una técnica de búsqueda sistemática. Construye una solución paso a paso, prueba candidatos y retrocede tan pronto detecta que la solución parcial ya no puede convertirse en una solución válida.

La exploración se hace en profundidad. Primero se intenta completar una rama del árbol de decisiones. Si la rama falla, se vuelve al nivel anterior y se prueba el siguiente candidato.

Idea esencial

Backtracking no evita que el problema sea combinatorio. Lo que hace es no perder tiempo completando combinaciones que ya son imposibles desde una etapa intermedia.

Backtracking vs fuerza bruta

Criterio	Fuerza bruta	Backtracking
Construcción	Genera combinaciones completas.	Construye soluciones parciales.
Momento de descarte	Filtra después de generar.	Poda antes de completar la rama.
Estructura típica	Bucles anidados o generación completa.	Recursión + validación + retroceso.

Caracterización de problemas resolubles por backtracking

Un problema encaja bien con backtracking cuando puede expresarse como una secuencia de decisiones. Cada decisión llena una posición de un vector solución.

Modelo de solución

X = (x_{0}, x_{1}, \dots, x_{n - 1}), x_{i} \in S_{i}

X representa el vector solución final de tamaño n. Cada xi es la decisión tomada en la etapa i (por ejemplo, el número de columna), y Si es el conjunto de valores posibles para esa decisión.

Modelo de solución parcial

X_{k} = (x_{0}, x_{1}, \dots, x_{k}, ?, \dots, ?)

Xk es una solución incompleta que ya tiene valores asignados hasta la posición k. Los signos de interrogación (?) indican las decisiones que aún no se han tomado.

Tamaño del espacio de soluciones

∣ E ∣ = i = 0 \prod n - 1 ∣ S_{i} ∣

El tamaño total del espacio de búsqueda |E| es el producto del número de opciones disponibles en cada nivel. Esto explica por qué el costo crece tan rápido al aumentar n.

Condiciones para aplicar backtracking

Condición	Significado	Pregunta de control
Solución como n-tupla	La solución se puede escribir como una secuencia de decisiones.	¿Puedo representar una solución como $(x_{0}, x_{1}, \dots, x_{n - 1})$ ?
Conjuntos finitos de candidatos	Cada decisión toma valores desde un conjunto acotado.	¿Cada $x_{i}$ sale de un conjunto finito $S_{i}$ ?
Restricciones parciales	Se puede detectar invalidez antes de completar toda la solución.	¿Puedo podar una rama apenas viola una regla?
Árbol de decisiones	Cada nivel representa una posición o etapa del vector solución.	¿Los hijos de un nodo son los candidatos para la siguiente decisión?

Decidir no es lo mismo que optimizar

Backtracking puede buscar una solución válida, todas las soluciones válidas o la mejor solución bajo un criterio. El modelo debe decir cuál de esas tres metas se persigue.

Modelo general de backtracking

En el nivel $k$ del árbol se intenta asignar un valor a $x_{k}$ . Si el candidato mantiene válida la solución parcial, se avanza al nivel $k + 1$ . Si no, se descarta esa rama.

Modelo de candidatos

C_{k} (X_{k - 1}) = {v \in S_{k} ∣ c an d i d a t o (v, k, X_{k - 1})}

Ck es el conjunto de valores válidos para la posición k, condicionados por la solución parcial previa Xk-1.

Modelo de poda por factibilidad

B_{k} (X_{k - 1}, v) = {verdadero, falso, X_{k - 1} \cup {x_{k} = v} puede extenderse a una soluci \overset{o}{ˊ} n X_{k - 1} \cup {x_{k} = v} viola restricciones

Bk es el predicado de poda o factibilidad. Si es falso, la rama se corta inmediatamente porque se ha detectado que esa combinación no puede llevar a una solución válida.

Modelo de avance y retroceso

X_{k} = {X_{k - 1} \cup {x_{k} = v}, X_{k - 1}, B_{k} (X_{k - 1}, v) = verdadero B_{k} (X_{k - 1}, v) = falso

Este modelo muestra cómo el vector solución avanza si el candidato es factible (unión de estados) o se mantiene en el estado previo si el candidato debe ser descartado.

Modelo de solución completa

es S o l u c i o n (X_{k}) = {verdadero, falso, k = n - 1 y X_{k} satisface todas las restricciones en otro caso

esSolucion indica que el proceso termina con éxito solo cuando llegamos al último nivel (n-1) y todas las restricciones del problema se cumplen.

Elements del modelo

Elemento	Rol	Ejemplo en N-Reinas
$k$	Nivel o etapa de decisión.	Fila actual del tablero.
$x_{k}$	Valor elegido en la etapa k.	Columna elegida para la reina de la fila k.
$S_{k}$	Conjunto de candidatos.	${1, 2, \dots, n}$
$B_{k}$	Predicado de factibilidad o poda.	No compartir columna ni diagonal.

Esquema algorítmico

El patrón básico es recursivo: si la solución está completa, se reporta; si no, se prueban candidatos para la siguiente posición. Cada candidato válido abre una llamada recursiva. Al volver, se deshace la decisión.

Backtracking general

backtracking(k, X[n]) BEGIN
 IF (esSolucion(k, X)) THEN BEGIN
 reportar(X);
 RETURN 1;
 END

 total <- 0;

 FOR cada candidato v EN candidatos(k, X) DO BEGIN
 IF (factible(k, v, X)) THEN BEGIN
 X[k] <- v;
 total <- total + backtracking(k + 1, X);
 X[k] <- NULL;
 END
 END

 RETURN total;
END

Flujo de una llamada de backtracking

Renderizando diagrama...

Deshacer es obligatorio

Si no se deshace la decisión al volver de la llamada recursiva, el siguiente candidato se evalúa sobre un estado contaminado. Ese error rompe el algoritmo.

Ejemplo: N-Reinas — planteamiento

El problema de las N-Reinas consiste en ubicar $n$ reinas en un tablero $n \times n$ sin que dos reinas se ataquen. Dos reinas se atacan si comparten fila, columna o diagonal.

Como no puede haber dos reinas en la misma fila, se coloca exactamente una reina por fila. Entonces la decisión de cada nivel ya no es escoger una casilla cualquiera del tablero, sino escoger la columna para la fila actual.

Modelo de solución

X = (x_{1}, x_{2}, \dots, x_{n}), x_{i} = columna de la reina en la fila i

En este vector X, el índice i representa la fila del tablero y el valor xi representa la columna donde ubicamos la reina de esa fila.

Modelo de candidatos

S_{i} = {1, 2, \dots, n}

Para cada fila, los candidatos Si son simplemente los números de columna del 1 al n.

Modelo de factibilidad

v a l i d o (i, c) = {verdadero, falso, \forall r < i : c \neq = x_{r} \land ∣ i - r ∣ \neq = ∣ c - x_{r} ∣ en otro caso

La función revisa que la columna c no se repita y que no haya ataques en diagonal. La fórmula |i-r| != |c-xr| asegura que la distancia en filas no sea igual a la distancia en columnas, lo cual caracteriza a las diagonales.

Modelo de solución completa

es S o l u c i o n (i, X) = {verdadero, falso, i = n + 1 i \leq n

La condición i=n+1 significa que ya hemos logrado colocar una reina en cada una de las n filas del tablero.

Reducción del espacio de búsqueda

Modelo	Espacio aproximado	Comentario
Elegir cualquier casilla para cada reina	$(n^{2})^{n}$	Demasiado grande y con muchas combinaciones obviamente inválidas.
Una reina por fila	$n^{n}$	Cada nivel decide una columna.
Una reina por fila y sin repetir columnas	$n!$	La poda por columna reduce drásticamente el árbol.

N-Reinas 4×4 — seguimiento paso a paso

Para $n = 4$ una solución puede representarse como $X = (2, 4, 1, 3)$ . Esto significa: fila 1 columna 2, fila 2 columna 4, fila 3 columna 1 y fila 4 columna 3.

Tablero solución para X = (2,4,1,3)

Fila	Col 1	Col 2	Col 3	Col 4
1	·	Q	·	·
2	·	·	·	Q
3	Q	·	·	·
4	·	·	Q	·

Seguimiento hasta encontrar X = (2,4,1,3)

Paso	Fila	Columna probada	¿Válida?	Acción
1	1	1	Sí	Colocar reina y avanzar.
2	2	1	No	Misma columna. Probar siguiente.
3	2	2	No	Diagonal. Probar siguiente.
4	2	3	Sí	Colocar reina y avanzar.
5	3	1,2,3,4	No	Todas fallan por columna o diagonal. Retroceder.
6	2	4	Sí	Reemplazar columna 3 por 4 y avanzar.
7	3	1,2,3,4	No	Todas fallan. Retroceder a fila 1.
8	1	2	Sí	Nueva rama: colocar en fila 1 columna 2.
9	2	4	Sí	Colocar y avanzar.
10	3	1	Sí	Colocar y avanzar.
11	4	3	Sí	Solución encontrada.

Fragmento del árbol de decisiones

Renderizando diagrama...

Resultado

Una solución válida para el tablero 4×4 es $X = (2, 4, 1, 3)$ . Ninguna pareja de reinas comparte columna ni diagonal.

N-Reinas — algoritmo

Condición de validez

v a l i d o (f i l a, co l) = {verdadero, falso, \forall r < f i l a : co l \neq = X [r] \land ∣ f i l a - r ∣ \neq = ∣ co l - X [r] ∣ en otro caso

Este modelo unifica las restricciones: la reina actual no debe compartir columna (col != X[r]) ni diagonal (distancia absoluta de filas != distancia absoluta de columnas) con ninguna reina colocada previamente.

N-Reinas con backtracking

nReinas(n) BEGIN
 X[1..n] <- NULL;
 RETURN ubicarReina(1, n, X);
END

ubicarReina(fila, n, X[n]) BEGIN
 IF (fila = n + 1) THEN BEGIN
 reportar(X);
 RETURN 1;
 END

 total <- 0;

 FOR col <- 1 TO n DO BEGIN
 IF (esValida(fila, col, X)) THEN BEGIN
 X[fila] <- col;
 total <- total + ubicarReina(fila + 1, n, X);
 X[fila] <- NULL;
 END
 END

 RETURN total;
END

Validación de una posición

esValida(fila, col, X[n]) BEGIN
 FOR r <- 1 TO fila - 1 DO BEGIN
 IF (X[r] = col) THEN BEGIN
 RETURN F;
 END

 IF (abs(fila - r) = abs(col - X[r])) THEN BEGIN
 RETURN F;
 END
 END

 RETURN T;
END

Reglas de validación

Regla	Modelo	Significado
No misma columna	$co l \neq = X [r]$	Dos reinas en la misma columna se atacan.
No misma diagonal	$∣ f i l a - r ∣ \neq = ∣ co l - X [r] ∣$	En una diagonal, la diferencia de filas coincide con la diferencia de columnas.

Complejidad de backtracking

La complejidad de backtracking depende del número de nodos visitados en el árbol de búsqueda y del costo de validar cada candidato. La poda puede reducir mucho el trabajo real, pero el peor caso sigue siendo combinatorio.

Modelo general de costo

T (n) = k = 0 \sum d N_{k} \cdot C_{v a l i d a r} (k)

Nk es el número de nodos visitados en el nivel k del árbol y Cvalidar es el costo de ejecutar la función de factibilidad en ese nivel.

Peor caso con factor de ramificación uniforme

T (d) = {Θ (b^{d} \cdot C_{v a l i d a r}), Θ (N_{v i s i t a d os} \cdot C_{v a l i d a r}), si se visitan casi todas las ramas si la poda reduce el \overset{a}{ˊ} rbol

En el peor caso, b es el factor de ramificación (promedio de hijos por nodo) y d es la profundidad del árbol. La poda busca que los nodos visitados sean mucho menos que el total teórico bd.

Cota típica para N-Reinas

T (n) = ⎩ ⎨ ⎧ O (n^{n} \cdot n), O (n! \cdot n), O (n!), si se permite repetir columnas y validar cuesta O (n) si se evita repetir columnas y validar cuesta O (n) si columnas y diagonales se validan en O (1)

El costo n! aparece cuando evitamos repetir columnas. Si también validamos en tiempo constante O(1), el costo se reduce simplemente al número de nodos del árbol factorial.

Factores que afectan el costo

Factor	Efecto	Ejemplo
Profundidad	Número de decisiones que deben tomarse.	En N-Reinas, profundidad $n$ .
Ramificación	Número de candidatos por decisión.	Columnas posibles por fila.
Poda	Reduce ramas exploradas.	Descartar columnas y diagonales atacadas.
Costo de validar	Multiplica cada nodo visitado.	$O (n)$ con escaneo, $O (1)$ con arreglos auxiliares.

La poda no cambia automáticamente el peor caso

Que el algoritmo pode muchas ramas en ejemplos pequeños no significa que el peor caso deje de ser exponencial o factorial. Para cambiar la cota hay que justificar formalmente cuántos nodos se eliminan.

Optimización de validación y poda

Aunque el árbol de búsqueda siga siendo grande, se puede mejorar mucho el tiempo real reduciendo el costo de validar candidatos y ordenando los candidatos de forma más útil.

Validación O(1) en N-Reinas

v a l i d o (f i l a, co l) = {verdadero, falso, \neg co l U s a d a [co l] \land \neg d ia g A [f i l a - co l] \land \neg d ia g B [f i l a + co l] en otro caso

Mediante arreglos booleanos para columnas y diagonales (identificadas por fila+col y fila-col), podemos saber si una casilla está amenazada en tiempo constante O(1), sin necesidad de recorrer las reinas anteriores.

Optimizaciones frecuentes

Optimización	Idea	Efecto
Arreglos de columnas	Guardar qué columnas ya están ocupadas.	Evita escanear reinas previas para columnas.
Arreglos de diagonales	Guardar diagonales ocupadas por índices $f i l a - co l$ y $f i l a + co l$ .	Validación de diagonales en tiempo constante.
Orden de candidatos	Probar primero candidatos más prometedores.	Puede encontrar una solución antes, aunque no mejora necesariamente el peor caso.
Poda por límite	Detectar que ni completando todos los pasos restantes se alcanza la meta.	Útil en suma de subconjuntos y problemas de selección.

N-Reinas con validación O(1)

ubicarReinaRapido(fila, n, X[n], colUsada[n], diagA[2*n], diagB[2*n]) BEGIN
 IF (fila = n + 1) THEN BEGIN
 reportar(X);
 RETURN 1;
 END

 total <- 0;

 FOR col <- 1 TO n DO BEGIN
 dA <- fila - col + n;
 dB <- fila + col;

 IF (NOT colUsada[col] AND NOT diagA[dA] AND NOT diagB[dB]) THEN BEGIN
 X[fila] <- col;
 colUsada[col] <- T;
 diagA[dA] <- T;
 diagB[dB] <- T;

 total <- total + ubicarReinaRapido(fila + 1, n, X, colUsada, diagA, diagB);

 X[fila] <- NULL;
 colUsada[col] <- F;
 diagA[dA] <- F;
 diagB[dB] <- F;
 END
 END

 RETURN total;
END

Problemas clásicos de backtracking

Backtracking aparece cuando hay que tomar una secuencia de decisiones bajo restricciones. La forma cambia, pero el patrón de solución parcial y poda se repite.

Familias típicas

Problema	Vector solución	Candidatos	Poda principal
N-Reinas	$X [i] = columna de la reina en fila i$	Columnas del tablero.	No misma columna ni diagonal.
Suma de subconjuntos	$X [i] \in {0, 1}$	Tomar o no tomar cada elemento.	La suma parcial no debe exceder el objetivo si todos los números son positivos.
Coloreo de grafos	$X [v] = color del v \overset{e}{ˊ} rtice v$	Colores disponibles.	Vértices adyacentes no pueden compartir color.
Sudoku	$X [i] = valor de la celda vac \overset{ı}{ˊ} a i$	Dígitos posibles.	No repetir en fila, columna ni subcuadro.
Permutaciones restringidas	$X [i] = elemento en posici \overset{o}{ˊ} n i$	Elementos no usados.	Restricciones específicas del problema.

Backtracking vs fuerza bruta vs voraces

Backtracking está entre dos extremos: no es tan ciego como fuerza bruta, pero tampoco se compromete irrevocablemente como un voraz.

Comparación de técnicas

Criterio	Fuerza bruta	Backtracking	Voraz
Construcción	Genera todo.	Construye y poda.	Elige localmente.
Retroceso	No aplica.	Sí.	No.
Poda temprana	No.	Sí, por factibilidad.	No explora alternativas descartadas.
Garantía	Completa si enumera todo.	Completa si la poda es correcta.	Solo si se demuestra propiedad voraz.
Costo típico	Combinatorio completo.	Combinatorio con poda.	Usualmente polinómico.

Selección de técnica

Renderizando diagrama...

Errores típicos

Errores frecuentes en backtracking

Error	Por qué está mal	Corrección
No deshacer la decisión	El siguiente candidato hereda un estado que no le corresponde.	Después de la llamada recursiva, restaurar la posición o estructura modificada.
Validar solo al final	Eso convierte el algoritmo en fuerza bruta.	Validar cada solución parcial antes de avanzar.
Podar una rama que sí podía llegar a solución	La poda incorrecta vuelve incompleto el algoritmo.	La poda debe ser una condición necesaria de invalidez, no una intuición.
Confundir backtracking con voraz	El voraz no reconsidera; backtracking sí retrocede.	Si hay deshacer y explorar alternativas, es backtracking.
Analizar solo el camino exitoso	El costo incluye candidatos fallidos y ramas podadas visitadas.	Analizar nodos visitados del árbol completo, no solo la solución final.
Decir que la poda hace el algoritmo polinómico	La poda mejora casos reales, pero no necesariamente cambia el peor caso.	Justificar formalmente cualquier mejora de cota.

Resumen operativo

Receta mínima

Define la solución como una n-tupla.
Define qué representa cada posición de la tupla.
Define los candidatos de cada nivel.
Define el predicado de factibilidad.
Define cuándo una solución está completa.
Explora en profundidad usando recursión.
Antes de avanzar, valida la solución parcial.
Después de volver de la recursión, deshaz la decisión.
Analiza el costo como nodos visitados por costo de validación.

Modelos clave

Solución como tupla

Cada posición del vector representa una decisión.

X = (x_{0}, x_{1}, \dots, x_{n - 1}), x_{i} \in S_{i}

Solución parcial

La solución todavía no está completa, pero ya puede validarse parcialmente.

X_{k} = (x_{0}, x_{1}, \dots, x_{k}, ?, \dots, ?)

Poda por factibilidad

Si el predicado es falso, la rama se corta.

B_{k} (X_{k - 1}, v) = {verdadero, falso, X_{k - 1} \cup {x_{k} = v} respeta restricciones viola alguna restricci \overset{o}{ˊ} n

Costo general

El costo depende de cuántos nodos se visitan en cada nivel y cuánto cuesta validarlos.

T (n) = k = 0 \sum d N_{k} \cdot C_{v a l i d a r} (k)