/**
 * @file code.c
 * @author Eliott
 * @author ESBELIN
 * @version finale
 * @date 10 avril 2025
 * @brief programme C pour résolution suguru
 */
 
#include <stdlib.h>
#include <stdio.h>
#include <string.h>

/**
 * @struct cpt
 * @brief type compteur de boucle
 */

typedef int cpt;
void afficher_grille(int **grille, int h, int w);

//############################################ Strucuture pour les choix au fur et à mesure de la résolution ############################################

/**
 * @struct choix
 * @brief type choix
 */

typedef struct {
    int indice[2];
    int tab[6];
    int nombre;
} choix;

//############################################ Déplacements: haut, bas, gauche, droite ############################################
int dx[] = {-1, 1, 0, 0};
int dy[] = {0, 0, -1, 1};

//############################################ Détection des cages et attribution d'identifiants uniques ############################################

/**
 * @fn void creer_cages_identifiants(char **cage, int h, int w, int **cage_identifiant)
 * @brief crée une grille rempli avec les numéros de cages à tous les indices
 * @param cage tableau de chaines de caractères
 * @param h entier naturel
 * @param w entier naturel
 * @param cage_identifiant tableau 2 dimensions d'entiers naturels
 */

void creer_cages_identifiants(char **cage, int h, int w, int **cage_identifiant) {
    int prochain_id = 0;
    cpt i,j;
    for (i = 0; i < h; i++) {
        for (j = 0; j < w; j++) {
            cage_identifiant[i][j] = -1;
        }
    }
    cpt a,b,c,d,e;
    for (a = 0; a < h; a++) {
        for (b = 0; b < w; b++) {
            if (cage_identifiant[a][b] == -1) {  
                char cage_type = cage[a][b];
                cage_identifiant[a][b] = prochain_id;

                int **queue = malloc(h * w * sizeof(int*));
                for (c = 0; c < h * w; c++) {
                    queue[c] = malloc(2 * sizeof(int));
                }

                int front = 0, rear = 0;
                queue[rear][0] = a;
                queue[rear++][1] = b;

                while (front < rear) {
                    int x = queue[front][0], y = queue[front++][1];

                    for (int d = 0; d < 4; d++) {
                        int nx = x + dx[d], ny = y + dy[d];

                        if (nx >= 0 && nx < h && ny >= 0 && ny < w &&
                            cage_identifiant[nx][ny] == -1 && cage[nx][ny] == cage_type) {
                            cage_identifiant[nx][ny] = prochain_id;
                            queue[rear][0] = nx;
                            queue[rear++][1] = ny;
                        }
                    }
                }

                for (e = 0; e < h * w; e++) {
                    free(queue[e]);
                }
                free(queue);

                prochain_id++;
            }
        }
    }
}

//############################################ Classification des indices par cages ############################################

/**
 * @fn void classifier_indices_par_cages(int **cage_identifiant, int h, int w, int ****tab, int *nombre_cages, int **cage_sizes)
 * @brief crée un tableau rangé par indice de cages avec tout les indices des cases présents dans la cage
 * @param cage_identifiant tableau 2 dimensions d'entiers naturels
 * @param h entier naturel
 * @param w entier naturel
 * @param tab un tableau à 3 dimensions d'entiers naturels
 * @param nombres_cages un entier naturel
 * @param cages_sizes un tableau à 2 dimension d'entiers naturels
 */

void classifier_indices_par_cages(int **cage_identifiant, int h, int w, int ****tab, int *nombre_cages, int **cage_sizes) {
    int max_cage_id = 0;
    cpt i,j;
    for (i = 0; i < h; i++) {
        for (j = 0; j < w; j++) {
            if (cage_identifiant[i][j] > max_cage_id) {
                max_cage_id = cage_identifiant[i][j];
            }
        }
    }
    *nombre_cages = max_cage_id + 1;

    *cage_sizes = malloc((*nombre_cages) * sizeof(int));
    cpt k;
    for (k = 0; k < *nombre_cages; k++) {
        (*cage_sizes)[k] = 0;
    }
    cpt l,m;
    for (l = 0; l < h; l++) {
        for (m = 0; m < w; m++) {
            int cage_id = cage_identifiant[l][m];
            (*cage_sizes)[cage_id]++;
        }
    }

    *tab = malloc((*nombre_cages) * sizeof(int**));
    cpt n,o;
    for (n = 0; n < *nombre_cages; n++) {
        (*tab)[n] = malloc((*cage_sizes)[n] * sizeof(int*));
        for (o = 0; o < (*cage_sizes)[n]; o++) {
            (*tab)[n][o] = malloc(2 * sizeof(int)); 
        }
    }

    int *cage_counter = malloc(*nombre_cages * sizeof(int));
    cpt p;
    for (p = 0; p < *nombre_cages; p++) {
        cage_counter[p] = 0;
    }
    cpt q,r;
    for (q = 0; q < h; q++) {
        for (r = 0; r < w; r++) {
            int cage_id = cage_identifiant[q][r];
            (*tab)[cage_id][cage_counter[cage_id]][0] = q;
            (*tab)[cage_id][cage_counter[cage_id]][1] = r;
            cage_counter[cage_id]++;
        }
    }

    free(cage_counter);
}

//############################################## Possibilité de remplissage pour une case donnée ##############################################

/**
 * @fn void possible(int ligne, int colonne, int x, int y, int cage[], int** grille, int*** tab, int** cage_identifiant, int possibilite[])
 * @brief renvoie les possibilités de chiffres dans une case
 * @param ligne entier naturel
 * @param colonne entier naturel
 * @param x entier naturel
 * @param y entier naturel
 * @param cage un tableau d'entiers naturels
 * @param grille un tableau à 2 dimensions d'entiers naturels
 * @param tab un tableau à 3 dimensions d'entiers naturels
 * @param cage_identifiant un tableau à 2 dimensions d'entiers naturels
 * @param possibilite un tableau d'entiers naturels
 */

void possible(int ligne, int colonne, int x, int y, int cage[], int** grille, int*** tab, int** cage_identifiant, int possibilite[]) {
    if (grille[x][y] == 0) {
        cpt i;
        for (i = 0; i < 6; i++) {
            possibilite[i] = i + 1;
        }
        cpt j, k;
        for (j = -1; j < 2; j++) {
            for (k = -1; k < 2; k++) {
                if(x + j < ligne && y + k < colonne && x+j>-1 && y+k>-1){
                    int val = grille[x + j][y + k];
                    if (val < 7) {
                        possibilite[val - 1] = 0;
                    }
                }
            }
        }
        int tailleCage = cage[cage_identifiant[x][y]];
        cpt l;
        for (l = tailleCage; l < 6; l++) {
            possibilite[l] = 0;
        }
        cpt m;
        for (m = 0; m < tailleCage; m++) {
            int a = tab[cage_identifiant[x][y]][m][0];
            int b = tab[cage_identifiant[x][y]][m][1];
            int val = grille[a][b];
            if (val < 7) {
                possibilite[val - 1] = 0;
            }
        }
    } 
    else {
        cpt i;
        for (i = 0; i < 6; i++) {
            possibilite[i] = 0;
        }
    }
}

//############################################## Résolution du suguru ##############################################

/**
 * @fn int resoudre(int ligne, int colonne, int x, int y, choix choisi[], int resolu[][2], int cage[], int** grille, int*** tab, int** cage_identifiant, int numero, int caseRempli, int decision)
 * @brief complète la grille de suguru
 * @param ligne entier naturel
 * @param colonne entier naturel
 * @param x entier naturel
 * @param y entier naturel
 * @param choisi un tableau de type choix
 * @param resolu un tableau à 2 dimensions d'entiers naturels
 * @param cage un tableau d'entier naturel
 * @param grille un tableau à 2 dimensions d'entiers naturels
 * @param tab un tableau à 3 dimensions d'entiers naturels
 * @param cage_identifiant un tableau à 2 dimensions d'entiers naturels
 * @param numero entier naturel
 * @param caseRempli entier naturel
 * @param decision entier naturel
 * @return 0 lorsque la grille est complété entièrement
 */
 
int resoudre(int ligne, int colonne, int x, int y, choix choisi[], int resolu[][2], int cage[], int** grille, int*** tab, int** cage_identifiant, int numero, int caseRempli, int decision) {
    if (caseRempli == ligne * colonne) {
        return 0;
    }
    int possibilite[6]={0};
    possible(ligne, colonne, x, y, cage, grille,tab,cage_identifiant,possibilite);
    int nombrePossibilite = 0;
    int valeur;
    cpt i;
    for (i = 0; i < 6; i++) {
        if (possibilite[i] != 0) {
            nombrePossibilite++;
            valeur = possibilite[i];
        }
    }
    if (nombrePossibilite == 0) {
        cpt i;
        for(i=numero-1;resolu[i][0]!=choisi[decision-1].indice[0] && resolu[i][1]!=choisi[decision-1].indice[1];i--){
            grille[resolu[i][0]][resolu[i][1]]=0;
            caseRempli--;
        }
        int nouvellePossibilite[6]={0};
        possible(ligne, colonne, choisi[decision-1].indice[0], choisi[decision-1].indice[1], cage, grille,tab,cage_identifiant,nouvellePossibilite);
        int nouveauNombrePossibilite = 0;
        cpt j;
        for (j = 0; j < 6; j++) {
            if (nouvellePossibilite[j] != 0) {
                nouveauNombrePossibilite++;
            }
        }
        if(choisi[decision-1].nombre!=nouveauNombrePossibilite){
            int nouvelleValeur=0;
            cpt j,k;
            for(j=0;j<6 && nouvelleValeur==0;j++){
                if(nouvellePossibilite[j]!=0){
                    int trouve=0;
                    for(k=0;k<choisi[decision-1].nombre && trouve==0;k++){
                        if(choisi[decision-1].tab[k]==nouvellePossibilite[j]){
                            trouve=1;
                        }
                    }
                    if(trouve==0){
                        nouvelleValeur=nouvellePossibilite[j];
                    }
                }
            }
            grille[choisi[decision-1].indice[0]][choisi[decision-1].indice[1]]=nouvelleValeur;
            choisi[decision-1].tab[choisi[decision-1].nombre]=nouvelleValeur;
            choisi[decision-1].nombre++;
            cpt l;
            int a, b;
            int x=choisi[decision-1].indice[0],y=choisi[decision-1].indice[1];
            int trouve = 0;
            for (l = 0; l < cage[cage_identifiant[x][y]] && trouve == 0; l++) {
                int tmp_x = tab[cage_identifiant[x][y]][l][0];
                int tmp_y = tab[cage_identifiant[x][y]][l][1];
                if (grille[tmp_x][tmp_y] == 0) {
                    a = tmp_x;
                    b = tmp_y;
                    trouve = 1;
                }
            }
            if (trouve == 0) {
                cpt k, l, m;
                for (k = 0; k < 20 && trouve == 0; k++) {
                    for (l = -1 - k; l < 1 + k && trouve == 0; l++) {
                        for (m = -1 - k; m < 1 + k && trouve == 0; m++) {
                            if (x + l < ligne && y + m < colonne && x+l>-1 && y+m>-1 && grille[x + l][y + m] == 0) {
                                a = x + l;
                                b = y + m;
                                trouve = 1;
                            }
                        }
                    }
                }
            }
            resoudre(ligne, colonne, a, b, choisi, resolu, cage, grille, tab, cage_identifiant, i+1, caseRempli, decision);
        }
        else{
            int nouvellePossibilite[6]={0};
            possible(ligne, colonne, choisi[decision-2].indice[0], choisi[decision-2].indice[1], cage, grille,tab,cage_identifiant,nouvellePossibilite);
            int nouveauNombrePossibilite = 0;
            cpt j;
            for (j = 0; j < 6; j++) {
                if (nouvellePossibilite[j] != 0) {
                    nouveauNombrePossibilite++;
                }
            }
            cpt k=i-1;
            j=2;
            while(nouveauNombrePossibilite==choisi[decision-j].nombre){
                for(;resolu[k][0]!=choisi[decision-j].indice[0] && resolu[k][1]!=choisi[decision-j].indice[1];k--){
                    grille[resolu[k][0]][resolu[k][1]]=0;
                    caseRempli--;
                }
                choisi[decision-j].nombre=0;
                choisi[decision-j].indice[0]=0;
                choisi[decision-j].indice[1]=0;
                cpt m;
                for(m=0;choisi[decision-j].tab[m]!=0;m++){
                    choisi[decision-j].tab[m]=0;
                }
                j++;
                int nouvellePossibilite[6]={0};
                possible(ligne, colonne, choisi[decision-j].indice[0], choisi[decision-j].indice[1], cage, grille,tab,cage_identifiant,nouvellePossibilite);
                int nouveauNombrePossibilite = 0;
                cpt l;
                for (l = 0; l < 6; l++) {
                    if (nouvellePossibilite[l] != 0) {
                        nouveauNombrePossibilite++;
                    }
                }
            }
            int nouvelleValeur=0;
            cpt m,n;
            for(m=0;m<6 && nouvelleValeur==0;m++){
                if(nouvellePossibilite[m]!=0){
                    int trouve=0;
                    for(n=0;n<choisi[decision-j+1].nombre && trouve==0;n++){
                        if(choisi[decision-j+1].tab[n]==nouvellePossibilite[m]){
                            trouve=1;
                        }
                    }
                    if(trouve==0){
                        nouvelleValeur=nouvellePossibilite[m];
                    }
                }
            }
            grille[choisi[decision-j+1].indice[0]][choisi[decision-j+1].indice[1]]=nouvelleValeur;
            choisi[decision-j+1].tab[choisi[decision-j+1].nombre]=nouvelleValeur;
            choisi[decision-j+1].nombre++;
            cpt l;
            int a, b;
            int x=choisi[decision-j+1].indice[0],y=choisi[decision-j+1].indice[1];
            int trouve = 0;
            for (l = 0; l < cage[cage_identifiant[x][y]] && trouve == 0; l++) {
                int tmp_x = tab[cage_identifiant[x][y]][l][0];
                int tmp_y = tab[cage_identifiant[x][y]][l][1];
                if (grille[tmp_x][tmp_y] == 0) {
                    a = tmp_x;
                    b = tmp_y;
                    trouve = 1;
                }
            }
            if (trouve == 0) {
                cpt k, l, m;
                for (k = 0; k < 20 && trouve == 0; k++) {
                    for (l = -1 - k; l < 1 + k && trouve == 0; l++) {
                        for (m = -1 - k; m < 1 + k && trouve == 0; m++) {
                            if (x + l < ligne && y + m < colonne && x+l>-1 && y+m>-1 && grille[x + l][y + m] == 0) {
                                a = x + l;
                                b = y + m;
                                trouve = 1;
                            }
                        }
                    }
                }
            }
            resoudre(ligne, colonne, a, b, choisi, resolu, cage, grille, tab, cage_identifiant, k+1, caseRempli, decision-j+1);
        }
    }
    else if (nombrePossibilite == 1) {
        grille[x][y] = valeur;
        resolu[numero][0]=x;
        resolu[numero][1]=y;
        cpt j;
        int a, b;
        int trouve = 0;
        for (j = 0; j < cage[cage_identifiant[x][y]] && trouve == 0; j++) {
            int tmp_x = tab[cage_identifiant[x][y]][j][0];
            int tmp_y = tab[cage_identifiant[x][y]][j][1];
            if (grille[tmp_x][tmp_y] == 0) {
                a = tmp_x;
                b = tmp_y;
                trouve = 1;
            }
        }
        if (trouve == 0) {
            cpt k, l, m;
            for (k = 0; k < 20 && trouve == 0; k++) {
                for (l = -1 - k; l < 1 + k && trouve == 0; l++) {
                    for (m = -1 - k; m < 1 + k && trouve == 0; m++) {
                        if (x + l < ligne && y + m < colonne && x+l>-1 && y+m>-1 && grille[x + l][y + m] == 0) {
                            a = x + l;
                            b = y + m;
                            trouve = 1;
                        }
                    }
                }
            }
        }
        resoudre(ligne, colonne, a, b, choisi, resolu, cage, grille, tab, cage_identifiant, numero + 1, caseRempli + 1, decision);
    } 
    else {
        grille[x][y] = valeur;
        resolu[numero][0]=x;
        resolu[numero][1]=y;
        choisi[decision].tab[0] = valeur;
        choisi[decision].tab[1] = 0;
        choisi[decision].indice[0] = x;
        choisi[decision].indice[1] = y;
        choisi[decision].nombre=1;
        cpt j;
        int a, b;
        int trouve = 0;
        for (j = 0; j < cage[cage_identifiant[x][y]] && trouve == 0; j++) {
            int tmp_x = tab[cage_identifiant[x][y]][j][0];
            int tmp_y = tab[cage_identifiant[x][y]][j][1];
            if (grille[tmp_x][tmp_y] == 0) {
                a = tmp_x;
                b = tmp_y;
                trouve = 1;
            }
        }
        if (trouve == 0) {
            cpt k, l, m;
            for (k = 0; k < 20 && trouve == 0; k++) {
                for (l = -1 - k; l < 1 + k && trouve == 0; l++) {
                    for (m = -1 - k; m < 1 + k && trouve == 0; m++) {
                        if (x + l < ligne && y + m < colonne && x+l>-1 && y+m>-1 && grille[x + l][y + m] == 0) {
                            a = x + l;
                            b = y + m;
                            trouve = 1;
                        }
                    }
                }
            }
        }
        resoudre(ligne, colonne, a, b, choisi, resolu, cage, grille, tab, cage_identifiant, numero + 1, caseRempli + 1, decision + 1);
    }
    return 0;
}

//############################################ Affichage de la grille ############################################

/**
 * @fn void afficher_grille(int **grille, int h, int w)
 * @brief affiche la grille
 * @param grille un tableau à 2 dimensions d'entiers naturels
 * @param h entier naturel
 * @param w entier naturel
 */

void afficher_grille(int **grille, int h, int w){
    cpt i,j;
    for(i=0;i<h;i++){
        for(j=0;j<w;j++){
            printf("%d",grille[i][j]);
        }
        printf("\n");
    }
}

//############################################ Affichage des indices classés par cage ############################################

/**
 * @fn void afficher_indices_par_cages(int ***tab, int nombre_cages, int *cage_sizes)
 * @brief affiche tous les indices des cases d'une même cage
 * @param tab un tableau à 3 dimensions d'entiers naturels
 * @param nombres_cages entier naturel
 * @param cages_sizes un tableau d'entiers naturels
 */

void afficher_indices_par_cages(int ***tab, int nombre_cages, int *cage_sizes) {
    printf("\nIndices classés par cages :\n");
    cpt i,j;
    for (i = 0; i < nombre_cages; i++) {
        printf("Cage %d:\n", i);
        for (j = 0; j < cage_sizes[i]; j++) {
            printf("  (%d, %d)\n", tab[i][j][0], tab[i][j][1]);
        }
    }
}

//############################################ Affichage des identifiants de cage ############################################

/**
 * @fn void afficher_cages(int **cage_identifiant, int h, int w)
 * @brief affiche la grille des cages
 * @param cage_identifiant un tableau à 2 dimensions d'entiers naturels
 * @param h entier naturel
 * @param w entier naturel
 */

void afficher_cages(int **cage_identifiant, int h, int w) {
    printf("\nIdentifiants des cages :\n");
    cpt i,j;
    for (i = 0; i < h; i++) {
        for (j = 0; j < w; j++) {
            printf("%d ", cage_identifiant[i][j]);
        }
        printf("\n");
    }
}

int main() {
    int w, h;                                                //Dimension de la grille
    scanf("%d%d", &w, &h); fgetc(stdin);
    
//############################################ Création des tableaux à 2 dimensions ############################################
    
    char **cage = malloc(sizeof(char*) * h);                 //Contient les lettres des cages de la grille de suguru
    int **cage_identifiant = malloc(sizeof(int*) * h);       //Contient les numéros des cages de la grille de suguru
    int ** grille=malloc(sizeof(int*)*h);                    //Contient la grille de suguru
    cpt i;
    for (i = 0; i < h; i++) {
        cage[i] = malloc(sizeof(char) * w);
        cage_identifiant[i] = malloc(sizeof(int) * w);
        grille[i]=malloc(sizeof(int)*w);
    }

//############################################ Remplissage des tableaux à 2 dimensions ############################################
    cpt j,k;
    for (j = 0; j < h; j++) {
        char line[60];
        scanf("%[^\n]", line); fgetc(stdin);
        for (k= 0; k < w * 3; k += 3) {
            cage[j][k / 3] = line[k];
            if(line[k+1]!='.'){
                grille[j][k/3]=line[k+1]-'0';
            }
            else{
                grille[j][k/3]=0;
            }
        }
    }

//############################################ Création et remplissage des tableaux concernant les cages ############################################

    creer_cages_identifiants(cage, h, w, cage_identifiant);
    int ***tab;
    int nombre_cages;
    int *cage_sizes;
    classifier_indices_par_cages(cage_identifiant, h, w, &tab, &nombre_cages, &cage_sizes);

//############################################ Affichages ############################################
    
    /*afficher_grille(grille,h,w);
    afficher_cages(cage_identifiant, h, w);
    afficher_indices_par_cages(tab, nombre_cages, cage_sizes);*/

//############################################ Test appel à la fonction possible ############################################

    /*int possibilite[6]={0};
    possible(h,w,1,0,cage_sizes,grille,tab,cage_identifiant,possibilite);

    cpt l;
    printf("Les différents chiffres possibles pour l'indice (1,0): ");
    for(l=0;l<6;l++){
        printf("%d, ",possibilite[i]);
    }
    puts("");*/

//############################################ Résolution du suguru ############################################

    choix decision[100];
    int casePrecedente[400][2];
    int caseRempli=0;
    cpt m,n;
    for(m=0;m<h;m++){
        for(n=0;n<w;n++){
            if(grille[m][n]!=0){
                caseRempli++;
            }
        }
    }
    resoudre(h,w,0,0,decision,casePrecedente,cage_sizes,grille,tab,cage_identifiant,0,caseRempli,0);
    afficher_grille(grille,h,w);

//############################################ Libération de la mémoire allouée ############################################

    cpt o,p;
    for (o = 0; o < nombre_cages; o++) {
        for (p = 0; p < cage_sizes[o]; p++) {
            free(tab[o][p]);
        }
        free(tab[o]);
    }
    free(tab);
    free(cage_sizes);
    cpt q;
    for (q = 0; q < h; q++) {
        free(cage[q]);
        free(cage_identifiant[q]);
        free(grille[q]);
    }
    free(cage);
    free(cage_identifiant);
    free(grille);

    return 0;
}