// Un backtracker genérico. No sabe qué problema resuelve: todo lo pregunta con callbacks,
// y les pasa el mismo contexto, que es donde vive el estado del problema.
#ifndef BACKTRACK_H
#define BACKTRACK_H

typedef struct {
    // Cuántas decisiones hay que tomar. Una solución es haber tomado todas.
    int steps;

    // Cuántas opciones hay en este paso. Se prueban de la 0 a la anterior a ese número.
    int (*options)(void *context, int step);

    // ¿Se puede tomar esta opción, dado lo que ya se decidió?
    int (*is_valid)(void *context, int step, int option);

    // Toma la opción: cambia el estado.
    void (*place)(void *context, int step, int option);

    // Deshace lo que hizo place, con los mismos argumentos.
    void (*undo)(void *context, int step, int option);

    // Se llama con cada solución. Devuelve 1 para detener la búsqueda y 0 para seguir.
    int (*on_solution)(void *context);
} Problem;

// Recorre el árbol de decisiones. Devuelve cuántos nodos visitó: una visita es llegar a un paso,
// o a una solución, incluida la raíz. Al terminar, aunque se haya detenido antes, cada place tuvo
// su undo: el estado queda como estaba. Por eso on_solution debe copiar lo que quiera guardar.
long backtrack(const Problem *problem, void *context);

#endif