// Backtracking por filas, para comparar con el solucionador SAT en el laboratorio. Lee un sudoku de 9 por 9 de un
// archivo, en el formato de Introducción a la Programación: 9 líneas de 9 dígitos, con 0 en las celdas vacías. Sin
// archivo, usa uno de 17 valores dados, difícil para este orden de búsqueda. Solo informa nodos y tiempo.
#include <array>
#include <chrono>
#include <fstream>
#include <iostream>
#include <string>
#include <vector>

namespace {

using Grid = std::array<int, 81>;

const char* const hard_puzzle[] = {"000000000", "000003085", "001020000", "000507000", "004000100",
                                   "090000000", "500000073", "002010000", "000040009"};

struct Counter {
    long long nodes = 0;
};

bool can_place(const Grid& grid, int position, int digit) {
    const int r = position / 9, c = position % 9;
    for (int i = 0; i < 9; i++) {
        if (grid[r * 9 + i] == digit || grid[i * 9 + c] == digit) return false;
        if (grid[(r / 3 * 3 + i / 3) * 9 + c / 3 * 3 + i % 3] == digit) return false;
    }
    return true;
}

bool solve(Grid& grid, int position, Counter& counter) {
    counter.nodes++;
    while (position < 81 && grid[position] != 0) position++;
    if (position == 81) return true;
    for (int digit = 1; digit <= 9; digit++) {
        if (can_place(grid, position, digit)) {
            grid[position] = digit;
            if (solve(grid, position + 1, counter)) return true;
            grid[position] = 0;
        }
    }
    return false;
}

}  // namespace

int main(int argc, char** argv) {
    std::vector<std::string> lines;
    if (argc > 1) {
        std::ifstream in(argv[1]);
        std::string line;
        while (in >> line) lines.push_back(line);
    } else {
        lines.assign(std::begin(hard_puzzle), std::end(hard_puzzle));
    }
    Grid grid{};
    int given = 0;
    for (int i = 0; i < 81; i++) {
        grid[i] = lines.at(i / 9).at(i % 9) - '0';
        given += grid[i] != 0 ? 1 : 0;
    }
    Counter counter;
    const auto start = std::chrono::steady_clock::now();
    const bool solved = solve(grid, 0, counter);
    const std::chrono::duration<double> elapsed = std::chrono::steady_clock::now() - start;
    std::cout << "valores dados: " << given << "\n";
    std::cout << "resultado: " << (solved ? "tiene solución" : "sin solución") << "\n";
    std::cout << "nodos: " << counter.nodes << "\n";
    std::cout << "segundos: " << elapsed.count() << "\n";
}