#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

#define N 9 // Taille du Sudoku

int sudoku_original[N][N] = {
        {8, 0, 4, 9, 0, 3, 0, 7, 1},
        {6, 3, 5, 8, 0, 7, 0, 2, 4},
        {9, 1, 9, 0, 2, 4, 0, 5, 0},
        {0, 8, 7, 0, 9, 1, 3, 0, 6},
        {1, 0, 0, 7, 3, 6, 0, 0, 9},
        {3, 0, 6, 4, 8, 0, 2, 1, 0},
        {0, 6, 0, 5, 4, 0, 7, 3, 8},
        {4, 7, 0, 3, 0, 2, 1, 9, 5},
        {9, 5, 0, 1, 0, 8, 4, 0, 2}
};

int sudoku_resolu[N][N] = {
        {8, 0, 4, 9, 0, 3, 0, 7, 1},
        {6, 3, 5, 8, 0, 7, 0, 2, 4},
        {9, 1, 9, 0, 2, 4, 0, 5, 0},
        {0, 8, 7, 0, 9, 1, 3, 0, 6},
        {1, 0, 0, 7, 3, 6, 0, 0, 9},
        {3, 0, 6, 4, 8, 0, 2, 1, 0},
        {0, 6, 0, 5, 4, 0, 7, 3, 8},
        {4, 7, 0, 3, 0, 2, 1, 9, 5},
        {9, 5, 0, 1, 0, 8, 4, 0, 2}
};



extern int sudoku_resolu[N][N]; // Déclaration d'une variable globale pour le sudoku résolu, utilisable dans d'autres fichiers.
extern int sudoku_original[N][N]; // Déclaration d'une variable globale pour le sudoku original, utilisable dans d'autres fichiers.








// Déclaration des tableaux globaux pour le sudoku original et résolu.
extern int sudoku_resolu[N][N];
extern int sudoku_original[N][N];

// Déclarations des fonctions


void afficherGrille(int grille[N][N], int posX, int posY);
bool estValideDansLigne(int ligne, int valeur);
bool estValideDansColonne(int colonne, int valeur);
bool estValideDansBloc(int ligneBloc, int colonneBloc, int valeur);
bool estValide(int ligne, int colonne, int valeur);
bool resoudre(int ligne, int colonne, bool visualiser, bool dessiner);




//Fonctions 


// Définit une fonction pour afficher la grille de sudoku, prenant une grille et les positions X et Y comme arguments.

void afficherGrille(int grille[N][N], int posX, int posY)

{
    
    for (int ligne = 0; ligne < N; ligne++)// Boucle sur chaque ligne de la grille.
        
    {
      
        if (ligne % 3 == 0)  // Imprime une ligne vide tous les 3 lignes pour structurer le sudoku visuellement.
        
        {
            printf("\n");
        }
       
        for (int colonne = 0; colonne < N; colonne++) // Boucle sur chaque colonne de la ligne actuelle.
            
        {
           
            if (colonne % 3 == 0) // Imprime un espace tous les 3 colonnes pour structurer le sudoku visuellement.
            {
                printf(" ");
            }
     
            bool presentDansOriginal = grille[ligne][colonne] == sudoku_original[ligne][colonne];       // Détermine si le nombre actuel est présent dans le sudoku original à la même position.
            
         
            printf("\x1b[32m");   // Définit la couleur du texte en vert pour tous les nombres.
            
            if(ligne == posX && colonne == posY)// Change l'arrière-plan en blanc et le texte en rouge si on est à la position spécifiée par posX et posY.
            
            {
                printf("\x1b[47m\x1b[31m");
            }
            
            if (presentDansOriginal) // Change la couleur du texte en bleu si le nombre est présent dans le sudoku original.
            
            {
                printf("\x1b[34m");
            }
            // Imprime le nombre avec la couleur de texte et/ou d'arrière-plan spécifiée, puis réinitialise les couleurs.
            printf("%d\x1b[0m", grille[ligne][colonne]);
        }
       
        printf("\n"); // Passe à une nouvelle ligne après avoir imprimé toutes les colonnes d'une ligne.
    }
   
    printf("\n\n\n"); // Ajoute des lignes vides après avoir imprimé toute la grille pour l'espacement.
}


// Définit une fonction pour vérifier si une valeur est valide dans une ligne spécifique du sudoku résolu.


bool estValideDansLigne(int ligne, int valeur) {
    // Parcourt chaque colonne de la ligne donnée.
    for (int j = 0; j < N; j++) {
        // Si la valeur est trouvée dans la ligne, retourne false (indiquant que la valeur n'est pas valide).
        if (sudoku_resolu[ligne][j] == valeur) {
            return false;
        }
    }
    // Si la valeur n'est pas trouvée dans la ligne, retourne true (indiquant que la valeur est valide).
    return true;
}



// Définit une fonction pour vérifier si une valeur est valide dans une colonne spécifique du sudoku résolu.
bool estValideDansColonne(int colonne, int valeur) 

{
    // Parcourt chaque ligne de la colonne donnée.
    for (int i = 0; i < N; i++) 
    
    {
        // Si la valeur est trouvée dans la colonne, retourne false (indiquant que la valeur n'est pas valide).
        if (sudoku_resolu[i][colonne] == valeur) {
            return false;
        }
    }
    // Si la valeur n'est pas trouvée dans la colonne, retourne true (indiquant que la valeur est valide).
    return true;
}


// Vérifie si une valeur donnée est valide dans un bloc 3x3 spécifique du sudoku résolu.
bool estValideDansBloc(int ligneBloc, int colonneBloc, int valeur) {
    // Boucle sur les 3 lignes du bloc.
    for (int i = 0; i < 3; i++) {
        // Boucle sur les 3 colonnes du bloc.
        for (int j = 0; j < 3; j++) {
            // Si la valeur est trouvée dans le bloc, retourne false (indiquant que la valeur n'est pas valide dans le bloc).
            if (sudoku_resolu[ligneBloc + i][colonneBloc + j] == valeur) {
                return false;
            }
        }
    }
    // Si la valeur n'est pas trouvée dans le bloc, retourne true (indiquant que la valeur est valide dans le bloc).
    return true;
}


// Vérifie si une valeur donnée est valide à la position spécifiée (ligne, colonne) du sudoku résolu.
bool estValide(int ligne, int colonne, int valeur) {
    // Retourne true si la valeur est valide dans la ligne spécifiée,
    // valide dans la colonne spécifiée, et valide dans le bloc 3x3 correspondant.
    return estValideDansLigne(ligne, valeur) &&
           estValideDansColonne(colonne, valeur) &&
           estValideDansBloc(ligne - ligne % 3, colonne - colonne % 3, valeur);
}



// Définit une fonction pour résoudre le sudoku, avec les paramètres ligne, colonne, visualiser (pour afficher les étapes), et dessiner (pour déterminer si l'affichage doit être effectué).


bool resoudre(int ligne, int colonne, bool visualiser, bool dessiner) 

{
    
    if (colonne > 8)// Vérifie si la colonne dépasse la grille du sudoku, ce qui indique la fin d'une ligne.
    
    {
        colonne = 0; // Réinitialise la colonne à la première colonne de la prochaine ligne.
        
        ligne += 1; // Passe à la ligne suivante.
       
        if (ligne > 8)  // Vérifie si la ligne dépasse la grille, ce qui indique que le sudoku est résolu.
        {
            
            if (!visualiser) // Si le mode visualiser est désactivé et le mode dessiner est activé, affiche la grille résolue.
            
            {
                if (dessiner)
                {
                    afficherGrille(sudoku_resolu, ligne, colonne);
                }
            }
            
            return true;// Retourne true pour indiquer que le sudoku est résolu.
        }
    }

   
    if (sudoku_resolu[ligne][colonne] != 0)  // Vérifie si la cellule actuelle est déjà remplie avec une valeur non nulle.
    
    {
        
        if (resoudre(ligne, colonne + 1, visualiser, dessiner)) // Tente de résoudre pour la cellule suivante. Si réussi, retourne true.
        
        {
            return true;
        }
    } else {
       
        for (int val = 1; val <= 9; val++)  // Si la cellule actuelle est vide, tente de placer des valeurs de 1 à 9.
            
        {
            
            if (estValide(ligne, colonne, val))// Vérifie si la valeur est valide à la position actuelle.
            
            {
                sudoku_resolu[ligne][colonne] = val; // Place la valeur dans la cellule.
                
                if (visualiser)// Si le mode visualiser est activé, affiche chaque tentative de placement.
                
                {
                    afficherGrille(sudoku_resolu, ligne, colonne);
                }
                
                if (resoudre(ligne, colonne + 1, visualiser, dessiner)) // Tente de résoudre à partir de la cellule suivante avec la nouvelle valeur placée.
                
                {
                    return true; // Retourne true si le sudoku est résolu avec la valeur placée.
                }
               
                sudoku_resolu[ligne][colonne] = 0; // Si le placement de la valeur n'a pas mené à une solution, remet la cellule à 0.
                
               
                if (visualiser) // Si le mode visualiser est activé, affiche la grille après avoir remis la cellule à 0.
                
                {
                    afficherGrille(sudoku_resolu, ligne, colonne);
                }
            }
        }
    }
    // Retourne false si aucune valeur valide ne peut être placée dans la cellule actuelle, nécessitant un backtracking.
    return false;
}

int main() {
    afficherGrille(sudoku_resolu, 10, 10);
    resoudre(0, 0, true, true);
    return 0;
}