Backtracking y poda

Hay problemas donde no se conoce nada mejor que probar. Poner ocho reinas en un tablero, completar un sudoku, repartir tareas entre máquinas. La diferencia entre probar bien y probar mal no es el orden de complejidad: es cuántas ramas se descartan antes de recorrerlas.

Decidir, avanzar y deshacer

Backtracking construye la solución de a una decisión por vez. Si la solución parcial todavía puede completarse, avanza; si no, deshace la última decisión y prueba la siguiente opción. De ahí el nombre: volver sobre los pasos.

Lo que recorre es un árbol de decisiones, en profundidad. La recursión hace el trabajo: al volver de la llamada, se deshace el cambio y se sigue con la alternativa. Ese “deshacer” es el error más frecuente cuando el estado es compartido en vez de copiado.

La poda no es una optimización: es el algoritmo

La poda es el chequeo que corta una rama antes de tiempo: si ninguna extensión de esta solución parcial puede ser válida, no hay razón para bajar.

En las ocho reinas, verificar el ataque al colocar cada reina en vez de al final reduce el espacio de más de cuatro mil millones de tableros a unos pocos miles de nodos. El algoritmo es el mismo; lo que cambió es cuándo se detecta el fracaso.

El orden de las variables, la palanca menos obvia

Hay una segunda palanca, menos obvia: el orden. Atacar primero la variable con menos opciones disponibles hace que los conflictos aparezcan arriba del árbol, donde podar elimina más.

Es la heurística que usan los resolvedores de sudoku: llenar antes la celda con menos candidatos. No cambia el peor caso teórico, pero en la práctica es la diferencia entre segundos y horas.

Mantener el estado en vez de recalcularlo

La eficiencia depende también de cómo se representa el estado. Recalcular desde cero si una posición es válida cuesta caro cuando se hace en cada nodo.

Conviene mantener estructuras incrementales —columnas y diagonales ocupadas, candidatos por celda— que se actualizan al decidir y se revierten al volver. El costo por nodo baja a constante, y como los nodos son millones, ahí está la diferencia real.

Sigue siendo exhaustivo

Backtracking sigue siendo búsqueda exhaustiva: garantiza encontrar todas las soluciones, o probar que no hay ninguna. La complejidad en el peor caso es exponencial y ninguna poda la cambia.

Lo que se gana es que el peor caso casi nunca ocurre: las restricciones reales eliminan la mayoría del espacio. Por eso es la técnica de referencia para problemas de satisfacción de restricciones, donde no hay estructura que permita algo mejor.

Cuándo conviene y cuándo no

Conviene cuando el espacio es discreto, hay restricciones que se pueden verificar sobre soluciones parciales y el tamaño de la instancia es moderado. Si las restricciones sólo se pueden verificar al final, no hay poda posible y es fuerza bruta con más código.

Cuando además hay una función a optimizar y no sólo restricciones a cumplir, la poda puede usar cotas sobre el valor alcanzable. Esa variante tiene nombre propio: branch and bound.

El esqueleto, que es siempre el mismo

Todo backtracking tiene la misma forma: elegir, recursar, deshacer.

const solveQueens = (size: number): number[][] => {
  const solutions: number[][] = [];
  const columns: number[] = []; // columns[fila] = columna elegida

  const isSafe = (row: number, column: number): boolean =>
    columns.every((placed, placedRow) =>
      placed !== column && Math.abs(placed - column) !== row - placedRow,
    );

  const place = (row: number): void => {
    if (row === size) {
      solutions.push([...columns]); // copia: columns se sigue modificando
      return;
    }

    for (let column = 0; column < size; column += 1) {
      if (!isSafe(row, column)) continue; // acá está la poda

      columns.push(column);   // elegir
      place(row + 1);         // recursar
      columns.pop();          // deshacer
    }
  };

  place(0);
  return solutions;
};

Las tres líneas del final del ciclo son el patrón entero. La del medio es la recursión; las otras dos mantienen el estado consistente, y olvidarse de la tercera es el error más común: sin el pop, el estado de una rama contamina a la siguiente.

Cuándo backtracking y cuándo no

Cierre

Backtracking es recorrer el árbol de decisiones en profundidad deshaciendo al volver. Su rendimiento real no sale del esquema sino de tres cosas: podar temprano, elegir bien el orden de las decisiones y mantener el estado de forma incremental.