Rapport : Killer sudoku solver

56..1..2. aabbccdde
..72..68. afghhiide
..2.87.15 jfggklmme
......3.9 jjgnklopp
.7....2.. qqgnooorr
9.634.8.. stuuvwwxx
2.9..8... stuuvvwyz
..41.2... sAuuByyyz
.8.4...3. CADDBEEFF
a=12 b=17 c=4 d=14 e=15 f=13 g=19 h=7 i=10 j=16 k=10 l=13 m=10 n=15 o=15 p=13 q=11 r=11 s=18 t=3 u=28 v=15 w=20 x=8 y=22 z=12 A=11 B=13 C=6 D=9 E=10 F=5

123874569
567932184
849651237
916247853
358196472
472385916
291768345
685423791
734519628

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


#define TAILLE 9

#define MAX_CAGES 52
#define MAX_COORDS_CAGE 9

typedef struct {
    int taille; // Nombre de d'element dans la cage
    int somme; // Somme de la cage
    int *coords[MAX_COORDS_CAGE];   // tableau de pointeur vers les coordonnees des cases de la cage
} cage_t;

typedef struct {
    cage_t cages[MAX_CAGES];
} liste_cages_t;

int lettre_to_index(char lettre) {
    return lettre >= 'a' ? lettre - 'a' : lettre - 'A' + 26;
}

void init_liste_cages(liste_cages_t *ls_cages) {
    for (int i = 0; i < MAX_CAGES; i++) {
        ls_cages->cages[i].taille = 0;
    }
}

void ajouter_coord_cage(liste_cages_t *ls_cages, int num_cage, int *coord) {
    ls_cages->cages[num_cage].coords[ls_cages->cages[num_cage].taille] = coord;
    ls_cages->cages[num_cage].taille++;
}

void ajouter_somme_cage(liste_cages_t *ls_cages, int num_cage, int somme) {
    ls_cages->cages[num_cage].somme = somme;
}

bool somme_cage_possible(liste_cages_t *ls_cages, int num_cage, int num) {
    int somme = 0;
    for (int i = 0; i < ls_cages->cages[num_cage].taille; i++) {
        somme += *ls_cages->cages[num_cage].coords[i];
    }
    return somme + num <= ls_cages->cages[num_cage].somme;
}

void lire_grille(int grille[TAILLE][TAILLE], int cage_index[TAILLE][TAILLE], liste_cages_t *ls_cages) {
    int i, j;
    int index;
    for (i = 0; i < TAILLE; i++) {
        char grid_line[10];
        char grid_cages[10];
        scanf("%s%s", grid_line, grid_cages);
        fgetc(stdin);
        for (j = 0; j < TAILLE; j++) {
            if (grid_line[j] == '.') {
                grille[i][j] = 0;
            } else {
                grille[i][j] = grid_line[j] - '0';
            }
        }

        for (j = 0; j < TAILLE; j++) {
            index = lettre_to_index(grid_cages[j]);
            cage_index[i][j] = index;
            ajouter_coord_cage(ls_cages, index, &grille[i][j]);
        }
    }

    char cages[251];
    scanf("%[^\n]", cages);

    char somme[3];
    char lettre;
    i = 0;
    while (cages[i] != '\0') {
        lettre = cages[i];
        i += 2;
        j = 0;
        somme[0] = '\0';
        somme[1] = '\0';
        somme[2] = '\0';
        while (cages[i] != ' ' && cages[i] != '\0') {
            somme[j] = cages[i];
            j++;
            i++;
        }
        ajouter_somme_cage(ls_cages, lettre_to_index(lettre), atoi(somme));
        i++;
    }
}

bool est_valide(int grille[TAILLE][TAILLE], int cage_index[TAILLE][TAILLE], liste_cages_t *ls_cages, int x, int y, int num) {
    int i;

    // Vérifier la ligne et la colonne
    for (i = 0; i < TAILLE; i++) {
        if (grille[i][y] == num || grille[x][i] == num) {
            return false;
        }
    }

    // Vérifier la sous-grille
    int x0 = (x / 3) * 3;
    int y0 = (y / 3) * 3;
    for (i = 0; i < 3; i++) {
        for (int j = 0; j < 3; j++) {
            if (grille[x0 + i][y0 + j] == num) {
                return false;
            }
        }
    }

    // Vérifier les cages
    return somme_cage_possible(ls_cages, cage_index[x][y], num);
}

bool resolution(int grille[TAILLE][TAILLE], int cage_index[TAILLE][TAILLE], liste_cages_t *ls_cages) {
    int i, j, num;

    for (i = 0; i < TAILLE; i++) {
        for (j = 0; j < TAILLE; j++) {
            if (grille[i][j] == 0) {
                for (num = 1; num <= 9; num++) {
                    if (est_valide(grille, cage_index, ls_cages, i, j, num)) {
                        grille[i][j] = num;
                        if (resolution(grille, cage_index, ls_cages)) {
                            return true;
                        } else {
                            grille[i][j] = 0;
                        }
                    }
                }
                return false;
            }
        }
    }
    return true;
}

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

int main() {
    int grille[TAILLE][TAILLE];
    int cage_index[TAILLE][TAILLE];
    liste_cages_t ls_cages;

    init_liste_cages(&ls_cages);

    lire_grille(grille, cage_index, &ls_cages);

    resolution(grille, cage_index, &ls_cages);
    afficher_grille(grille);

    return 0;
}