Backtracking

Las dos últimas semanas fueron de recursión. Primero, una función que se llama una vez y resuelve un problema más pequeño. Después, la recursión en árbol: una función que se llama varias veces, como Fibonacci o flood fill. En flood fill, una celda visitada queda marcada para siempre, porque nunca hace falta volver a pintarla.

Hoy aparece un problema de otra forma: hay que tomar una serie de decisiones, y no se sabe cuál es la buena hasta haber tomado las siguientes. Un sudoku es así. Ponen un 5 en una celda, llenan otras diez, y recién ahí descubren que una celda ya no admite ningún dígito. El 5 estaba mal. Hay que volver, borrar lo que se escribió y probar el 6.

Esa técnica se llama backtracking: probar una elección, explorar lo que sigue y, si no funciona, deshacerla para probar otra. No necesita ninguna idea nueva de C. Es la recursión en árbol de la semana pasada, con una regla de más: lo que se marca, se desmarca al volver. Esa diferencia con flood fill es el centro del capítulo.

¿Por qué no probar todo y listo? Porque “todo” suele ser demasiado. Un sudoku con 57 celdas vacías tiene 9^57 formas de llenarlas, un número de 55 cifras. En el laboratorio van a resolver ese tablero visitando menos de dos millones de nodos y, con una decisión mejor, menos de dos mil. Por eso la otra mitad del capítulo es la poda (pruning): dejar de explorar una rama que no puede funcionar, y medir cuánto se gana.

Ruta de lectura.

• Antes de clase (15 a 20 minutos, obligatoria): la introducción, Un problema de decisiones, El esquema: elegir, explorar, deshacer y Subconjuntos.
• En clase: Permutaciones, N reinas, Una solución o todas y Poda.
• Después de clase: El laboratorio, paso a paso. Luego el Resumen y los Ejercicios. Para ir más allá: los últimos ejercicios del capítulo.

Código. Los programas de este capítulo están en code/week-11. Dentro del entorno del curso, entren a esa carpeta y corran make para compilar los ejemplos y make test para comprobarlos. Los comandos de este capítulo se corren desde ahí. Los programas de errors/ tienen errores a propósito y se compilan a mano, como se muestra en cada caso.

Un problema de decisiones

Una búsqueda se puede dibujar como un árbol. Cada nodo es un estado de la búsqueda: las decisiones tomadas hasta ahí. Cada rama que sale de un nodo es una opción para la siguiente decisión. El nodo de arriba es la raíz, sin ninguna decisión tomada. Un nodo del que no sale ninguna rama es una hoja.

Tomemos un ejemplo de todos los días. Van a armar un menú, y por cada plato de la carta deciden si lo piden o no. Con tres platos, a, b y c, son tres decisiones seguidas, y este es su árbol de decisiones:

Nadie construye este dibujo en la memoria. El árbol es la forma que toman las llamadas: cada llamada recursiva es un nodo, y la pila guarda solo el camino desde la raíz hasta el nodo actual. Para ir de una hoja a la otra, las llamadas retornan hasta el punto en que queda otra opción: de ahí viene el nombre backtracking, volver sobre los pasos.

Idea clave. Un árbol enorme no gasta mucha memoria. En cualquier momento solo existen los marcos del camino actual, y hay tantos como decisiones más uno. Este árbol tiene 15 nodos, pero nunca hay más de 4 marcos a la vez. Con flood fill sobre una cuadrícula grande, la pila puede llegar muy hondo. Aquí la profundidad es el número de decisiones.

El esquema: elegir, explorar, deshacer

Todos los programas de hoy tienen la misma forma:

algoritmo buscar(estado)
    si estado está completo entonces
        procesar la solución
        devolver
    fin si
    para opcion desde 0 hasta cantidad_de_opciones - 1 hacer
        si opcion es válida en estado entonces
            aplicar opcion a estado
            buscar(estado)
            quitar opcion de estado
        fin si
    fin para
fin algoritmo

Las tres líneas del medio son toda la técnica:

1. Elegir: aplicar la opción al estado.
2. Explorar: la llamada recursiva. Por el salto de fe, supongan que recorre bien todo lo que hay debajo de esa elección.
3. Deshacer: dejar el estado exactamente como estaba antes de elegir.

Lo tercero es lo nuevo. Se necesita porque hay un solo estado, compartido por todas las llamadas: lo que se pasa es un puntero a un arreglo, no una copia. Por eso la condición de la recursión se puede decir así:

Idea clave. La promesa de buscar es: cuando retorno, el estado está como me lo dieron. Si cada llamada la cumple, quien llamó puede seguir con su siguiente opción como si nada hubiera pasado. Es un razonamiento por inducción, igual que los de la semana 9: se supone que la llamada interna cumple la promesa, y se comprueba que esta también.

Se podría evitar deshacer pasando una copia del estado a cada llamada. Funciona, y a veces es lo más simple, pero se paga una copia en cada nodo. Con un estado de 81 celdas y millones de nodos, se nota. En este curso compartimos un solo estado.

Subconjuntos

Un subconjunto de {a, b, c} se forma decidiendo, para cada elemento, si se toma o no. El árbol es el del menú. En pseudocódigo:

algoritmo subconjuntos(elementos, n, elegidos, indice)
    si indice = n entonces
        escribir los elementos marcados en elegidos
        devolver
    fin si
    elegidos[indice] ← 1
    subconjuntos(elementos, n, elegidos, indice + 1)
    elegidos[indice] ← 0
    subconjuntos(elementos, n, elegidos, indice + 1)
fin algoritmo

Aquí las opciones son siempre dos, así que no hace falta el ciclo. En C, con un contador de nodos:

static void subsets(const char *items, int *chosen, int n, int index, long *nodes) {
    (*nodes)++;
    if (index == n) {
        print_subset(items, chosen, n);
        return;
    }
    chosen[index] = 1;                               // elegir: se toma
    subsets(items, chosen, n, index + 1, nodes);     // explorar
    chosen[index] = 0;                               // deshacer: no se toma
    subsets(items, chosen, n, index + 1, nodes);     // explorar
}

Sigan los primeros pasos en papel, con chosen en tres posiciones:

$ build/subsets
{ a b c }
{ a b }
{ a c }
{ a }
{ b c }
{ b }
{ c }
{ }
nodos: 15

Salen 8 hojas: el orden de las líneas es el de las hojas del dibujo, de izquierda a derecha. Cada elemento duplica los caminos, así que con n elementos hay 2^n hojas. Los 15 nodos son 1 + 2 + 4 + 8: en general, 2^(n+1) − 1, casi el doble de las hojas.

Error común. Olvidar el chosen[index] = 0. El programa compila sin avisos, corre sin ningún informe de ASan y termina normalmente. Solo la salida dice que algo anda mal:

$ gcc -Wall -Wextra -std=c17 -g -fsanitize=address,undefined errors/subsets_no_undo.c -o build/subsets_no_undo
$ build/subsets_no_undo
{ a b c }
{ a b c }
{ a b c }
{ a b c }
{ a b c }
{ a b c }
{ a b c }
{ a b c }

El árbol se recorre completo y llegan las 8 hojas. Pero lo elegido una vez queda elegido para siempre, y todas las hojas ven el mismo estado. Ni gcc ni los sanitizers pueden ayudar aquí: ninguna regla de C se rompió, solo una promesa del programa. Por eso es importante tener un caso que puedan calcular a mano.

Permutaciones

Una permutación de abc es un orden de sus elementos. El árbol es distinto. La primera decisión es qué elemento va primero, y tiene 3 opciones. La segunda tiene 2, porque uno ya se usó. La tercera tiene 1.

                         (vacío)
             a              b              c
          ab   ac        ba   bc        ca   cb
         abc   acb      bac   bca      cab   cba

Lo nuevo es que no toda opción es válida en cada nodo. Necesitamos saber qué elementos ya se usaron, y para eso sirve otra parte del estado, el arreglo used. Ya no hay dos opciones fijas, así que vuelve el ciclo del esquema:

algoritmo permutaciones(elementos, n, actual, usados, profundidad)
    si profundidad = n entonces
        escribir actual
        devolver
    fin si
    para i desde 0 hasta n - 1 hacer
        si usados[i] = 0 entonces
            usados[i] ← 1
            actual[profundidad] ← elementos[i]
            permutaciones(elementos, n, actual, usados, profundidad + 1)
            usados[i] ← 0
        fin si
    fin para
fin algoritmo

static void permutations(const char *items, int n, char *current, int *used, int depth,
                         long *nodes) {
    (*nodes)++;
    if (depth == n) {
        current[n] = '\0';
        printf("%s\n", current);
        return;
    }
    for (int i = 0; i < n; i++) {
        if (!used[i]) {
            used[i] = 1;                                                // elegir
            current[depth] = items[i];
            permutations(items, n, current, used, depth + 1, nodes);    // explorar
            used[i] = 0;                                                // deshacer
        }
    }
}

$ build/permutations
abc
acb
bac
bca
cab
cba
nodos: 16

Sigan el inicio. Al llegar a abc, used vale 1 1 1. Al retornar, el nivel 2 deshace c y queda 1 1 0. Su ciclo termina, porque i ya vale 2, así que retorna. El nivel 1 deshace b y queda 1 0 0. Su ciclo sigue con i = 2: c está libre, así que used queda 1 0 1 y current empieza con ac. Por eso la siguiente línea es acb.

¿Por qué no se deshace current[depth]? Porque nadie lee esa posición antes de volver a escribirla: al llegar a una hoja, las posiciones de 0 a n − 1 fueron escritas por el camino actual. Solo hay que deshacer lo que una decisión posterior va a leer. El arreglo used se lee en cada nodo; current solo se lee en las hojas.

Olvidar el used[i] = 0 da una falla distinta a la de los subconjuntos. Lo usado nunca se libera, y la búsqueda termina casi enseguida:

$ gcc -Wall -Wextra -std=c17 -g -fsanitize=address,undefined errors/permutations_no_undo.c -o build/permutations_no_undo
$ build/permutations_no_undo
abc

Cuánto crecen los árboles

No hace falta suponerlo: count_trees.c recorre los dos árboles de verdad y cuenta.

$ build/count_trees
 n | subconjuntos    nodos | permutaciones      nodos
 1 |            2        3 |             1          2
 2 |            4        7 |             2          5
 3 |            8       15 |             6         16
 4 |           16       31 |            24         65
 5 |           32       63 |           120        326
 6 |           64      127 |           720       1957
 7 |          128      255 |          5040      13700
 8 |          256      511 |         40320     109601
 9 |          512     1023 |        362880     986410
10 |         1024     2047 |       3628800    9864101

Con 5 elementos, el árbol de permutaciones tiene 5! = 120 hojas, y el de subconjuntos, 2^5 = 32. El de subconjuntos duplica su tamaño con cada elemento. El de permutaciones lo multiplica por n, y por eso crece mucho más rápido. Con 20 elementos habría 2^20, un poco más de un millón de subconjuntos, y eso se recorre sin problema. Pero también habría un número de 19 cifras de permutaciones, y eso no lo recorre ninguna computadora en un tiempo razonable. Lo que se puede hacer es no recorrerlo todo: para eso es la poda.

Idea clave. Antes de escribir un backtracking, dibujen los dos primeros niveles del árbol y calculen cuántas hojas tiene. Esa cuenta les dice si el programa va a terminar antes de que acabe el semestre.

N reinas

Ahora un problema de verdad. En un tablero de N × N hay que poner N reinas de ajedrez sin que ninguna ataque a otra. Una reina ataca a lo largo de su fila, su columna y sus dos diagonales. Una solución para N = 4 es esta:

. Q . .
. . . Q
Q . . .
. . Q .

Representar el estado

La primera decisión es de diseño: qué es una elección. Si la elección es “poner una reina en cualquier casilla”, en N = 8 hay C(64, 8) = 4426165368 formas de elegir 8 casillas. Pero como dos reinas en la misma fila se atacan, hay exactamente una reina por fila. Entonces la decisión de cada nivel es “en qué columna va la reina de esta fila”, y el árbol tiene 8^8 = 16777216 hojas. Antes de escribir una línea, una buena representación ya bajó el número en más de 260 veces, y ya no hay estados con dos reinas en una fila: no se pueden representar, como las uniones etiquetadas de la semana 7.

El estado del primer programa es un arreglo: column_of_row[r] es la columna de la reina de la fila r.

Sin poda

Empecemos por el camino ingenuo: probar todas las columnas en cada fila, y revisar solo cuando el tablero está lleno. Esto es queens_no_prune.c:

static long search(int *column_of_row, int n, int row, long *nodes) {
    (*nodes)++;
    if (row == n) {
        return all_safe(column_of_row, n);
    }
    long solutions = 0;
    for (int col = 0; col < n; col++) {
        column_of_row[row] = col;
        solutions += search(column_of_row, n, row + 1, nodes);
    }
    return solutions;
}

Aquí no hay un “deshacer” escrito. column_of_row[row] se sobrescribe en la vuelta siguiente, y las filas de abajo las escribe cada rama antes de leerlas. Es la misma razón por la que current no se deshace en las permutaciones.

$ build/queens_no_prune 8
n = 8, sin poda: 92 soluciones, 19173961 nodos

Hay 92 soluciones para el tablero de 8 × 8, y costaron casi 20 millones de nodos. Es absurdo: si las dos primeras reinas ya se atacan, ninguna forma de poner las otras seis lo va a arreglar, y aun así el programa las prueba todas.

Con poda

La poda consiste en no entrar en esa rama. Se revisa si la reina puede ir ahí antes de hacer la llamada recursiva, que es justamente el “si opción es válida” del esquema. Para revisarlo rápido, el estado guarda qué columnas y qué diagonales están ocupadas:

typedef struct {
    int n;
    int column_used[MAX_N];
    int down_used[2 * MAX_N - 1];   // diagonal que baja: row - col + n - 1 es constante
    int up_used[2 * MAX_N - 1];     // diagonal que sube: row + col es constante
    long solutions;
    long nodes;
} Queens;

¿Por qué esas cuentas identifican una diagonal? Miren el tablero de 4 × 4, con row + col en cada casilla a la izquierda y row - col + 3 a la derecha:

0 1 2 3        3 2 1 0
1 2 3 4        4 3 2 1
2 3 4 5        5 4 3 2
3 4 5 6        6 5 4 3

Los números iguales forman una diagonal. A la izquierda suben hacia la derecha, y a la derecha bajan. El + 3, que es n - 1, solo está para que el índice no sea negativo. Hay 2n − 1 diagonales en cada sentido. Con esto, saber si una casilla está libre son tres lecturas, y poner o quitar una reina son tres escrituras:

static int can_place(const Queens *q, int row, int col) {
    return !q->column_used[col]
        && !q->down_used[row - col + q->n - 1]
        && !q->up_used[row + col];
}

// Pone una reina con value = 1 y la quita con value = 0.
static void mark(Queens *q, int row, int col, int value) {
    q->column_used[col] = value;
    q->down_used[row - col + q->n - 1] = value;
    q->up_used[row + col] = value;
}

static void search(Queens *q, int row) {
    q->nodes++;
    if (row == q->n) {
        q->solutions++;
        return;
    }
    for (int col = 0; col < q->n; col++) {
        if (can_place(q, row, col)) {
            mark(q, row, col, 1);       // elegir
            search(q, row + 1);         // explorar
            mark(q, row, col, 0);       // deshacer
        }
    }
}

Como mark hace las tres escrituras, elegir y deshacer son la misma función con otro valor. Así es difícil olvidarse de una parte. Fíjense en que este estado sí necesita deshacer: column_used lo leen todas las filas de abajo.

$ build/queens 8
n = 8, con poda: 92 soluciones, 2057 nodos

Las mismas 92 soluciones, con 2057 nodos en vez de 19173961: unas 9300 veces menos.

El árbol completo de 4 reinas

Con N = 4 cabe entero en la pantalla. Cada línea es una reina puesta, y la sangría es la profundidad:

$ build/queens_trace
fila 0, columna 0
  fila 1, columna 2
    sin lugar en la fila 2: se vuelve
  fila 1, columna 3
    fila 2, columna 1
      sin lugar en la fila 3: se vuelve
fila 0, columna 1
  fila 1, columna 3
    fila 2, columna 0
      fila 3, columna 2
        solución
fila 0, columna 2
  fila 1, columna 0
    fila 2, columna 3
      fila 3, columna 1
        solución
fila 0, columna 3
  fila 1, columna 0
    fila 2, columna 2
      sin lugar en la fila 3: se vuelve
  fila 1, columna 1
    sin lugar en la fila 2: se vuelve
nodos: 17

Hagan el primer tramo en papel. Con la reina en (0, 0), en la fila 1 quedan las columnas 2 y 3: la 0 está ocupada, y la 1 está en la diagonal. Con (1, 2), la fila 2 no tiene ningún lugar: 0 y 2 están en columnas ocupadas, y 1 y 3 están en diagonales. La búsqueda vuelve, deshace (1, 2) y prueba (1, 3). Sin poda, ese árbol tendría 341 nodos.

La tabla se obtiene corriendo los dos programas para cada N. La poda no cambia la columna de soluciones, y eso es lo que hay que exigirle. Con poda se llega mucho más lejos. Para N = 12, el programa sin poda necesitaría más de 9 millones de millones de nodos, y no lo vamos a correr:

$ build/queens 12
n = 12, con poda: 14200 soluciones, 856189 nodos

Deshacer de forma correcta

“Deshacer” es exactamente lo contrario de elegir, en todas las partes del estado. Una versión a medias es peor que un olvido total, porque parece correcta al leerla. En errors/queens_partial_undo.c se libera la columna, pero las diagonales quedan marcadas:

q->column_used[col] = 0;    // deshace solo una parte

$ gcc -Wall -Wextra -std=c17 -g -fsanitize=address,undefined errors/queens_partial_undo.c -o build/queens_partial_undo
$ build/queens_partial_undo 8
n = 8, con poda: 0 soluciones, 11 nodos

Cero soluciones, sin ningún aviso, en un problema que tiene 92. Cada reina que se quitó dejó sus diagonales como ocupadas, y con eso el tablero se fue llenando de casillas prohibidas que ya nadie ataca. Por eso se usa una sola función para elegir y deshacer, o por lo menos dos líneas que se puedan leer lado a lado.

Error común. Deshacer con otro índice, o después de haber cambiado una variable. Si col cambia entre elegir y deshacer, se libera la columna equivocada. Las dos llamadas a mark deben recibir los mismos valores.

Una solución o todas

queens.c cuenta todas las soluciones, y por eso recorre todo lo que la poda deja. Muchas veces basta con una: un sudoku se resuelve una vez, y no tiene sentido seguir buscando. El cambio está en el retorno. La función devuelve si encontró algo, y quien la llama revisa esa respuesta:

algoritmo buscar(estado)
    si estado está completo entonces
        devolver 1
    fin si
    para opcion desde 0 hasta cantidad_de_opciones - 1 hacer
        si opcion es válida en estado entonces
            aplicar opcion a estado
            si buscar(estado) = 1 entonces
                devolver 1
            fin si
            quitar opcion de estado
        fin si
    fin para
    devolver 0
fin algoritmo

Comparen las dos formas:

En queens_first.c, además, column_of_row guarda las columnas elegidas:

// Devuelve 1 si encontró una solución, y la deja en column_of_row.
static int search(Queens *q, int row) {
    q->nodes++;
    if (row == q->n) {
        return 1;
    }
    for (int col = 0; col < q->n; col++) {
        if (can_place(q, row, col)) {
            mark(q, row, col, 1);
            q->column_of_row[row] = col;
            if (search(q, row + 1)) {
                return 1;
            }
            mark(q, row, col, 0);
        }
    }
    return 0;
}

$ build/queens_first 8
Q . . . . . . .
. . . . Q . . .
. . . . . . . Q
. . . . . Q . .
. . Q . . . . .
. . . . . . Q .
. Q . . . . . .
. . . Q . . . .
n = 8, primera solución: 114 nodos

Son 114 nodos en vez de 2057. No deshacer al encontrar es intencional, porque el estado es la respuesta: si se deshiciera de camino a la raíz, se borraría la solución que se acaba de encontrar. La promesa de la función queda con dos casos: si devuelve 1, el estado tiene una solución. Si devuelve 0, el estado está como se lo dieron.

Error común. Llamar a la función sin mirar lo que devuelve. En errors/first_ignored.c, la línea es search(q, row + 1); sola:

$ gcc -Wall -Wextra -std=c17 -g -fsanitize=address,undefined errors/first_ignored.c -o build/first_ignored
$ build/first_ignored 8
no hay solución
n = 8, primera solución: 2057 nodos

Los 2057 nodos delatan el problema: recorrió el árbol completo, encontró las 92 soluciones, ignoró cada aviso y al final devolvió 0. Y -Wall -Wextra no avisa, porque no es un error dejar de usar lo que devuelve una función.

Poda

Ya vimos un caso. Ahora la idea general, porque aquí está la pregunta importante: ¿la poda puede hacer que se pierda una solución?

Puede. Una poda es una afirmación: “debajo de este nodo no hay ninguna solución”. Si esa afirmación es verdadera, se ahorra trabajo sin cambiar el resultado. Si es falsa, el programa da una respuesta equivocada, rápido y sin ningún aviso. Por eso cada poda necesita una justificación, y esa justificación suele depender de algo que los datos deben cumplir.

En las reinas, la justificación es esta: si dos reinas ya puestas se atacan, seguirán atacándose sin importar dónde se pongan las demás, porque nunca se mueven. Agregar reinas no quita un ataque.

Un menú con presupuesto

Tenemos una carta con 12 platos, y un presupuesto de 30 soles. ¿Cuántas combinaciones de platos caben? El árbol es el de los subconjuntos, y sin poda se revisa el total en cada hoja:

// Sin poda: recorre todo el árbol y solo revisa el total en las hojas.
static long count_all(const int *prices, int n, int index, int total, int budget, long *nodes) {
    (*nodes)++;
    if (index == n) {
        return total <= budget;
    }
    return count_all(prices, n, index + 1, total + prices[index], budget, nodes)
         + count_all(prices, n, index + 1, total, budget, nodes);
}

Si total ya pasó de 30, pedir más platos no lo va a bajar. La versión con poda solo agrega esa revisión:

// Con poda: si ya se pasó, ningún plato más lo arregla, porque los precios son positivos.
static long count_pruned(const int *prices, int n, int index, int total, int budget, long *nodes) {
    (*nodes)++;
    if (total > budget) {
        return 0;
    }
    if (index == n) {
        return 1;
    }
    return count_pruned(prices, n, index + 1, total + prices[index], budget, nodes)
         + count_pruned(prices, n, index + 1, total, budget, nodes);
}

$ build/combos
sin poda: 249 combinaciones, 8191 nodos
con poda: 249 combinaciones, 1265 nodos

Los dos cuentan lo mismo, con 6 veces menos nodos. Observen que este programa pasa el estado por valor: total es un int de cada llamada. Por eso no hay nada que deshacer. Cada marco tiene su propio total, y al volver, el de quien llamó sigue intacto. Deshacer solo hace falta en lo que se comparte.

Cuando la poda miente

Ahora, la carta también tiene un vale de descuento de 5 soles, es decir, un “plato” de precio −5. Todo lo demás es igual:

$ gcc -Wall -Wextra -std=c17 -g -fsanitize=address,undefined errors/bad_prune.c -o build/bad_prune
$ build/bad_prune
sin poda: 5 combinaciones
con poda: 4 combinaciones

Los precios son {8, 5, -5} y el presupuesto es 6. Hagan la cuenta a mano:

Son 5, y la poda encontró 4. Al tomar el 8, el total ya pasó de 6, y la poda cortó esa rama. Pero más abajo estaba {8, −5}, que sí cabe. La frase “si ya me pasé, no hay arreglo” dependía de que los precios fueran positivos.

Idea clave. Una poda es correcta si solo corta ramas que no contienen ninguna solución. Escriban qué suposición la justifica. Cuando prueben, comparen con la versión sin poda: el contador de nodos debe bajar, y el resultado debe ser el mismo.

Elegir bien también poda

Hay otra forma de reducir el árbol, y es la que usarán en el laboratorio: elegir mejor qué decidir primero.

Las reinas se deciden fila por fila, porque cada fila tiene exactamente una. Un sudoku es distinto: cada celda vacía se tiene que llenar, y el orden lo elegimos nosotros. Podemos llenarlas en orden de lectura. O podemos elegir la celda con menos opciones.

• Si una celda tiene 0 opciones, ya se sabe que este camino no sirve. Al elegirla primero, el ciclo no hace ninguna llamada y se retorna de inmediato. En orden de lectura, habría que llenar todas las celdas anteriores, y repetir ese trabajo con cada combinación, antes de encontrarse con ella.
• Si tiene 1 opción, no hay nada que decidir: esa llamada no abre ninguna rama nueva.
• Si tiene 2, la rama se abre lo menos posible.

Esto no pierde soluciones, y la razón es simple: esa celda tiene que llenarse de todas maneras. Cambiar el orden de las decisiones no cambia qué tableros completos se pueden alcanzar. Por eso, con rigor, no es un corte como los de arriba, sino un cambio de orden que hace que los cortes ocurran antes. En la práctica se le llama poda porque el efecto es el mismo: desaparecen ramas del árbol que se habría recorrido.

Tiene un precio: cada nodo cuesta más. Para elegir la celda hay que contar las opciones de todas las vacías. Un nodo en orden de lectura llama a can_place hasta 9 veces, y un nodo con menos opciones puede llamarla cientos de veces. Menos nodos no siempre quiere decir menos tiempo.

El código de esta semana

make compila los programas de la clase en build/. make test corre tres archivos de pruebas:

make test-lab corre esas mismas pruebas de laboratorio sobre su código.

El laboratorio, paso a paso

Los archivos de partida están en code/week-11/lab, y su README.md tiene las preguntas y lo que pide cada parte. Esta semana hay una sola sesión, porque la otra es para la Práctica 3. make test-lab comprueba todo: falla hasta que terminen. Aquí están las ideas, no el código.

subset_sum. ¿Algún subconjunto del arreglo suma exactamente un valor? Es el árbol de subconjuntos con el retorno de “la primera solución”. La hoja responde si lo que falta sumar es 0. Como los valores pueden ser negativos, no pueden cortar cuando se pasan: ya vieron por qué. Con eso, un caso sin solución recorre todo el árbol, y sus nodos son exactamente 2^(n+1) − 1.

El sudoku. Un tablero de 9 × 9 tiene algunas celdas ya llenas. Hay que llenar las demás con dígitos de 1 a 9, sin repetir ninguno en una fila, en una columna o en una caja de 3 × 3. El archivo tiene 9 líneas de 9 dígitos, con 0 para una celda vacía. Por ejemplo, las dos primeras líneas de lab/data/facil.txt son estas:

430900600
602408005

El lector ya está hecho, en lab/board.c. El tablero se declara así, en lab/board.h:

typedef struct {
    int cells[BOARD_SIZE][BOARD_SIZE];
} Board;

Traduzcan el esquema al sudoku antes de escribir nada:

Tres cosas para cuidar:

• Un return 0 al final de los dígitos. Si ningún dígito sirve en la primera celda vacía, este camino está muerto, y se devuelve 0. Si ese return 0 falta, el ciclo sigue con la celda siguiente y deja vacía una celda obligatoria. Al final, la función devuelve 1 con un tablero incompleto. Por eso las pruebas miran el tablero, no solo el retorno.
• El orden de los dígitos y de las celdas. Para que todos cuenten igual, lab/solver.h fija las reglas: dígitos de 1 a 9, llamada recursiva solo si can_place lo permite, y nodo contado al entrar. Con estas reglas, el conteo es exacto, y make test-lab lo compara.
• Las pistas no se tocan. El ciclo solo mira celdas vacías, y deshacer solo pone 0 en la celda que este nodo llenó.

Después de la búsqueda en orden, escriban count_options, y una función que busque la celda con menos opciones. El empate lo gana la primera en orden de lectura. La búsqueda queda casi igual: solo cambia cómo se elige la celda.

Esto debe producir su programa con los cuatro tableros dados. Cada uno tiene una sola solución, comprobada con un programa que cuenta soluciones:

$ build/lab/solve lab/data/facil.txt lab/data/medio.txt lab/data/dificil.txt lab/data/sorpresa.txt
lab/data/facil.txt
  orden de lectura: resuelto, 72 nodos
  menos opciones:   resuelto, 38 nodos
lab/data/medio.txt
  orden de lectura: resuelto, 4314 nodos
  menos opciones:   resuelto, 169 nodos
lab/data/dificil.txt
  orden de lectura: resuelto, 1745319 nodos
  menos opciones:   resuelto, 1815 nodos
lab/data/sorpresa.txt
  orden de lectura: resuelto, 815 nodos
  menos opciones:   resuelto, 1116 nodos

Miren el último tablero. Elegir la celda con menos opciones no siempre gana: es un criterio que suele ayudar, no una garantía. Hay que medir, y por eso contamos nodos. Lo que sí está garantizado es que los dos métodos encuentran la misma solución, porque el tablero solo tiene una.

Y miren facil.txt: 38 nodos con 37 celdas vacías. Con menos opciones, hay un nodo por celda más la raíz: nunca hubo que volver atrás. Por lo mismo, ese tablero no sirve para comprobar que search_fewest_options deshace bien. Para eso usen medio.txt, o el tablero sin solución de test_lab.py.

Resumen

• Backtracking es buscar en un árbol de decisiones: elegir, explorar, deshacer. Cada nodo es un estado, cada rama es una opción y cada hoja es un final.
• En la pila solo está el camino actual: el árbol puede ser enorme, y la profundidad es el número de decisiones.
• La promesa de la función: al retornar, el estado está como lo recibió. Quien la llama puede seguir con su siguiente opción porque confía en eso.
• Solo hay que deshacer lo que se comparte y lo que una decisión posterior va a leer. Lo que se pasa por valor se deshace solo, y lo que siempre se sobrescribe antes de leerlo no necesita deshacerse.
• Subconjuntos: 2^n hojas y 2^(n+1) − 1 nodos. Permutaciones: n! hojas. Con 5 elementos: 32 y 120.
• Olvidar deshacer no produce avisos de gcc ni de los sanitizers. Sale un resultado equivocado, y hace falta un caso calculado a mano para verlo.
• Para buscar una solución, la función devuelve 1 o 0, y quien llama revisa ese retorno: si es 1, retorna sin deshacer, porque el estado es la respuesta.
• N reinas: una reina por fila es una representación que descarta casi todo. Con la poda, 8 reinas pasan de 19173961 nodos a 2057, con las mismas 92 soluciones.
• Una poda es correcta solo si corta ramas sin soluciones, y esa afirmación necesita una justificación. Si la suposición falla, como con un precio negativo, se pierden soluciones sin ningún aviso.
• Elegir primero la celda con menos opciones no pierde soluciones, porque esa celda hay que llenarla igual. Suele bajar mucho los nodos, pero no siempre, y cada nodo cuesta más. Hay que medir.

Ejercicios

Decidan primero y ejecuten después. Todo programa revisa sus lecturas, compila sin advertencias y libera lo que reserva.

1. Dibujen el árbol de permutaciones de abcd hasta el segundo nivel. ¿Cuántos nodos tiene cada nivel completo? Sumen y compárenlo con la fila n = 4 de build/count_trees.

2. Sin ejecutar, digan cuántas líneas escribe cada programa, y cuáles son las dos primeras, si items es "abcd". Luego cámbienlo y compruébenlo.

   a) subsets.c
   b) permutations.c

3. En subsets.c, intercambien las dos ramas: que primero explore sin el elemento y después con él. Escriban cuidando que la promesa se cumpla. ¿Cambia el orden de la salida? ¿Y los nodos? ¿Hace falta deshacer algo al final de la función?

4. errors/subsets_no_undo.c escribe ocho veces lo mismo. Sigan a mano sus primeras llamadas, y expliquen cómo se llega a la segunda línea. Corríjanlo, y digan qué promesa se rompía.

5. Escriban un programa que escriba todas las combinaciones de k elementos de abcde. Por ejemplo, para k = 2: ab, ac, ad… Empiecen por dibujar el árbol. ¿Cuántas hay para k = 2? ¿Qué condición corta una rama si ya no quedan elementos suficientes para llegar a k? Comparen los nodos con y sin ese corte.

6. Todas las cadenas de longitud n con los caracteres a y b: escriban la función y digan cuántas hay. Luego, las que no tienen dos b seguidas. ¿Se puede podar? ¿Qué se revisa, y en qué momento?

7. En queens_first.c, cambien mark(q, row, col, 0); de lugar: pónganlo antes del if (search(...)). Antes de ejecutar, digan qué ocurre. Luego compruébenlo. ¿Por qué el programa puede seguir escribiendo un tablero, aunque esté mal?

8. queens.c usa tres arreglos para saber qué está ocupado. Escriban can_place sin ellos, solo con column_of_row, revisando las filas anteriores. ¿Hace falta deshacer algo? ¿Cuántos nodos da? ¿Por qué esa cuenta no cambia con respecto a queens.c, aunque cada nodo trabaje más?

9. Modifiquen queens.c para que no cuente las soluciones que son reflejo de otra: basta pedir que la reina de la fila 0 esté en la mitad izquierda. Con N = 8, ¿cuántos nodos y soluciones salen? ¿Es correcta esa poda? Justifíquenlo. Tengan cuidado con N impar.

10. En combos.c, ordenen los precios de mayor a menor antes de buscar. ¿Cambia el resultado? ¿Y los nodos? Prueben también de menor a mayor, y expliquen en qué orden la poda corta antes.

11. Escriban una poda correcta para errors/bad_prune.c, que funcione aun con vales: antes de buscar, sumen los precios negativos que quedan por decidir. ¿Cuánto es lo menos que puede llegar a valer el total desde este nodo?

12. Escriban int count_solutions(Board *board, int limit) para el laboratorio. Debe detenerse al llegar a limit y dejar el tablero como lo recibió. ¿Se puede usar el return de la función para saber cuándo parar? Úsenla con limit = 2 para comprobar que los cuatro tableros de lab/data tienen una sola solución. Luego borren pistas de facil.txt, en una copia, hasta que tenga dos.