Backtracking (vuelta atrás) explicado: cómo funciona, código y ejemplos

Qué problema resuelve el backtracking

Algunos problemas piden todas las disposiciones que cumplen un conjunto de reglas, o una cualquiera de ellas: colocar 8 reinas de modo que ninguna ataque a otra, rellenar una cuadrícula de Sudoku, listar todos los subconjuntos de un conjunto que suman un objetivo, encontrar todas las formas de dividir una cadena en palabras de un diccionario. No hay una fórmula ingeniosa; hay que buscar. Probar a ciegas todas las combinaciones completas es demasiado lento, pero la mayoría de las combinaciones parciales ya son inválidas tras unas pocas elecciones.

El backtracking comprueba las reglas después de cada elección. Cuando una solución parcial rompe una regla, abandona de inmediato toda esa rama del árbol de búsqueda y vuelve atrás para probar la siguiente opción.

La idea en palabras sencillas

1. Si la solución parcial actual está completa, regístrala.
2. En caso contrario, para cada posible elección siguiente: si la elección está permitida, hazla (elegir).
3. Recurre para extender más la solución (explorar).
4. Deshaz la elección, para que la siguiente opción parta del mismo estado (deshacer).

El espacio de búsqueda es un árbol: la raíz es la solución vacía, cada nivel añade una elección y las hojas son candidatos completos. El backtracking es una búsqueda en profundidad sobre este árbol, y podar significa cortar los subárboles que no pueden contener una solución.

Ejemplo resuelto: 4 reinas

Coloca 4 reinas en un tablero de 4 × 4, una por fila, de modo que no haya dos en la misma columna ni en la misma diagonal. Las columnas se numeran de 0 a 3.

Si se continúa la búsqueda, aparece la única otra solución, 2, 0, 3, 1, que es la imagen especular de la primera.

Implementación en Python

Mantén conjuntos de columnas y diagonales usadas para que cada comprobación de seguridad sea O(1). En una diagonal row - col es constante, y en la otra lo es row + col.

def solve_n_queens(n):
    solutions, cols = [], []
    used_cols, diag1, diag2 = set(), set(), set()

    def place(row):
        if row == n:
            solutions.append(cols.copy())   # copy, not the live list
            return
        for col in range(n):
            if col in used_cols or row - col in diag1 or row + col in diag2:
                continue                    # prune: square is attacked
            cols.append(col)                # choose
            used_cols.add(col); diag1.add(row - col); diag2.add(row + col)
            place(row + 1)                  # explore
            cols.pop()                      # unchoose
            used_cols.remove(col); diag1.remove(row - col); diag2.remove(row + col)

    place(0)
    return solutions

print(solve_n_queens(4))       # [[1, 3, 0, 2], [2, 0, 3, 1]]
print(len(solve_n_queens(8)))  # 92

La misma plantilla genera todos los subconjuntos y todas las permutaciones:

def subsets(items):
    result, current = [], []

    def go(i):
        if i == len(items):
            result.append(current.copy())
            return
        current.append(items[i]); go(i + 1); current.pop()   # take items[i]
        go(i + 1)                                            # skip items[i]

    go(0)
    return result

def permutations(items):
    result, current, used = [], [], [False] * len(items)

    def go():
        if len(current) == len(items):
            result.append(current.copy())
            return
        for i, x in enumerate(items):
            if not used[i]:
                used[i] = True; current.append(x)
                go()
                used[i] = False; current.pop()

    go()
    return result

print(subsets([1, 2, 3]))
# [[1, 2, 3], [1, 2], [1, 3], [1], [2, 3], [2], [3], []]
print(permutations([1, 2, 3]))
# [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]

Para subconjuntos y permutaciones simples en código real, itertools.combinations e itertools.permutations son más rápidas. Escribe tu propio backtracking cuando necesites podar con reglas específicas del problema.

Complejidad temporal y espacial

El backtracking no puede superar el tamaño de la salida: si debes listar n! permutaciones, necesitas al menos n! pasos. La poda solo ayuda saltándose ramas que no producen nada.

Variantes y errores comunes

• Olvidar deshacer: si el estado no se restaura después de la llamada recursiva, las ramas posteriores ven elecciones obsoletas.
• Añadir la lista viva: result.append(current) guarda una referencia que cambia después; añade current.copy().
• Duplicados en la entrada: ordena los elementos y omite un elemento igual al anterior a la misma profundidad para evitar subconjuntos o permutaciones duplicados.
• Parar en la primera solución: devuelve True desde la recursión y detén los bucles cuando baste una solución, como en un resolutor de Sudoku.
• Mejor ordenación: prueba primero la elección más restringida (en Sudoku, la celda vacía con menos candidatos). Esto suele reducir el árbol de forma drástica.

Cuándo usarlo y usos en el mundo real

• Satisfacción de restricciones: Sudoku, crucigramas, coloreado de mapas, horarios y planificación de exámenes.
• Los resolutores SAT y los motores lógicos al estilo de Prolog se basan en la búsqueda con backtracking y una poda intensa.
• Los motores de expresiones regulares de muchos lenguajes, incluido re de Python, usan backtracking; los patrones mal escritos pueden retroceder de forma exponencial ("catastrophic backtracking").
• Problemas de entrevista: subconjuntos, permutaciones, suma de combinaciones, N reinas, búsqueda de palabras en una cuadrícula, partición de palíndromos, generar paréntesis, combinaciones de letras de un número de teléfono.