#include "CHEUCLE - HUYNH - ODIER - WAKIM.h"
int taille_arbre = 0;
int retour;
/** Retourn les possibilités d'un case en tennant compte de son entourage, sa collonne, ligne et case*/
vector <unsigned> poss_case(vector <unsigned> tab_ligne, vector <unsigned> tab_collonne, vector< vector <unsigned> > tab_case)
{
    vector <unsigned> possibilites;
    for(unsigned i=0 ; i<tab_ligne.size() ; i++) possibilites.push_back(i+1); // On a toutes les possibilitées, on les élimine quand on vois que ce n'est pas possible

    for(unsigned i=0 ; i<tab_ligne.size() ; i++) // Vérification de la ligne et de la collonne
    {
        if(position_in_vector(possibilites, tab_ligne[i]) != possibilites.size()+1) /* on cherche si la contrainte impose qqchose */
        {
            possibilites.erase(possibilites.begin() + position_in_vector(possibilites, tab_ligne[i])); // on enlève la possibilité
        }

        if(position_in_vector(possibilites, tab_collonne[i]) != possibilites.size()+1) /* on cherche si la contrainte impose qqchose */
        {
            possibilites.erase(possibilites.begin() + position_in_vector(possibilites, tab_collonne[i])); // on enlève la possibilité
        }
    }
    for(unsigned i=0 ; i<tab_case.size() ; i++) // Vérification de la case
    {
        for(unsigned j=0 ; j<tab_case[i].size() ; j++)
        {
            if(position_in_vector(possibilites, tab_case[i][j]) != possibilites.size()+1) /* on cherche si la contrainte impose qqchose */
            {
                possibilites.erase(possibilites.begin() + position_in_vector(possibilites, tab_case[i][j])); // on enlève la possibilité
            }
        }
    }
    //if(possibilites.size() == 0) possibilites.push_back(0);
    return possibilites;
}
/** Retourne la position d'un élèment dans un vector ( l'index)*/
unsigned position_in_vector(vector <unsigned> possibilites, unsigned value)
{
    for(unsigned i=0 ; i<possibilites.size() ; i++) // On parcour à la recherche de notre élèment
    {
        if(value == possibilites[i]) return i;
    }
    return possibilites.size()+1;
}
/** Résolution basique on évite uniquement les choix entrainant une impossibilité*/
vector< vector <unsigned> > Super_resolution_propagation_contraintes(vector< vector <unsigned> > sudoku, unsigned mode) // ajouter en argument une fonction de contraintes ?
{
    vector < vector<unsigned> > cases_et_poss;

    for(unsigned i=0 ; i<sudoku.size(); i++)
    {
        for(unsigned j=0 ; j< sudoku[i].size() ; j++) // Parcour de toutes les cases pour en choisir les valeurs.
        {
            if(sudoku[i][j] == 0)
            {
                vector <unsigned> tab_ligne = sudoku[i]; // la ligne correspondante
                vector <unsigned> tab_collonne = get_collone(sudoku, j); // la collonne correspondante
                vector < vector <unsigned> > tab_case = get_case(sudoku, i/mode, j/mode, mode); // la case correspondante
                vector <unsigned> possibilites = poss_case(tab_ligne, tab_collonne, tab_case); // Calcul possibilitès
                for(unsigned k=0; k<possibilites.size() ; k++) // récursivité
                {
                    vector< vector <unsigned> > sudoku_to_send = sudoku;
                    sudoku_to_send[i][j] = possibilites[k];
                    sudoku_to_send = Super_resolution_propagation_contraintes(sudoku_to_send, mode);
                    if(est_total_sudoku(sudoku_to_send)) return sudoku_to_send;
                }
            }
        }
    }
    return sudoku;
}
/** Résolution avec propagation de contrainte et évaluation des choix possible. Le critère est : l'état ayant le moins de possibilité de changement*/

/** ATTENTION ! Toutes les autres fonction commencant par "Super_resolution_propagation_contraintes" fonctionnent de la même facon !
L'unique changement est dans le critère de notation des possibilitées. Pour cette raison uniquement cette fonction sera commenté */
vector< vector <unsigned> > Super_resolution_propagation_contraintes2(vector< vector <unsigned> > sudoku, unsigned mode) // min
{
    taille_arbre ++;
    if(est_total_sudoku(sudoku)){ // Affichage au moment de la fin
        cout << endl << "Le nombre d'état et de changements : " << taille_arbre-1 << endl;
        cout << "Le nombre de retour : " << retour << endl;
        return sudoku;}
    vector < vector<unsigned> > cases_et_poss;
    vector < vector <unsigned> > tab_possibilites;
    vector <unsigned> tab_possibilites_j;
    vector <unsigned> tab_possibilites_x;

    for(unsigned i=0 ; i<sudoku.size(); i++) // On Regarde toutes les valeurs non assigné et on donne une note à chaque point pour savoir lequel on va choisir
    {
        for(unsigned j=0 ; j< sudoku[i].size() ; j++) // Parcour de toutes les cases pour en choisir les valeurs.
        {
            if(sudoku[i][j] == 0)
            {
                vector <unsigned> tab_ligne = sudoku[i]; // la ligne correspondante
                vector <unsigned> tab_collonne = get_collone(sudoku, j); // la collonne correspondante
                vector < vector <unsigned> > tab_case = get_case(sudoku, i/mode, j/mode, mode); // la case correspondante
                tab_possibilites.push_back(poss_case(tab_ligne, tab_collonne, tab_case)); // possibilitès
                if(tab_possibilites[tab_possibilites.size()-1].size() == 0){
                    retour ++;
                    return sudoku;
                    }
                tab_possibilites_j.push_back(j);/** Stockage de i et j */
                tab_possibilites_x.push_back(i);
            }
        }
    }

    unsigned min=mode*mode +1, position; // Choix du point suivant notre critère, ici minimum de possibilité de changement donc la taille du tableau contenant les possibilités pour un point
    for(unsigned i=0 ; i<tab_possibilites.size() ; i++)
    {
        if(tab_possibilites[i].size()<min)
        {
            min = tab_possibilites[i].size();
            position = i;
        }
    }
    // Récurcivité pour toutes les possibilitées de changement du point choisi
    for(unsigned k=0; tab_possibilites.size() != 0 && k<tab_possibilites[position].size() ; k++) // récursivité
    {
        vector< vector <unsigned> > sudoku_to_send = sudoku;
        sudoku_to_send[tab_possibilites_x[position]][tab_possibilites_j[position]] = tab_possibilites[position][k];
        sudoku_to_send = Super_resolution_propagation_contraintes2(sudoku_to_send, mode);
        if(est_total_sudoku(sudoku_to_send)) return sudoku_to_send;
    }
    return sudoku;
}
/** Résolution avec propagation de contrainte et évaluation des choix possible. Le critère est : l'état ayant le plus de possibilité de changement*/
vector< vector <unsigned> > Super_resolution_propagation_contraintes3(vector< vector <unsigned> > sudoku, unsigned mode) // max
{
    if(est_total_sudoku(sudoku)) return sudoku;
    vector < vector<unsigned> > cases_et_poss;
    vector < vector <unsigned> > tab_possibilites;
    vector <unsigned> tab_possibilites_j;
    vector <unsigned> tab_possibilites_x;

    for(unsigned i=0 ; i<sudoku.size(); i++)
    {
        for(unsigned j=0 ; j< sudoku[i].size() ; j++) // Parcour de toutes les cases pour en choisir les valeurs.
        {
            if(sudoku[i][j] == 0)
            {
                vector <unsigned> tab_ligne = sudoku[i]; // la ligne correspondante
                vector <unsigned> tab_collonne = get_collone(sudoku, j); // la collonne correspondante
                vector < vector <unsigned> > tab_case = get_case(sudoku, i/mode, j/mode, mode); // la case correspondante
                tab_possibilites.push_back(poss_case(tab_ligne, tab_collonne, tab_case)); // possibilitès
                if(tab_possibilites[tab_possibilites.size()-1].size() == 0)return sudoku;
                tab_possibilites_j.push_back(j);
                tab_possibilites_x.push_back(i);
            }
        }
    }

    unsigned max=0, position;
    for(unsigned i=0 ; i<tab_possibilites.size() ; i++)
    {
        if(tab_possibilites[i].size()>max)
        {
            max = tab_possibilites[i].size();
            position = i;
        }
    }

    for(unsigned k=0; tab_possibilites.size() != 0 && k<tab_possibilites[position].size() ; k++) // récursivité
    {
        vector< vector <unsigned> > sudoku_to_send = sudoku;
        sudoku_to_send[tab_possibilites_x[position]][tab_possibilites_j[position]] = tab_possibilites[position][k];
        sudoku_to_send = Super_resolution_propagation_contraintes3(sudoku_to_send, mode);
        if(est_total_sudoku(sudoku_to_send)) return sudoku_to_send;
    }
    return sudoku;
}
/** Résolution avec propagation de contrainte et évaluation des choix possible. Le critère est : l'état ayant le moins de possibilité de changement et le moins d'influence*/
vector< vector <unsigned> > Super_resolution_propagation_contraintes4(vector< vector <unsigned> > sudoku, unsigned mode) // min et ajout influence
{
    taille_arbre ++;
    if(est_total_sudoku(sudoku)){
        cout << endl << "Le nombre d'état et de changements : " << taille_arbre-1 << endl;
        cout << "Le nombre de retour : " << retour << endl;
        return sudoku;}
    vector < vector<unsigned> > cases_et_poss;
    vector < vector <unsigned> > tab_possibilites;
    vector < vector <unsigned> > tab_influence = creation_sudoku_vide(mode);
    vector <unsigned> tab_possibilites_j;
    vector <unsigned> tab_possibilites_x;


    for(unsigned i=0 ; i<sudoku.size(); i++)
    {
        for(unsigned j=0 ; j< sudoku[i].size() ; j++) // Parcour de toutes les cases pour en choisir les valeurs.
        {
            if(sudoku[i][j] == 0)
            {
                vector <unsigned> tab_ligne = sudoku[i]; // la ligne correspondante
                vector <unsigned> tab_collonne = get_collone(sudoku, j); // la collonne correspondante
                vector < vector <unsigned> > tab_case = get_case(sudoku, i/mode, j/mode, mode); // la case correspondante
                tab_influence[i][j] = CalculInfluence( tab_ligne, tab_collonne, tab_case);
                tab_possibilites.push_back(poss_case(tab_ligne, tab_collonne, tab_case)); // possibilitès
                if(tab_possibilites[tab_possibilites.size()-1].size() == 0){
                    retour ++;
                    return sudoku;
                    }
                tab_possibilites_j.push_back(j);
                tab_possibilites_x.push_back(i);

            }
        }
    }
    if(tab_possibilites.size() == 0) return sudoku;

    unsigned min=mode*mode*mode +1, position;
    for(unsigned i=0 ; i<tab_possibilites.size() && tab_possibilites[i].size() != 0 ; i++)
    {
        if(tab_possibilites[i].size()+ tab_influence[tab_possibilites_x[i]][tab_possibilites_j[i]]<min && tab_possibilites[i].size()!=0 )
        {
            min = tab_possibilites[i].size() + tab_influence[tab_possibilites_x[i]][tab_possibilites_j[i]];
            position = i;
        }
    }
    for(unsigned k=0; tab_possibilites.size() != 0 && k<tab_possibilites[position].size() && tab_possibilites[position][k] != 0 ; k++) // récursivité
    {
        vector< vector <unsigned> > sudoku_to_send = sudoku;
        sudoku_to_send[tab_possibilites_x[position]][tab_possibilites_j[position]] = tab_possibilites[position][k];
        sudoku_to_send = Super_resolution_propagation_contraintes4(sudoku_to_send, mode);
        if(est_total_sudoku(sudoku_to_send)) return sudoku_to_send;
    }
    return sudoku;
}
/** Résolution avec propagation de contrainte et évaluation des choix possible. Le critère est : ayant le moins d'influence */
vector< vector <unsigned> > Super_resolution_propagation_contraintes5(vector< vector <unsigned> > sudoku, unsigned mode) // influence min
{
    taille_arbre ++;
    if(est_total_sudoku(sudoku)){
        cout << endl << "Le nombre d'état et de changements : " << taille_arbre-1 << endl;
        cout << "Le nombre de retour : " << retour << endl;
        return sudoku;
        }
    vector < vector<unsigned> > cases_et_poss;
    vector < vector <unsigned> > tab_possibilites;
    vector <unsigned> tab_influence;
    vector <unsigned> tab_possibilites_y;
    vector <unsigned> tab_possibilites_x;

    for(unsigned i=0 ; i<sudoku.size(); i++)
    {
        for(unsigned j=0 ; j< sudoku[i].size() ; j++) // Parcour de toutes les cases pour en choisir les valeurs.
        {
            if(sudoku[i][j] == 0)
            {
                vector <unsigned> tab_ligne = sudoku[i]; // la ligne correspondante
                vector <unsigned> tab_collonne = get_collone(sudoku, j); // la collonne correspondante
                vector < vector <unsigned> > tab_case = get_case(sudoku, i/mode, j/mode, mode); // la case correspondante
                tab_influence.push_back(CalculInfluence( tab_ligne, tab_collonne, tab_case));
                tab_possibilites_y.push_back(j);
                tab_possibilites_x.push_back(i);
            }
        }
    }

    unsigned min=mode*mode*mode +1, position;
    for(unsigned i=0 ; i< tab_influence.size() ; i++)
    {
        if(tab_influence[i]<min && tab_influence[i]!=0)
        {
            min =tab_influence[i];
            position = i;
        }
    }
    vector <unsigned> tab_ligne = sudoku[tab_possibilites_x[position]]; // la ligne correspondante
    vector <unsigned> tab_collonne = get_collone(sudoku, tab_possibilites_y[position]); // la collonne correspondante
    vector < vector <unsigned> > tab_case = get_case(sudoku, tab_possibilites_x[position]/mode, tab_possibilites_y[position]/mode, mode); // la case correspondante
    tab_possibilites.push_back(poss_case(tab_ligne, tab_collonne, tab_case));

    if(tab_possibilites[0].size() == 0){
        retour ++;
        return sudoku;
    }

    for(unsigned k=0; tab_possibilites.size() != 0 && k<tab_possibilites[0].size() ; k++) // récursivité
    {
        vector< vector <unsigned> > sudoku_to_send = sudoku;
        sudoku_to_send[tab_possibilites_x[position]][tab_possibilites_y[position]] = tab_possibilites[0][k];
        sudoku_to_send = Super_resolution_propagation_contraintes5(sudoku_to_send, mode);
        if(est_total_sudoku(sudoku_to_send)) return sudoku_to_send;
    }
    return sudoku;
}
/** Résolution avec propagation de contrainte et évaluation des choix possible. Le critère est : l'état ayant le plus d'influence*/
vector< vector <unsigned> > Super_resolution_propagation_contraintes6(vector< vector <unsigned> > sudoku, unsigned mode) // influence max
{
    taille_arbre ++;
    if(est_total_sudoku(sudoku)){
        cout << endl << "Le nombre d'état et de changements : " << taille_arbre-1 << endl;
        cout << "Le nombre de retour : " << retour << endl;
        return sudoku;}
    vector < vector<unsigned> > cases_et_poss;
    vector < vector <unsigned> > tab_possibilites;
    vector < vector <unsigned> > tab_influence = creation_sudoku_vide(mode);
    unsigned x;
    unsigned y;

    for(unsigned i=0 ; i<sudoku.size(); i++)
    {
        for(unsigned j=0 ; j< sudoku[i].size() ; j++) // Parcour de toutes les cases pour en choisir les valeurs.
        {
            if(sudoku[i][j] == 0)
            {
                vector <unsigned> tab_ligne = sudoku[i]; // la ligne correspondante
                vector <unsigned> tab_collonne = get_collone(sudoku, j); // la collonne correspondante
                vector < vector <unsigned> > tab_case = get_case(sudoku, i/mode, j/mode, mode); // la case correspondante
                tab_influence[i][j] = CalculInfluence( tab_ligne, tab_collonne, tab_case);
            }
        }
    }

    unsigned max=0;
    for(unsigned i=0 ; i< tab_influence.size() ; i++)
    {
        for(unsigned j=0 ; j< tab_influence[i].size() ; j++)
        {
            if(tab_influence[i][j]>max)
            {
                max = tab_influence[i][j];
                x = i;
                y = j;
            }
        }
    }
    vector <unsigned> tab_ligne = sudoku[x]; // la ligne correspondante
    vector <unsigned> tab_collonne = get_collone(sudoku, y); // la collonne correspondante
    vector < vector <unsigned> > tab_case = get_case(sudoku, x/mode, y/mode, mode); // la case correspondante
    tab_possibilites.push_back(poss_case(tab_ligne, tab_collonne, tab_case));

    if(tab_possibilites[0].size() == 0){
        retour ++;
        return sudoku;
    }

    for(unsigned k=0; tab_possibilites.size() != 0 && k<tab_possibilites[0].size() ; k++) // récursivité
    {
        vector< vector <unsigned> > sudoku_to_send = sudoku;
        sudoku_to_send[x][y] = tab_possibilites[0][k];
        sudoku_to_send = Super_resolution_propagation_contraintes6(sudoku_to_send, mode);
        if(est_total_sudoku(sudoku_to_send)) return sudoku_to_send;
    }
    return sudoku;
}
/** Résolution avec propagation de contrainte et évaluation des choix possible. Le critère est : l'état le plus influencé*/
vector< vector <unsigned> > Super_resolution_propagation_contraintes7(vector< vector <unsigned> > sudoku, unsigned mode) // max qui m'influ
{
    taille_arbre ++;
    if(est_total_sudoku(sudoku)){
        cout << endl << "Le nombre d'état et de changements : " << taille_arbre-1 << endl;
        cout << "Le nombre de retour : " << retour << endl;
        return sudoku;
        }
    vector < vector<unsigned> > cases_et_poss;
    vector < vector <unsigned> > tab_possibilites;
    vector <unsigned> tab_influence;
    vector <unsigned> tab_possibilites_y;
    vector <unsigned> tab_possibilites_x;

    for(unsigned i=0 ; i<sudoku.size(); i++)
    {
        for(unsigned j=0 ; j< sudoku[i].size() ; j++) // Parcour de toutes les cases pour en choisir les valeurs.
        {
            if(sudoku[i][j] == 0)
            {
                vector <unsigned> tab_ligne = sudoku[i]; // la ligne correspondante
                vector <unsigned> tab_collonne = get_collone(sudoku, j); // la collonne correspondante
                vector < vector <unsigned> > tab_case = get_case(sudoku, i/mode, j/mode, mode); // la case correspondante
                tab_influence.push_back(mode*mode*3 - CalculInfluence( tab_ligne, tab_collonne, tab_case));
                tab_possibilites_y.push_back(j);
                tab_possibilites_x.push_back(i);
            }
        }
    }

    unsigned max=0, position;
    for(unsigned i=0 ; i< tab_influence.size() ; i++)
    {
        if(tab_influence[i]>max && tab_influence[i]!=0)
        {
            max =tab_influence[i];
            position = i;
        }
    }
    vector <unsigned> tab_ligne = sudoku[tab_possibilites_x[position]]; // la ligne correspondante
    vector <unsigned> tab_collonne = get_collone(sudoku, tab_possibilites_y[position]); // la collonne correspondante
    vector < vector <unsigned> > tab_case = get_case(sudoku, tab_possibilites_x[position]/mode, tab_possibilites_y[position]/mode, mode); // la case correspondante
    tab_possibilites.push_back(poss_case(tab_ligne, tab_collonne, tab_case));

    if(tab_possibilites[0].size() == 0){
        retour ++;
        return sudoku;
    }

    for(unsigned k=0; tab_possibilites.size() != 0 && k<tab_possibilites[0].size() ; k++) // récursivité
    {
        vector< vector <unsigned> > sudoku_to_send = sudoku;
        sudoku_to_send[tab_possibilites_x[position]][tab_possibilites_y[position]] = tab_possibilites[0][k];
        sudoku_to_send = Super_resolution_propagation_contraintes7(sudoku_to_send, mode);
        if(est_total_sudoku(sudoku_to_send)) return sudoku_to_send;
    }
    return sudoku;
}
/** Résolution avec propagation de contrainte et évaluation des choix possible. Le critère est : une combinaison prenant le maximum d'influence subi et la maximum de possibilité de changement*/
vector< vector <unsigned> > Super_resolution_propagation_contraintes8(vector< vector <unsigned> > sudoku, unsigned mode){ // max qui m'influ + max poss
    taille_arbre ++;
    if(est_total_sudoku(sudoku)){
        cout << endl << "Le nombre d'état et de changements : " << taille_arbre-1 << endl;
        cout << "Le nombre de retour : " << retour << endl;
        return sudoku;
        }
    vector < vector<unsigned> > cases_et_poss;
    vector < vector <unsigned> > tab_possibilites;
    vector <unsigned> tab_influence;
    vector <unsigned> tab_possibilites_y;
    vector <unsigned> tab_possibilites_x;

    for(unsigned i=0 ; i<sudoku.size(); i++)
    {
        for(unsigned j=0 ; j< sudoku[i].size() ; j++) // Parcour de toutes les cases pour en choisir les valeurs.
        {
            if(sudoku[i][j] == 0)
            {
                vector <unsigned> tab_ligne = sudoku[i]; // la ligne correspondante
                vector <unsigned> tab_collonne = get_collone(sudoku, j); // la collonne correspondante
                vector < vector <unsigned> > tab_case = get_case(sudoku, i/mode, j/mode, mode); // la case correspondante
                tab_influence.push_back(mode*mode*3 - CalculInfluence( tab_ligne, tab_collonne, tab_case) + mode - poss_case(tab_ligne, tab_collonne, tab_case).size());
                tab_possibilites_y.push_back(j);
                tab_possibilites_x.push_back(i);
            }
        }
    }

    unsigned max=0, position;
    for(unsigned i=0 ; i< tab_influence.size() ; i++)
    {
        if(tab_influence[i]>max && tab_influence[i]!=0)
        {
            max =tab_influence[i];
            position = i;
        }
    }
    vector <unsigned> tab_ligne = sudoku[tab_possibilites_x[position]]; // la ligne correspondante
    vector <unsigned> tab_collonne = get_collone(sudoku, tab_possibilites_y[position]); // la collonne correspondante
    vector < vector <unsigned> > tab_case = get_case(sudoku, tab_possibilites_x[position]/mode, tab_possibilites_y[position]/mode, mode); // la case correspondante
    tab_possibilites.push_back(poss_case(tab_ligne, tab_collonne, tab_case));

    if(tab_possibilites[0].size() == 0){
        retour ++;
        return sudoku;
    }

    for(unsigned k=0; tab_possibilites.size() != 0 && k<tab_possibilites[0].size() ; k++) // récursivité
    {
        vector< vector <unsigned> > sudoku_to_send = sudoku;
        sudoku_to_send[tab_possibilites_x[position]][tab_possibilites_y[position]] = tab_possibilites[0][k];
        sudoku_to_send = Super_resolution_propagation_contraintes8(sudoku_to_send, mode);
        if(est_total_sudoku(sudoku_to_send)) return sudoku_to_send;
    }
    return sudoku;
}
/** Résolution avec propagation de contrainte et évaluation des choix possible. Le critère est : une combinaison prenant le maximum d'influence subi et la moins de possibilité de changement*/
vector< vector <unsigned> > Super_resolution_propagation_contraintes9(vector< vector <unsigned> > sudoku, unsigned mode){ // max qui m'influ - max poss
    taille_arbre ++;
    if(est_total_sudoku(sudoku)){
        cout << endl << "Le nombre d'état et de changements : " << taille_arbre-1 << endl;
        cout << "Le nombre de retour : " << retour << endl;
        return sudoku;
        }
    vector < vector<unsigned> > cases_et_poss;
    vector < vector <unsigned> > tab_possibilites;
    vector <unsigned> tab_influence;
    vector <unsigned> tab_possibilites_y;
    vector <unsigned> tab_possibilites_x;

    for(unsigned i=0 ; i<sudoku.size(); i++)
    {
        for(unsigned j=0 ; j< sudoku[i].size() ; j++) // Parcour de toutes les cases pour en choisir les valeurs.
        {
            if(sudoku[i][j] == 0)
            {
                vector <unsigned> tab_ligne = sudoku[i]; // la ligne correspondante
                vector <unsigned> tab_collonne = get_collone(sudoku, j); // la collonne correspondante
                vector < vector <unsigned> > tab_case = get_case(sudoku, i/mode, j/mode, mode); // la case correspondante
                tab_influence.push_back(mode*mode*3 - CalculInfluence( tab_ligne, tab_collonne, tab_case) + poss_case(tab_ligne, tab_collonne, tab_case).size());
                tab_possibilites_y.push_back(j);
                tab_possibilites_x.push_back(i);
            }
        }
    }

    unsigned max=0, position;
    for(unsigned i=0 ; i< tab_influence.size() ; i++)
    {
        if(tab_influence[i]>max && tab_influence[i]!=0)
        {
            max =tab_influence[i];
            position = i;
        }
    }
    vector <unsigned> tab_ligne = sudoku[tab_possibilites_x[position]]; // la ligne correspondante
    vector <unsigned> tab_collonne = get_collone(sudoku, tab_possibilites_y[position]); // la collonne correspondante
    vector < vector <unsigned> > tab_case = get_case(sudoku, tab_possibilites_x[position]/mode, tab_possibilites_y[position]/mode, mode); // la case correspondante
    tab_possibilites.push_back(poss_case(tab_ligne, tab_collonne, tab_case));

    if(tab_possibilites[0].size() == 0){
        retour ++;
        return sudoku;
    }

    for(unsigned k=0; tab_possibilites.size() != 0 && k<tab_possibilites[0].size() ; k++) // récursivité
    {
        vector< vector <unsigned> > sudoku_to_send = sudoku;
        sudoku_to_send[tab_possibilites_x[position]][tab_possibilites_y[position]] = tab_possibilites[0][k];
        sudoku_to_send = Super_resolution_propagation_contraintes9(sudoku_to_send, mode);
        if(est_total_sudoku(sudoku_to_send)) return sudoku_to_send;
    }
    return sudoku;
}
/** Résolution avec propagation de contrainte et évaluation des choix possible. Le critère est : une combinaison prenant le maximum d'influence et la maximum de possibilité de changement*/
vector< vector <unsigned> > Super_resolution_propagation_contraintes10(vector< vector <unsigned> > sudoku, unsigned mode){ // max et ajout qu m'influence
    taille_arbre ++;
    if(est_total_sudoku(sudoku)){
        cout << endl << "Le nombre d'état et de changements : " << taille_arbre-1 << endl;
        cout << "Le nombre de retour : " << retour << endl;
        return sudoku;
        }
    vector < vector<unsigned> > cases_et_poss;
    vector < vector <unsigned> > tab_possibilites;
    vector <unsigned> tab_influence;
    vector <unsigned> tab_possibilites_y;
    vector <unsigned> tab_possibilites_x;

    for(unsigned i=0 ; i<sudoku.size(); i++)
    {
        for(unsigned j=0 ; j< sudoku[i].size() ; j++) // Parcour de toutes les cases pour en choisir les valeurs.
        {
            if(sudoku[i][j] == 0)
            {
                vector <unsigned> tab_ligne = sudoku[i]; // la ligne correspondante
                vector <unsigned> tab_collonne = get_collone(sudoku, j); // la collonne correspondante
                vector < vector <unsigned> > tab_case = get_case(sudoku, i/mode, j/mode, mode); // la case correspondante
                tab_influence.push_back(CalculInfluence( tab_ligne, tab_collonne, tab_case) + mode - poss_case(tab_ligne, tab_collonne, tab_case).size());
                tab_possibilites_y.push_back(j);
                tab_possibilites_x.push_back(i);
            }
        }
    }

    unsigned max=0, position;
    for(unsigned i=0 ; i< tab_influence.size() ; i++)
    {
        if(tab_influence[i]>max && tab_influence[i]!=0)
        {
            max =tab_influence[i];
            position = i;
        }
    }
    vector <unsigned> tab_ligne = sudoku[tab_possibilites_x[position]]; // la ligne correspondante
    vector <unsigned> tab_collonne = get_collone(sudoku, tab_possibilites_y[position]); // la collonne correspondante
    vector < vector <unsigned> > tab_case = get_case(sudoku, tab_possibilites_x[position]/mode, tab_possibilites_y[position]/mode, mode); // la case correspondante
    tab_possibilites.push_back(poss_case(tab_ligne, tab_collonne, tab_case));

    if(tab_possibilites[0].size() == 0){
        retour ++;
        return sudoku;
    }

    for(unsigned k=0; tab_possibilites.size() != 0 && k<tab_possibilites[0].size() ; k++) // récursivité
    {
        vector< vector <unsigned> > sudoku_to_send = sudoku;
        sudoku_to_send[tab_possibilites_x[position]][tab_possibilites_y[position]] = tab_possibilites[0][k];
        sudoku_to_send = Super_resolution_propagation_contraintes10(sudoku_to_send, mode);
        if(est_total_sudoku(sudoku_to_send)) return sudoku_to_send;
    }
    return sudoku;
}
/** écriture résultat*/
void ecrire_fichier(vector < vector <unsigned> > sudokuBase, vector < vector <unsigned> > sudokuFinal, unsigned nb_chgments, unsigned nb_retours)
{
    ofstream fichier("test.html");
    if(fichier)
    {


        fichier << "<link rel=""stylesheet"" href=""design.css"" />" << endl;
        fichier << "<h1> Résolution du Sudoku </h1>" << endl;

        fichier << "<p> Grille de départ: </p>" << endl;

        fichier << "<table>" << endl;
        for(unsigned i=0; i<sudokuBase.size(); i++)
        {
            fichier << "<tr>";
            for(unsigned j=0 ; j<sudokuBase[i].size(); j++)
            {
                fichier << "<td>"<< sudokuBase[i][j]<<"</td>";
            }
            fichier << "</tr>";
        }
        fichier << "</table></br>" << endl;


        fichier << "<p> Grille résolue: </p>" << endl;

        fichier << "<table>" << endl;
        for(unsigned i=0; i<sudokuFinal.size(); i++)
        {
            fichier << "<tr>";
            for(unsigned j=0 ; j<sudokuFinal[i].size(); j++)
            {
                fichier << "<td>"<< sudokuFinal[i][j]<<"</td>";
            }
            fichier << "</tr>";
        }
        fichier << "</table></br>" << endl;

        fichier <<" <h1>Mesures de performance </h1>"<< endl;
        fichier <<" <p>Nombre d'états et de changements : "<< nb_chgments<<" </p>"<< endl;
        fichier <<" <p>Nombre de retours : "<< nb_retours<<" </p>"<< endl;

    }
    else
    {
        cout << "Erreur : impossible d'ouvrir le fichier" << endl;
    }

}
/** Calcul de l'influence d'un point sur le sudoku */
/** Le calcul de l'influence est simple, on compte tous les points non assigné qui ont un rapport avec le point que nous avons selectionné. Donc nous regardons la case / ligne / collonne correspondant à ce point*/
unsigned CalculInfluence(vector <unsigned> &tab_ligne,  vector <unsigned> &tab_collonne, vector < vector <unsigned> > &tab_case){
    unsigned tobereturn = 0;
    for(unsigned i=0 ; i<tab_ligne.size() ; i++){// parcours ligne et collonne
        if(tab_ligne[i] == 0) tobereturn++;
        if(tab_collonne[i] == 0) tobereturn++;
    }
    for(unsigned i=0 ; i<tab_case.size() ; i++){// parcours case
        for(unsigned j=0 ; j<tab_case.size() ; j++){
            if(tab_case[i][j] == 0) tobereturn++;
        }
    }
    return tobereturn;
}
/** Reset les variables globales*/
void ResetGlobal(){
    taille_arbre = retour = 0;
}
/** Récupère une variable global*/
unsigned GetChangement(){
    return taille_arbre;
}
/** Récupère une variable global*/
unsigned GetRetour(){
    return retour;
}

/** récupère la collonne d'un vector */
vector <unsigned> get_collone(vector< vector <unsigned> > tableau, unsigned numero_collonne)
{
    vector <unsigned> temp;
    for(unsigned i=0 ; i<tableau.size() ; i++) // On rentre toutes les valeurs de la collonne dans un tableau
    {
        temp.push_back(tableau[i][numero_collonne]);
    }
    return temp;
}
/** récupère la case dans laquel se trouve un élèment (dans un sudoku)*/
vector < vector <unsigned> > get_case(vector< vector <unsigned> > tableau, unsigned numero_ligne, unsigned numero_collonne, unsigned mode)
{
    /** On récupère la case suivant la définition du sudoku, simple parcour de tableau*/
    vector < vector < unsigned> > temp;
    vector <unsigned> temp_ligne;
    for(unsigned i=mode*numero_ligne ; i< mode*(numero_ligne+1) ; i++)
    {
        temp_ligne.clear();
        for(unsigned j=mode*numero_collonne ; j< mode*(numero_collonne+1) ; j++)
        {

            temp_ligne.push_back(tableau[i][j]);
        }
        temp.push_back(temp_ligne);
    }
    return temp;
}
/** Vérifie si le sudoku est complet */
bool est_total_sudoku (vector< vector <unsigned> > sudoku)
{
    for(unsigned i=0 ; i<sudoku.size() ; i++)// On parcours notre sudoku pour vérifier que toutes les valeurs sont assigné
    {
        for(unsigned j=0 ; j<sudoku[i].size() ; j++)
        {
            if(sudoku[i][j] == 0) return false;
        }
    }
    return true;
}
/** Affiche un sudoku (Fonction de test)*/
/** N'est plus utilisé */
void affichage_sudoku(vector< vector <unsigned> > sudoku)
{
    for(unsigned i=0 ; i<sudoku.size() ; i++)
    {
        for(unsigned j=0 ; j<sudoku[i].size() ; j++)
        {
            cout << sudoku[i][j] << " ";
        }
        cout << endl;
    }
}
/** Ecritue de la solution*/
void ecrire_fichier(vector < vector <unsigned> > sudokuBase, vector < vector <unsigned> > sudokuFinal, unsigned nb_chgments, unsigned nb_retours,unsigned tmp_exec)
{
    ofstream fichier("test.html");
    if(fichier)
    {


        fichier << "<link rel=""stylesheet"" href=""design.css"" />" << endl;
        fichier << "<h1> Résolution du Sudoku </h1>" << endl;

        fichier << "<p> Grille de départ: </p>" << endl;

        fichier << "<table>" << endl;
        for(unsigned i=0; i<sudokuBase.size(); i++)
        {
            fichier << "<tr>";
            for(unsigned j=0 ; j<sudokuBase[i].size(); j++)
            {
                fichier << "<td>"<< sudokuBase[i][j]<<"</td>";
            }
            fichier << "</tr>";
        }
        fichier << "</table></br>" << endl;


        fichier << "<p> Grille résolue: </p>" << endl;

        fichier << "<table>" << endl;
        for(unsigned i=0; i<sudokuFinal.size(); i++)
        {
            fichier << "<tr>";
            for(unsigned j=0 ; j<sudokuFinal[i].size(); j++)
            {
                fichier << "<td>"<< sudokuFinal[i][j]<<"</td>";
            }
            fichier << "</tr>";
        }
        fichier << "</table></br>" << endl;

        fichier <<" <h1>Mesures de performance </h1>"<< endl;
        fichier <<" <p>Nombre d'états et de changements : "<< nb_chgments<<" </p>"<< endl;
        fichier <<" <p>Nombre de retours : "<< nb_retours<<" </p>"<< endl;
		fichier <<" <p>Temps d'exécution : "<< tmp_exec<<" ms </p>"<< endl;

    }
    else
    {
        cout << "Erreur : impossible d'ouvrir le fichier" << endl;
    }

}
/** Crée un sudoku totalement vide*/
/** Allocation simple */
vector < vector <unsigned> > creation_sudoku_vide(unsigned mode)
{
    vector < vector <unsigned> > tobereturn;
    vector <unsigned> temp;
    temp.resize(mode*mode,0);
    for(unsigned i=0 ; i<mode*mode ; i++)
    {
        tobereturn.push_back(temp);
    }
    return tobereturn;
}
/** Chargement d'un sudoku à partir d'un fichier */
/** Lecture simple, n'a pas d'impact sur la résolution*/
vector< vector<unsigned> > lecture_sudoku(string nom, unsigned taille)
{
    ifstream fichier(nom.c_str(), ios::in);

    vector<vector<unsigned> > sudoku = creation_sudoku_vide(taille);
    vector<unsigned> test;
    int a;
    if(fichier)
    {
        for(unsigned i=0 ; i<taille*taille ; i++)
        {
            test=sudoku.at(i);
            for(unsigned j=0 ; j<taille*taille ; j++)
            {
                fichier >> a;
                test[j] = a;
            }
            sudoku.at(i) = test;
        }
         fichier.close();
    }
    else  // sinon
            cerr << "Impossible d'ouvrir le fichier !" << endl;

    fichier.close();
    return sudoku;
}