#include "backtrack.h"
#include "sudoku.h"

#define MAX_EMPTY (BOARD_SIZE * BOARD_SIZE)

// El estado del problema. Cada paso es una celda vacía, y están en estas listas, en orden de lectura.
typedef struct {
    Board board;
    int empty_row[MAX_EMPTY];
    int empty_column[MAX_EMPTY];
    long found;
    int limit;
    Board first;
} Sudoku;

// --- Por escribir. El paso es el índice de una celda vacía. La opción va de 0 a 8, y representa
// el dígito opción + 1. ---

static int sudoku_options(void *context, int step) {
    (void) context;
    (void) step;
    return 0;
}

// Usen board_can_place, de board.h.
static int sudoku_is_valid(void *context, int step, int option) {
    (void) context;
    (void) step;
    (void) option;
    return 0;
}

static void sudoku_place(void *context, int step, int option) {
    (void) context;
    (void) step;
    (void) option;
}

static void sudoku_undo(void *context, int step, int option) {
    (void) context;
    (void) step;
    (void) option;
}

// Cuenta la solución, y si es la primera la copia en first. Devuelve 1 si ya se llegó a limit.
static int sudoku_on_solution(void *context) {
    (void) context;
    return 1;
}

// --- De aquí para abajo ya está hecho. ---

static int list_empty_cells(Sudoku *state) {
    int count = 0;
    for (int row = 0; row < BOARD_SIZE; row++) {
        for (int column = 0; column < BOARD_SIZE; column++) {
            if (state->board.cells[row][column] == 0) {
                state->empty_row[count] = row;
                state->empty_column[count] = column;
                count++;
            }
        }
    }
    return count;
}

long sudoku_search(const Board *puzzle, int limit, Board *solution, long *nodes) {
    *nodes = 0;
    if (!board_is_legal(puzzle)) {
        return 0;
    }
    Sudoku state = {.board = *puzzle, .found = 0, .limit = limit};
    Problem problem = {
        .steps = list_empty_cells(&state),
        .options = sudoku_options,
        .is_valid = sudoku_is_valid,
        .place = sudoku_place,
        .undo = sudoku_undo,
        .on_solution = sudoku_on_solution,
    };
    *nodes = backtrack(&problem, &state);
    if (state.found > 0) {
        *solution = state.first;
    }
    return state.found;
}