Backtracking: N reinas, subconjuntos, permutaciones

De qué trata este capítulo

Hay problemas que no se pueden acomodar en una tabla ni resolver eligiendo lo mejor localmente: tienes que buscar en el espacio de posibilidades. El backtracking es la forma disciplinada de hacerlo: construyes una solución candidata una decisión a la vez y, en cuanto un candidato parcial ya no puede llevar a una respuesta válida, lo abandonas y te regresas. Es una búsqueda en profundidad sobre un árbol de decisiones con un agregado decisivo — la poda — que le permite saltarse regiones astronómicamente grandes del espacio sin siquiera mirarlas. Este capítulo construye el paradigma sobre el problema de las N reinas (colocar N reinas sin que ninguna ataque a otra), donde la fuerza bruta probaría más candidatos que átomos hay en un cuarto, mientras que el backtracking resuelve un tablero de 12×12 examinando una fracción de un porcentaje del espacio. También construye las otras dos rutinas canónicas de backtracking — generar todos los subconjuntos y todas las permutaciones — y muestra lo que rinde la poda: con N=12, el backtracking examina casi un millón de veces menos candidatos que la fuerza bruta.

Un poco de historia

La palabra "backtracking" la acuñó D. H. Lehmer en los años cincuenta, pero la técnica es mucho más vieja: es la formalización de cómo cualquiera resuelve un laberinto o un rompecabezas por prueba y error, de manera sistemática. El problema de las N reinas se remonta a 1848, cuando el compositor de ajedrez Max Bezzel planteó el acertijo de las ocho reinas; Gauss lo estudió y terminó siendo un caso de prueba favorito para algoritmos de búsqueda porque su estructura es clarísima. El tratamiento teórico del backtracking maduró en los sesenta y setenta: el artículo de Golomb y Baumert de 1965 dio un marco general, y el trabajo posterior de Knuth (incluida su técnica "Dancing Links" para problemas de cobertura exacta como el Sudoku) lo refinó hasta volverlo un arte. Su importancia está en que es la herramienta de propósito general para la satisfacción de restricciones — problemas definidos como "encuentra una asignación que cumpla estas reglas" — que aparecen en todos lados, desde la planeación de horarios hasta el diseño de circuitos y la planificación en IA. Los solvers SAT modernos y los sistemas de programación con restricciones son, en el fondo, backtracking muy sofisticado con poda aprendida; el humilde prueba-recursa-deshaz de este capítulo es su antepasado.

La intuición

Las N reinas hacen que el paradigma se vea clarísimo. Tienes que colocar N reinas en un tablero de N×N sin que ninguna ataque a otra: nunca dos en la misma fila, columna o diagonal. La idea de fuerza bruta es probar todas las formas de colocar N reinas y revisar cada una en busca de conflictos, pero eso es imposible: incluso restringiendo a una reina por columna, son Nᴺ arreglos completos que generar y probar. La clave del backtracking es revisar mientras construyes. Coloca una reina en la columna 0. Pásate a la columna 1 y prueba cada fila; sáltate cualquier fila atacada por la reina ya colocada (esa es la poda) y coloca la reina en la primera fila segura. Pásate a la columna 2 y haz lo mismo. Si en algún momento llegas a una columna donde todas las filas están atacadas, la colocación parcial es un callejón sin salida — ninguna forma de completarla va a funcionar — así que te regresas a la columna anterior, quitas su reina y pruebas ahí la siguiente fila segura. Sigue hasta llenar las N columnas (una solución) o hasta agotar todas las posibilidades (no hay solución).

Lo poderoso es que un conflicto detectado temprano mata un subárbol entero. Si colocar una reina en la columna 3 genera conflicto, el backtracking nunca explora ninguno de los arreglos de las columnas 4 a N que habrían seguido: los poda todos de un jalón, sin examinarlos. La fuerza bruta habría generado y probado cada uno. La forma del código es la esencia del paradigma y se repite en todos lados: prueba una opción, recursa para tomar la siguiente decisión y deshaz la opción si la recursión falla. Ese prueba-recursa-deshaz es exactamente cómo generas todos los subconjuntos (para cada elemento, prueba incluirlo, recursa, luego prueba excluirlo) y todas las permutaciones (para cada posición, prueba cada elemento sin usar, recursa, luego regrésalo). El backtracking es búsqueda en profundidad donde el árbol es el espacio de soluciones parciales y la poda corta las ramas que no van a dar fruto.

Complejidad: cómo escala

El backtracking, en el peor caso, sigue siendo exponencial: es búsqueda, y algunos problemas (como las N reinas para N grande, o SAT) no tienen ningún algoritmo polinomial conocido. Pero su costo práctico está muy por debajo del espacio de fuerza bruta porque la poda elimina la mayor parte. El enfrentamiento mide justo eso: la cantidad de nodos que el backtracking realmente examina contra el tamaño del espacio ingenuo de fuerza bruta (Nᴺ), conforme crece N:

Las dos líneas suben — esto sigue siendo búsqueda exponencial — pero se separan muchísimo. En un tablero de 12×12, el espacio de fuerza bruta es de unos 8.9 billones de arreglos con una reina por columna; el backtracking examinó alrededor de 10 millones de nodos para enumerar todas las soluciones: unas 880,000 veces menos. Esa brecha es pura poda: cada vez que una colocación parcial genera conflicto, el backtracking descarta el subárbol completo de las formas de completarla que la fuerza bruta habría generado y probado. La lección no es que el backtracking vuelva fácil el problema — las N reinas son genuinamente difíciles, y la línea del backtracking sigue siendo exponencial — sino que la poda recupera la fuerza bruta solo donde el problema lo exige, explorando la fracción del espacio que no es obviamente inútil. Para muchos problemas de restricciones prácticos, esa fracción es lo bastante chica como para volver tratable una búsqueda intratable.

En qué es bueno y en qué no

El backtracking es la herramienta correcta para problemas de satisfacción de restricciones y de generación combinatoria: encontrar una asignación que cumpla un conjunto de reglas, o enumerar todas las configuraciones válidas. Resuelve rompecabezas y juegos (N reinas, Sudoku, crucigramas, solitario de fichas), genera objetos combinatorios (todos los subconjuntos, permutaciones, combinaciones, paréntesis válidos), mueve parsers y motores de expresiones regulares (que se regresan entre coincidencias alternativas) y está debajo de la planificación y la programación de horarios en IA. Es el enfoque natural siempre que la solución se construye a partir de una secuencia de decisiones y puedes probar soluciones parciales, porque esa capacidad de probar es lo que habilita la poda, y la poda es lo que hace que el backtracking le gane a la fuerza bruta. Cuando puedes podar temprano y seguido, un espacio exponencial se vuelve buscable.

Donde batalla es en problemas con poda débil o con cantidades enormes de soluciones. Si los candidatos parciales no se pueden rechazar hasta que están casi completos, el backtracking degenera hacia la fuerza bruta. Si el problema tiene subproblemas traslapados (el mismo estado parcial alcanzado por muchos caminos), el backtracking los vuelve a explorar: ese es territorio de la programación dinámica, y a veces las dos se combinan (backtracking memoizado). Y el backtracking encuentra una solución o todas las soluciones, pero no da ninguna garantía de optimalidad en problemas de optimización sin maquinaria extra (branch-and-bound agrega cotas para podar ramas subóptimas). Para problemas donde aplica un enfoque greedy o de DP, esos son mucho más rápidos; el backtracking es para la búsqueda genuinamente combinatoria que se les resiste. Y aun así es exponencial en el peor caso: vuelve problemas difíciles tratables en la práctica, no polinomiales.

Los datos, o las entradas

El enfrentamiento cuenta los nodos que el backtracking examina para enumerar todas las soluciones de las N reinas contra el espacio de fuerza bruta Nᴺ, para tableros de hasta 12×12: la razón de poda. La corrección se verifica en serio: la colocación del solver tiene que estar genuinamente libre de conflictos para cada N, el conteo de todas las soluciones tiene que coincidir con la secuencia conocida de las N reinas (1, 0, 0, 2, 10, 4, 40, 92, 352, 724 para N = 1…10), y los generadores de subconjuntos y permutaciones tienen que coincidir exactamente con itertools de Python. La animación corre el backtracking en un tablero de 5×5, mostrando cada intento: una reina colocada en una casilla segura (verde), una casilla podada por estar atacada (rojo) y un backtrack cuando a una columna se le acaban las filas seguras (deshacer y retroceder).

Constrúyelo, una función a la vez

N reinas: coloca una reina por columna, poda las casillas atacadas, deshaz al llegar a un callejón sin salida:

def solve_nqueens(n, trace=None):
    """Place N non-attacking queens, one per column, by backtracking. Track occupied rows and both
    diagonals (c-r and c+r are constant along the two diagonal directions) so conflict checks are
    O(1). At each column try every row; skip attacked squares (prune), place on a free one and
    recurse; if the recursion fails, UNDO the placement and try the next row. Returns (first
    solution or None, nodes_examined). `trace` optionally records every place/attack/backtrack step
    for the animation."""
    cols, diag1, diag2 = set(), set(), set()
    placement = [-1] * n
    nodes = [0]

    def place(c):
        if c == n:                               # all columns filled → a complete solution
            return True
        for r in range(n):
            nodes[0] += 1
            if r in cols or (c - r) in diag1 or (c + r) in diag2:
                if trace is not None:
                    trace.append((c, r, "attack", placement[:]))
                continue                          # pruned: this square is attacked, skip it
            placement[c] = r
            cols.add(r); diag1.add(c - r); diag2.add(c + r)
            if trace is not None:
                trace.append((c, r, "place", placement[:]))
            if place(c + 1):                      # recurse into the next column
                return True
            placement[c] = -1                     # undo — backtrack and try the next row
            cols.discard(r); diag1.discard(c - r); diag2.discard(c + r)
            if trace is not None:
                trace.append((c, r, "backtrack", placement[:]))
        return False

    found = place(0)
    return (placement[:] if found else None), nodes[0]


def count_nqueens(n):
    """Count ALL solutions (and nodes examined) — used to compare backtracking's search size against
    the brute-force space. Same algorithm, but never stops at the first solution."""
    cols, diag1, diag2 = set(), set(), set()
    total, nodes = [0], [0]

    def place(c):
        if c == n:
            total[0] += 1
            return
        for r in range(n):
            nodes[0] += 1
            if r in cols or (c - r) in diag1 or (c + r) in diag2:
                continue
            cols.add(r); diag1.add(c - r); diag2.add(c + r)
            place(c + 1)
            cols.discard(r); diag1.discard(c - r); diag2.discard(c + r)

    place(0)
    return total[0], nodes[0]

Los dos generadores canónicos — subconjuntos y permutaciones, ambos puro prueba-recursa-deshaz:

def subsets(items):
    """All subsets, by backtracking: at each element choose to include it or not, recursing on the
    rest. 2^n subsets, built incrementally with a try-recurse-undo on the 'current' list."""
    out, cur = [], []

    def choose(i):
        if i == len(items):
            out.append(cur[:])
            return
        choose(i + 1)                            # branch 1: skip items[i]
        cur.append(items[i])                     # branch 2: include items[i]
        choose(i + 1)
        cur.pop()                                # undo

    choose(0)
    return out


def permutations(items):
    """All permutations, by backtracking: pick each unused element for the next position, recurse,
    then unpick it. n! permutations."""
    out, cur, used = [], [], [False] * len(items)

    def build():
        if len(cur) == len(items):
            out.append(cur[:])
            return
        for i in range(len(items)):
            if used[i]:
                continue
            used[i] = True
            cur.append(items[i])
            build()
            cur.pop()                            # undo
            used[i] = False

    build()
    return out

Míralo funcionar

Aquí está el backtracking resolviendo el acertijo de las 5 reinas, colocando una reina por columna de izquierda a derecha. Una reina (♛, verde) va en la primera fila segura de cada columna. Cuando una casilla candidata está atacada por una reina ya colocada — misma fila o diagonal — parpadea en rojo y queda podada, descartada sin más. Y cuando a una columna se le acaban por completo las filas seguras, observa al algoritmo hacer backtrack: la casilla naranja marca una reina que se está quitando mientras la búsqueda retrocede a la columna anterior para probar una fila más arriba. Sigue la marcha de las reinas por el tablero, regresándose de vez en cuando cuando se meten a un callejón sin salida, hasta que las cinco columnas tengan una reina y ninguna ataque a otra. Cada casilla roja es una rama entera de posibilidades descartada de un vistazo; cada backtrack es la búsqueda admitiendo un callejón sin salida y volviendo a intentar:

El código completo

La pestaña desde cero es las N reinas (resolver y contar) más los generadores de subconjuntos y permutaciones; la pestaña de librería es el tamaño del espacio de fuerza bruta (lo que la poda encoge) y las referencias de itertools que los generadores reproducen. Cambia entre las dos: itertools.permutations es lo que usarías en la práctica, pero ver la versión con backtracking muestra que es el mismo prueba-recursa-deshaz, y que la versión con restricciones (N reinas) es ese esqueleto más una prueba de poda.

"""Backtracking — search the space of possibilities by building a candidate one choice at a time,
and ABANDONING it the moment it can't lead to a solution. It's depth-first search over a tree of
choices with one crucial addition: pruning. Instead of generating every complete candidate and
testing it (brute force), backtracking checks partial candidates as it builds them and cuts off
entire branches early, so it explores a tiny fraction of the full space.

The showcase is the N-Queens puzzle: place N queens on an N×N board so none attacks another (no two
share a row, column, or diagonal). Brute force would try every way to drop N queens on the board and
check each — astronomically many. Backtracking places one queen per column, and the instant a
partial placement has a conflict it stops extending that branch and backs up. The same shape solves
Sudoku, generates all subsets and permutations, and searches any space of incremental choices: try a
choice, recurse, and undo it if it fails ("try — recurse — undo"). Pruning is what turns an
intractable search into a fast one.
"""


# region: nqueens
def solve_nqueens(n, trace=None):
    """Place N non-attacking queens, one per column, by backtracking. Track occupied rows and both
    diagonals (c-r and c+r are constant along the two diagonal directions) so conflict checks are
    O(1). At each column try every row; skip attacked squares (prune), place on a free one and
    recurse; if the recursion fails, UNDO the placement and try the next row. Returns (first
    solution or None, nodes_examined). `trace` optionally records every place/attack/backtrack step
    for the animation."""
    cols, diag1, diag2 = set(), set(), set()
    placement = [-1] * n
    nodes = [0]

    def place(c):
        if c == n:                               # all columns filled → a complete solution
            return True
        for r in range(n):
            nodes[0] += 1
            if r in cols or (c - r) in diag1 or (c + r) in diag2:
                if trace is not None:
                    trace.append((c, r, "attack", placement[:]))
                continue                          # pruned: this square is attacked, skip it
            placement[c] = r
            cols.add(r); diag1.add(c - r); diag2.add(c + r)
            if trace is not None:
                trace.append((c, r, "place", placement[:]))
            if place(c + 1):                      # recurse into the next column
                return True
            placement[c] = -1                     # undo — backtrack and try the next row
            cols.discard(r); diag1.discard(c - r); diag2.discard(c + r)
            if trace is not None:
                trace.append((c, r, "backtrack", placement[:]))
        return False

    found = place(0)
    return (placement[:] if found else None), nodes[0]


def count_nqueens(n):
    """Count ALL solutions (and nodes examined) — used to compare backtracking's search size against
    the brute-force space. Same algorithm, but never stops at the first solution."""
    cols, diag1, diag2 = set(), set(), set()
    total, nodes = [0], [0]

    def place(c):
        if c == n:
            total[0] += 1
            return
        for r in range(n):
            nodes[0] += 1
            if r in cols or (c - r) in diag1 or (c + r) in diag2:
                continue
            cols.add(r); diag1.add(c - r); diag2.add(c + r)
            place(c + 1)
            cols.discard(r); diag1.discard(c - r); diag2.discard(c + r)

    place(0)
    return total[0], nodes[0]
# endregion


# region: subsets_perms
def subsets(items):
    """All subsets, by backtracking: at each element choose to include it or not, recursing on the
    rest. 2^n subsets, built incrementally with a try-recurse-undo on the 'current' list."""
    out, cur = [], []

    def choose(i):
        if i == len(items):
            out.append(cur[:])
            return
        choose(i + 1)                            # branch 1: skip items[i]
        cur.append(items[i])                     # branch 2: include items[i]
        choose(i + 1)
        cur.pop()                                # undo

    choose(0)
    return out


def permutations(items):
    """All permutations, by backtracking: pick each unused element for the next position, recurse,
    then unpick it. n! permutations."""
    out, cur, used = [], [], [False] * len(items)

    def build():
        if len(cur) == len(items):
            out.append(cur[:])
            return
        for i in range(len(items)):
            if used[i]:
                continue
            used[i] = True
            cur.append(items[i])
            build()
            cur.pop()                            # undo
            used[i] = False

    build()
    return out
# endregion

"""The contrast and the reference. Two things:

- `brute_force_nqueens_space` reports the size of the naive search space — every way to place one
  queen per column with NO pruning, which is n^n complete candidates to generate and test. It's the
  baseline backtracking's pruning shrinks; we compute its size rather than actually enumerate it
  (n^n is astronomically large).
- Python's `itertools` provides the standard-library generators that backtracking reproduces:
  `itertools.permutations`, `itertools.combinations`, `product`. They're the correctness reference
  for the subset/permutation builders (and what you'd actually use for those).

    from itertools import permutations, combinations
    list(permutations(items))                 # all n! orderings
    [c for r in range(len(items)+1) for c in combinations(items, r)]   # all subsets
"""
from itertools import combinations, permutations as iperms


# region: bruteforce
def brute_force_nqueens_space(n):
    """The number of complete candidates a no-pruning brute force would generate: one row choice per
    column, independently, = n^n. Backtracking examines far fewer NODES because it prunes attacked
    partial placements before completing them."""
    return n ** n
# endregion


# region: references
def all_permutations(items):
    """itertools reference for the permutation builder."""
    return [list(p) for p in iperms(items)]


def all_subsets(items):
    """itertools reference for the subset builder (every size of combination)."""
    out = []
    for r in range(len(items) + 1):
        out.extend(list(c) for c in combinations(items, r))
    return out
# endregion

Desde cero vs librería

La lección del backtracking es que la poda es el algoritmo. El esqueleto — prueba, recursa, deshaz — es trivial e idéntico entre las N reinas, los subconjuntos y las permutaciones; lo que vuelve tratables las N reinas donde la fuerza bruta es imposible es esa línea extra que rechaza una casilla atacada antes de recursar. La brecha de 880,000 veces del enfrentamiento es enteramente esa línea. Esto replantea cómo encarar una búsqueda combinatoria: no preguntes "cómo genero todos los candidatos", pregunta "qué tan temprano puedo detectar que un candidato parcial está condenado", porque cada rechazo temprano poda un subárbol exponencial. Es la misma idea que escala hasta los solvers SAT y de programación con restricciones industriales: son el esqueleto de este capítulo con poda progresivamente más inteligente (propagación, aprendizaje de cláusulas) y ordenamiento de variables. Y conecta con los otros paradigmas: el backtracking es la recursión de divide y vencerás sin la independencia (las ramas comparten el estado parcial que va creciendo), y se encuentra con la programación dinámica cuando los estados parciales se traslapan (backtracking memoizado). Para pura generación usarías itertools; construir tú mismo las N reinas es lo que convierte "la poda vuelve tratable una búsqueda intratable" en un número que mediste, no en una afirmación.

Dónde te lo vas a encontrar de verdad

El backtracking corre dondequiera que se busque una solución entre posibilidades combinatorias. Los solvers de restricciones y los solvers SAT — detrás de la verificación de hardware, el model checking de software, la programación de horarios y la planificación automatizada — son backtracking con poda sofisticada. Los solvers de Sudoku, crucigramas y rompecabezas son aplicaciones directas. Los motores de expresiones regulares (los de tipo backtracking, como el de Perl y el re de Python) hacen match probando alternativas y regresándose, que es también por lo que las regex patológicas pueden explotar exponencialmente. Los parsers de gramáticas ambiguas se regresan entre alternativas de parseo. Los compiladores lo usan en la asignación de registros y la programación de instrucciones. La generación combinatoria — enumerar permutaciones, combinaciones, particiones, configuraciones válidas — es backtracking, igual que buena parte de la IA que juega (minimax es una búsqueda con backtracking sobre árboles de juego). Los demostradores de teoremas, la inferencia de tipos y la síntesis de programas buscan con él. En cualquier lugar donde la tarea sea "encuentra (o enumera) asignaciones que satisfagan restricciones", el backtracking, más una buena poda, es el motor.

Puntos clave

El backtracking busca en un espacio de posibilidades construyendo candidatos una decisión a la vez y podando — abandonando un candidato parcial en cuanto deja de poder llevar a una solución — un "prueba, recursa, deshaz" en profundidad sobre el árbol de decisiones. La poda es lo que lo distingue de la fuerza bruta y lo que lo hace poderoso: un conflicto detectado temprano descarta un subárbol exponencial entero sin examinarlo, lo que permite al backtracking resolver las N reinas examinando 880,000× menos candidatos que la fuerza bruta con N=12. Sigue siendo exponencial en el peor caso — vuelve tratable en la práctica una búsqueda difícil, no polinomial — y su velocidad vive por completo en qué tan temprano y qué tan astutamente puedes podar, la dimensión de diseño que lo escala hasta los solvers modernos de restricciones y SAT.

Al nivel de paradigmas le quedan dos capítulos, ambos sobre otro tipo de astucia: no buscar en un espacio, sino explotar la estructura para evitar recalcular. Las técnicas de dos punteros y ventana deslizante (la siguiente) convierten muchos recorridos O(n²) en pasadas únicas O(n) manteniendo el estado de una ventana móvil de forma incremental, con el mismo espíritu de "reutiliza lo que ya calculaste" del rolling hash. Después, la búsqueda binaria sobre la respuesta aplica la búsqueda binaria no a un array sino al espacio de respuestas posibles, resolviendo problemas de optimización preguntando repetidamente una cuestión de factibilidad de sí o no.