# Laboratorio de la semana 11: resolver sudokus

Esta semana hay una sola sesión de laboratorio, porque la otra es para la Práctica 3. Está pensada
para unos 90 minutos de trabajo. Los comandos se corren desde `code/week-11`. Las ideas están en los
apuntes, en la sección "El laboratorio, paso a paso".

| Archivo | Qué es | ¿Lo cambian? |
|---|---|---|
| `board.h`, `board.c` | El tablero y su lectura desde un archivo | No |
| `subset_sum.h` | Lo que promete `subset_sum` | No |
| `subset_sum.c` | `subset_sum` hecha, y su función recursiva por escribir | **Sí** |
| `solver.h` | Lo que promete cada función del solucionador, y cómo se cuentan los nodos | No |
| `solver.c` | Las funciones por escribir | **Sí** |
| `solver_tests.c` | Pruebas con `assert`. Agreguen las suyas | **Sí** |
| `solve.c` | El programa que resuelve archivos y compara los nodos | No |
| `data/` | `facil.txt`, `medio.txt`, `dificil.txt` y `sorpresa.txt`: cuatro tableros con una sola solución | No |

Un archivo de tablero tiene 9 líneas de 9 dígitos, con 0 para una celda vacía. El lector no acepta otra
cosa, y no revisa las reglas del sudoku: de eso se encarga `board_is_legal`, y `solve.c` la llama antes de
resolver.

```sh
make lab                  # compila solver_tests y solve en build/lab/
build/lab/solver_tests    # corre sus pruebas
build/lab/solve lab/data/facil.txt
make test-lab             # comprueba todo el laboratorio; falla hasta que terminen
```

## Parte 1: leer (unos 10 minutos)

Lean `board.h`, `solver.h` y `subset_sum.h` completos, y luego `board.c`. Respondan por escrito, sin
ejecutar nada.

1. En `board.c`, ¿qué línea rechaza una línea de 10 dígitos? ¿Y un archivo con una décima
   línea?
2. En `is_repeated`, ¿qué celda revisa la vuelta `i = 5` si `row = 4` y `col = 7`?
3. `solver.h` promete que, si no hay solución, `*board` queda igual que al inicio. ¿Qué línea de su
   búsqueda tendrá que cumplir esa promesa?
4. Dos cuentas de nodos solo se pueden comparar si significan lo mismo. Según `solver.h`, ¿qué es un nodo?
   ¿Cuenta la primera llamada?

## Parte 2: `subset_sum` (unos 20 minutos)

Escriban `search` en `subset_sum.c`. Por cada elemento hay dos ramas, con él y sin él: es el árbol de
subconjuntos de los apuntes, con dos diferencias. La hoja responde en vez de escribir, y el retorno se
revisa para detenerse en la primera solución.

Antes de ejecutar, calculen a mano cuántos nodos da `{3, 9, 5}` con un objetivo que no existe. La prueba en
`solver_tests.c` lo comprueba. No agreguen una poda por "ya me pasé": los valores pueden ser negativos, y
las pruebas lo revisan.

## Parte 3: el solucionador en orden (unos 35 minutos)

1. `can_place`: fila, columna y caja, en un solo ciclo o en tres.
2. `search_in_order`: cuenta el nodo, busca la primera celda vacía y prueba en ella los dígitos de 1 a 9. Si
   no hay celdas vacías, ya terminó. Elegir, explorar, deshacer.

Cuando pasen las primeras pruebas, comparen `facil.txt` con `medio.txt`. Busquen la línea que deshace,
bórrenla, y vean qué dice cada tablero. Luego vuelvan a ponerla.

## Parte 4: elegir la celda con menos opciones (unos 25 minutos)

1. `count_options`: es un ciclo sobre `can_place`.
2. `search_fewest_options`: lo mismo, pero en vez de tomar la primera celda vacía, toma la de menos opciones.
   Escriban una función aparte que la busque: necesita dos ciclos, y devolver una fila y una columna.

Con eso, comparen:

```sh
build/lab/solve lab/data/facil.txt lab/data/medio.txt lab/data/dificil.txt lab/data/sorpresa.txt
make test-lab
```

Escriban en una tabla los nodos de cada método, y respondan: ¿en qué tablero se gana más? ¿Hay alguno en el
que se pierde? ¿Cuánto cuesta cada nodo en cada método, en llamadas a `can_place` como máximo?

**Si no alcanza el tiempo:** lo que no terminen lo terminan antes de la próxima clase. El orden de arriba deja
lo más importante primero. La parte 4 es la que puede quedar para después de la sesión.

## Si sobra tiempo

1. Escriban `int count_solutions(Board *board, int limit)`, que cuenta soluciones y se detiene al llegar a
   `limit`. Con ella pueden comprobar que un tablero suyo tiene una sola solución.
2. Inventen un tablero con una sola solución en el que `solve_in_order` visite más de un millón de nodos.
   ¿Qué tienen que dejar vacío al inicio?
3. Agreguen a `subset_sum` una poda que sea correcta también con valores negativos. Pista: antes de buscar,
   calculen cuánto pueden sumar como máximo y como mínimo los elementos que faltan.