#include <bits/stdc++.h>
#include <chrono>
using namespace std;

#define LIBERA 0
#define N 9

bool trova_casella_vuota(int griglia[N][N], int &riga, int &colonna);

bool va_bene(int griglia[N][N], int riga,int colonna, int num);

bool risolvi(int griglia[N][N]);

//Cuore del programma. Prende una griglia parzialmente riempita e
//prova a completarla ricorsivamente

bool risolvi(int griglia[N][N])
{
    int riga, colonna;

    if (!trova_casella_vuota(griglia, riga, colonna))
        return true; // siamo a posto!

    for (int num = 1; num <= 9; num++)
    {
        if (va_bene(griglia, riga, colonna, num))
        {
            // prova a vedere se va bene
            griglia[riga][colonna] = num;
            if (risolvi(griglia))
                return true;
            // Torna indietro
            griglia[riga][colonna] = LIBERA;
        }
    }
    return false; // Forza il backtracking
}


bool trova_casella_vuota(int griglia[N][N],
                         int &riga, int &colonna)
{
    for (riga = 0; riga < N; riga++)
        for (colonna = 0; colonna < N; colonna++)
            if (griglia[riga][colonna] == LIBERA)
                return true;
    return false;
}

bool usato_nella_riga(int griglia[N][N], int riga, int num)
{
    for (int colonna = 0; colonna < N; colonna++)
        if (griglia[riga][colonna] == num)
            return true;
    return false;
}

bool usato_nella_colonna(int griglia[N][N], int colonna, int num)
{
    for (int riga = 0; riga < N; riga++)
        if (griglia[riga][colonna] == num)
            return true;
    return false;
}

bool usato_nella_scatola(int griglia[N][N], int boxStartriga,
                         int boxStartcolonna, int num)
{
    for (int riga = 0; riga < 3; riga++)
        for (int colonna = 0; colonna < 3; colonna++)
            if (griglia[riga + boxStartriga]
                [colonna + boxStartcolonna] == num)
                return true;
    return false;
}

//Controlla se si può assegnare una cifra alla riga e colonna indicata
bool va_bene(int griglia[N][N], int riga,
             int colonna, int num)
{
    return !usato_nella_riga(griglia, riga, num) &&
           !usato_nella_colonna(griglia, colonna, num) &&
           !usato_nella_scatola(griglia, riga - riga % 3,
                                colonna - colonna % 3, num) &&
           griglia[riga][colonna] == LIBERA;
}

void stampa(int griglia[N][N])
{
    for (int riga = 0; riga < N; riga++)
    {
        for (int colonna = 0; colonna < N; colonna++)
            cout << griglia[riga][colonna] << " ";
        cout << endl;
    }
}


int main()
{
    int griglia[N][N] = {{3, 0, 6, 5, 0, 8, 4, 0, 0},
                      {5, 2, 0, 0, 0, 0, 0, 0, 0},
                      {0, 8, 7, 0, 0, 0, 0, 3, 1},
                      {0, 0, 3, 0, 1, 0, 0, 8, 0},
                      {9, 0, 0, 8, 6, 3, 0, 0, 5},
                      {0, 5, 0, 0, 9, 0, 6, 0, 0},
                      {1, 3, 0, 0, 0, 0, 2, 5, 0},
                      {0, 0, 0, 0, 0, 0, 0, 7, 4},
                      {0, 0, 5, 2, 0, 6, 3, 0, 0}};



    chrono::steady_clock::time_point begin = std::chrono::steady_clock::now();
    bool risolto=risolvi(griglia);
    chrono::steady_clock::time_point end = std::chrono::steady_clock::now();
    cout << "Durata calcoli = " << std::chrono::duration_cast<std::chrono::microseconds>(end - begin).count() << "[µs]" << std::endl;

    if (risolto)
        stampa(griglia);
    else
        cout << "Nessuna soluzione\n";

    return 0;
}

// Codice originale di rathbhupendra