Backtracking es recursion con arrepentimiento. Tomas una decision, exploras a fondo lo que se abre a partir de ella, y si no funciona deshaces la decision y pruebas la siguiente.
Ese "deshacer" es la linea que todo el mundo olvida, y es la que hace que el algoritmo sea correcto.
static void explorar(Estado e) {
if (esSolucion(e)) { registrar(e); return; }
for (Opcion op : opciones(e)) {
if (!esValida(op, e)) continue;
aplicar(op, e); // 1. ELEGIR
explorar(e); // 2. EXPLORAR
deshacer(op, e); // 3. DESHACER
}
}
Este esqueleto resuelve N-reinas, sudoku, laberintos, permutaciones y subconjuntos. Cambia lo que pones en cada hueco.
La poda
Sin esValida() el algoritmo probaria todas las combinaciones posibles. Con esa comprobacion cortas ramas enteras antes de bajar por ellas. En N-reinas con n=8, la poda reduce el espacio de busqueda de 16 millones de posiciones a unas 15.000 exploraciones.
Podar temprano vale mas que optimizar el codigo de adentro.
Deshacer, o no deshacer
Si tu estado es mutable (un arreglo, una lista, un tablero), tienes que deshacer. Si en cada llamada creas un objeto nuevo, no hace falta, pero pagas en memoria. Java tiende a lo primero por eficiencia, y por eso el bug clasico de backtracking es una lista que sale llena de basura de otras ramas.
Ejecuta y observa
Cambia los parametros, dale a Reproducir, y usa las flechas para avanzar
paso a paso. La pila crece hacia arriba: el marco de arriba es el que se
esta ejecutando ahora mismo.
Errores que vas a cometer
Lee el codigo, decide que esta mal, y despues abre la correccion.
Olvidar el deshacer
static void subconjuntos(int[] a, int i, List<Integer> actual) {
if (i == a.length) { System.out.println(actual); return; }
subconjuntos(a, i + 1, actual);
actual.add(a[i]);
subconjuntos(a, i + 1, actual);
// falta: actual.remove(actual.size() - 1);
}
La lista es compartida entre todas las ramas. Sin quitar el elemento al volver, cada rama contamina a la siguiente y salen subconjuntos que no existen.
if (esSolucion()) {
resultados.add(actual); // guarda la MISMA lista
}
Al deshacer, esa lista se vacia. Terminas con una lista de listas vacias, todas apuntando al mismo objeto.
if (esSolucion()) {
resultados.add(new ArrayList<>(actual)); // copia
}
Comprueba lo que entendiste
Necesitas el 70% para dar el nivel por visto. Responde sin devolverte a la teoria:
si fallas, la explicacion te dice exactamente donde estaba el hueco.