Rapport : Suguru solver

4 5
G. G4 G1 G.
R. G. B. B.
G. R. R4 B.
G. R. R2 B.
G3 G. R. B.

2413
1525
2341
1523
3414

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

#define MAX_CAGES 100
#define MAX_COORDS_CAGE 6

typedef struct
{
    int taille;                   // Nombre de d'element dans 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 **creer_grille(int largeur, int hauteur)
{
    int **grille = malloc(hauteur * sizeof *grille);
    for (int i = 0; i < hauteur; i++)
    {
        grille[i] = malloc(largeur * sizeof *grille[i]);
    }
    return grille;
}

void detruire_grille(int **grille, int hauteur)
{
    for (int i = 0; i < hauteur; i++)
    {
        free(grille[i]);
    }
    free(grille);
}

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 lire_grille(int **grille, int **cage_index, int l, int h)
{
    int i, j, k;
    for (i = 0; i < h; i++)
    {
        char line[60];
        scanf("%[^\n]", line);
        fgetc(stdin);
        for (j = 0; j < l; j++)
        {
            k = j * 3;
            cage_index[i][j] = line[k] - 'A' + 26;
            if (line[k + 1] == '.')
            {
                grille[i][j] = 0;
            }
            else
            {
                grille[i][j] = line[k + 1] - '0';
            }
        }
    }
}

void propagation(int **grille, int **cage_index, int **new_index, liste_cages_t *ls_cages, int l, int h, int x, int y)
{
    // propagation au dessus, en dessous, à gauche et à droite de la case si l'index de la case est similaire à celui de la case actuelle
    // mais pas en diagonale
    int i, j;
    for (i = x - 1; i <= x + 1; i++)
    {
        for (j = y - 1; j <= y + 1; j++)
        {
            if (i >= 0 && i < h && j >= 0 && j < l)
            {
                if (i == x || j == y)
                {
                    if (new_index[i][j] == 0 && cage_index[i][j] == cage_index[x][y])
                    {
                        new_index[i][j] = new_index[x][y];
                        ajouter_coord_cage(ls_cages, new_index[x][y], &grille[i][j]);
                        propagation(grille, cage_index, new_index, ls_cages, l, h, i, j);
                    }
                }
            }
        }
    }
}

void completion_cage(int **grille, int **cage_index, int l, int h, liste_cages_t *ls_cages)
{
    int i, j;

    int **new_index = creer_grille(l, h);
    int prochain_index = 1;

    // Initialisation de la grille de l'index des cages à 0
    for (i = 0; i < h; i++)
    {
        for (j = 0; j < l; j++)
        {
            new_index[i][j] = 0;
        }
    }

    for (i = 0; i < h; i++)
    {
        for (j = 0; j < l; j++)
        {
            if (new_index[i][j] == 0)
            {
                new_index[i][j] = prochain_index;
                propagation(grille, cage_index, new_index, ls_cages, l, h, i, j);
                ajouter_coord_cage(ls_cages, prochain_index, &grille[i][j]);
                prochain_index++;
            }
        }
    }

    for (i = 0; i < h; i++)
    {
        for (j = 0; j < l; j++)
        {
            cage_index[i][j] = new_index[i][j];
        }
    }

    detruire_grille(new_index, h);
}

bool est_valide(int **grille, int **cage_index, liste_cages_t *ls_cages, int x, int y, int num, int l, int h)
{
    // Verifier voisin 3x3 centré sur la case
    int i, j;
    for (i = x - 1; i <= x + 1; i++)
    {
        for (j = y - 1; j <= y + 1; j++)
        {
            if (i >= 0 && i < h && j >= 0 && j < l && grille[i][j] == num)
            {
                return false;
            }
        }
    }

    // Vérifier la cage
    int index = cage_index[x][y];
    for (i = 0; i < ls_cages->cages[index].taille; i++)
    {
        if (*(ls_cages->cages[index].coords[i]) == num)
        {
            return false;
        }
    }

    // la valeur ne dépasse pas la taille de la cage
    if (num > ls_cages->cages[index].taille)
    {
        return false;
    }

    return true;
}

bool resolution(int **grille, int **cage_index, liste_cages_t *ls_cages, int l, int h)
{
    int i, j, num;

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

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

int main()
{
    int l, h;
    scanf("%d%d", &l, &h);
    fgetc(stdin);

    int **grille = creer_grille(l, h);
    int **cage_index = creer_grille(l, h);
    liste_cages_t ls_cages;

    init_liste_cages(&ls_cages);

    lire_grille(grille, cage_index, l, h);

    completion_cage(grille, cage_index, l, h, &ls_cages);

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

    detruire_grille(grille, h);
    detruire_grille(cage_index, h);

    return 0;
}