// Un problema completo, ya resuelto con el backtracker: pintar cinco zonas de un mapa con tres
// colores, sin que dos zonas vecinas tengan el mismo. Es el modelo para queens.c y sudoku.c.
#include <stdio.h>

#include "backtrack.h"

#define ZONES 5
#define COLORS 3

// Las vecinas de cada zona, de la A a la E.
const int NEIGHBORS[ZONES][ZONES] = {
    {0, 1, 1, 0, 0},
    {1, 0, 1, 1, 0},
    {1, 1, 0, 1, 0},
    {0, 1, 1, 0, 1},
    {0, 0, 0, 1, 0},
};

// El estado vive aquí. El backtracker solo ve un void *.
typedef struct {
    int color[ZONES];
    long solutions;
    int first[ZONES];
} Coloring;

// El paso es la zona, y la opción es el color.
static int coloring_options(void *context, int step) {
    (void) context;
    (void) step;
    return COLORS;
}

static int coloring_is_valid(void *context, int step, int option) {
    const Coloring *state = context;
    for (int zone = 0; zone < step; zone++) {
        if (NEIGHBORS[step][zone] && state->color[zone] == option) {
            return 0;
        }
    }
    return 1;
}

static void coloring_place(void *context, int step, int option) {
    Coloring *state = context;
    state->color[step] = option;
}

static void coloring_undo(void *context, int step, int option) {
    Coloring *state = context;
    (void) option;
    state->color[step] = -1;
}

// Devuelve 0 para seguir buscando: queremos contarlas todas.
static int coloring_on_solution(void *context) {
    Coloring *state = context;
    if (state->solutions == 0) {
        for (int zone = 0; zone < ZONES; zone++) {
            state->first[zone] = state->color[zone];
        }
    }
    state->solutions++;
    return 0;
}

int main(void) {
    const char *names[COLORS] = {"rojo", "verde", "azul"};
    Coloring state = {.solutions = 0};
    Problem problem = {
        .steps = ZONES,
        .options = coloring_options,
        .is_valid = coloring_is_valid,
        .place = coloring_place,
        .undo = coloring_undo,
        .on_solution = coloring_on_solution,
    };

    long nodes = backtrack(&problem, &state);

    printf("%ld soluciones, %ld nodos\n", state.solutions, nodes);
    if (state.solutions > 0) {
        for (int zone = 0; zone < ZONES; zone++) {
            printf("%c: %s\n", 'A' + zone, names[state.first[zone]]);
        }
    }
    return 0;
}