Rapport sur Killer Sudoku Solver

void affiche(){

    for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                fprintf(stderr,"%d", tab[i][j]); // Affiche la case de coordonnée i,j dans le tableau
            }
            fprintf(stderr,"\n");
        }
}

Cette fonction permet d’afficher la grille de sudoku. Elle m’a notamment été utile lors du débugage de mon code.

int find_cage(int x,int y,int n){

    // Définition des variables

    int somme=n;
    int k=0;
    int stop=0;
    int i=0;
    int j=0;
    int count=0;

    // Boucle qui permet de récupérer des informations sur la cage dans laquelle se situe la case que l'on traite

    while((lettre[k]!='\0')&&(stop!=1)){
        if(lettre[k]==cage[y][x]){
            stop=1;
        }

        k++;
    }

    // Tant que l'on a pas parcouru le tableau ou que l'on a pas trouvé tout les élements d'une cage

    while((i<9)&&(compteur[k-1]!=count)){
        while((j<9)&&(compteur[k-1]!=count)){
            if((cage[i][j]==cage[y][x])&&(tab[i][j]!=0)){ // Si on a trouvé un élement de la cage et qu'il est rempli
                somme+=tab[i][j]; // On ajoute sa valeur à la somme
                count++;
                if(somme>valeur[k-1]){ // Si la somme des cases est plus grande que la somme attendue
                    return -1;
                }
            }else if((cage[i][j]==cage[y][x])&&(tab[i][j]==0)&&((i!=y)||(j!=x))){ // Si on trouve une case qui appartient à la cage est qui est vide
                return 1;
            }
            j++;
        }
        j=0;
        i++;
    }


    if(somme==valeur[k-1]){ // Si la somme est bien la somme attendue
        return 1;
    }

    return 0;
}

Cette fonction permet de vérifier si le nombre que l’on souhaite ajouter respecte bien les conditions liées à sa cage. On cherche donc à savoir si la somme des nombres de la cage en question (ajoutés au nouveau nombre) est bien la bonne. Pour cela, on va parcourir la grille dans une double boucle while ce qui pourra nous permettre de stopper le parcour lorsque l’on aura trouvé tout les élements dont on a besoin. Ainsi, on va définir une variable count qui sera incrémentée de 1 dès lors que l’on aura trouvé un élement de la cage. Elle permettra à la boucle de s’arréter lorsque l’on aura trouvé tout les élements de la cage. Mais ce n’est pas la seule condition qui fera s’arréter la boucle. En effet, si un des élements de la cage n’est pas encore complété, il ne servira à rien de chercher les autres élements, puisqu’il nous sera impossible de compléter la somme de la cage. Alors, on renvoi 1, ce qui signifit que le nombre que l’on souhaite ajouter peut être bon, même si l’on en est pas assuré. Enfin, à chaque tour de boucle, on va tester si la somme actuelle que l’on connait (celle qui n’est pas encore complète puisque l’on a pas trouvé toutes les cases), ne dépasse pas la somme attendue. Si tel est le cas, on renvoi le code -1, qui signifit que le nombre que l’on souhaite tester fait que la somme dépasse de la valeur attendu. Cela pourra nous aider à gagner en nombre d’opération plus tard dans le programme. Enfin, si l’appel de la fonction ne s’est pas arrété avant la fin du parcour, on compare la somme obtenue à celle attendue pour la cage. Si elles sont égales, on renvoi le code 1 signifiant que le nombre est éligible pour compléter cette case.

int test(int y, int x, int n) {
    int x0=0, y0=0;
    int count=1;

    // Vérifie si le nombre testé est déja sur la ligne

    while (x0 < 9 && count==1) {
        if (tab[y][x0] == n) {
            count=0;
        }
        x0++;
    }

    // Vérifie si le nombre testé est déja sur la colonne

    while (y0 < 9 && count==1) {
        if (tab[y0][x] == n) {
            count=0;
        }
        y0++;
    }


    // Vérifie si le nombre testé est déja dans le carré de 3 par 3

    x0 = (x / 3) * 3;
    y0 = (y / 3) * 3;
    int i=0;
    while (i < 3 && count==1) {
        int j = 0;
        while (j < 3 && count==1) {
            if (tab[y0+i][x0+j] == n) {
                count=0;
            }
            j++;
        }
        i++;
    }
    return count;
}

Dans cette troisième partie, on définie une fonction test, qui va permettre de tester la validité des nombres que l’on souhaite ajouter à la grille. Cette fonction prend en argument les coordonnées de la position à laquelle on souhaite ajouter le nombre, ainsi que le nombre que l’on souhaite ajouter. Premièrement, la fonction va tester si le nombre testé est présent sur la ligne où l’on souhaite l’ajouter. Si c’est le cas, on renverra le code 0 qui, dans le cadre de ce code représentera un échec. Ensuite, la fonction va tester de la même manière, si le nombre que l’on souhaite ajouter est déjà présent sur la colonne. Enfin, dans une troisième boucle, qui est une double boucle while, on va parcourir le tableau afin de vérifier si le nombre est déjà présent dans le cube de 3*3 délimité par les grilles de sudoku. A la fin de tout ces test, on renverra 1 si tout les tests sont passés, sinon la fonction renverra 0.

void solve() {

    int y, x,n;
    for (y= 0; y < 9; y++) {       // On parcour le tableau
        for (x = 0; x < 9; x++) {
            if (tab[y][x] == 0) {       // Si on tombe sur une case non remplie
                for(n = 1; n < 10; n++){
                    int find=find_cage(x,y,n);
                    if ((test(y, x, n)==1)&&(find==1)){  // Test si le nombre n peut aller dans la case
                        tab[y][x] = n;   //  Mise à jour du tableau
                        solve();        // On relance la fonction
                        tab[y][x] = 0;      // Remise à 0 de la case si mauvais choix
                    }else if((test(y, x, n)==1)&&(find==-1)){
                        break;
                    }
                }
                return;
            }
        }
    }

    for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                printf("%d", tab[i][j]);
            }
            printf("\n");
        }
    exit(0);
}

Dans cette partie, on retrouve la fonction solve, utilisant le mécanisme de récursion, qui va nous permettre de trouver la solution à la grille de Sudoku. Si le nombre que l’on souhaite ajouter respecte les conditions, on va à nouveau appeler la fonction solve pour continuer à compléter la grille. Si la fonction find renvoie le code -1, cela signifit que la somme de la cage est plus grande que la somme attendu. Il faut donc revenir en arrière sur le positionnement des autres chiffres, puisque comme on test les chiffres par ordre croissant, le chiffre suivant ne sera forcement pas valide (la somme sera forcement trop grande).

int voisin(int i, int j, char name, int count, int teste[10][10]){

    // Si l'élement testé ne fait pas parti de la cage

    if (cage[i][j]!=name){
        return count;
    }

    count++; // On ajoute 1 au compteur si on détecte un élement de la cage
    teste[i][j]=1; // Indique que la case a déja été testé


    if((i!=0)&&(teste[i-1][j]!=1)){     // Si on est pas en haut du tableau, alors on regarde la case du dessus
        count=voisin(i-1 , j, name, count, teste) ;
    }
    if((j!=0)&&(teste[i][j-1]!=1)){     // Si on est pas sur le bord droit du tableau, alors on regarde la case de gauche
        count=voisin(i , j-1, name, count, teste ) ;
    }
    if((j!=8)&&(teste[i][j+1]!=1)){     // Si on est pas en haut du tableau, alors on regarde la case de droite
        count=voisin(i , j+1, name, count, teste ) ;
    }
    if((i!=8)&&(teste[i+1][j]!=1)){     // Si on est pas en bas du tableau, alors on regarde la case du dessous
        count=voisin(i+1 , j, name, count, teste ) ;
    }

    return count;
}

Dans cette partie, on définit la fonction voisin, qui a pour but de calculer le nombre d’élement de chaque cage. Ainsi, on pourra se servir de cette donnée afin de créer les nouvelles conditions vu au dessus. Cela diminuera donc la complexité de notre code, et donc son temps d’execution. On reviendra plus en détail sur cette fonction lors du détail algorithmique.

for (int i = 0; i < 9; i++) {
        char grid_line[10];
        char grid_cages[10];
        scanf("%s%s", grid_line, grid_cages);
        fgetc(stdin);
        for(int j=0;j <9 ;j++){ // Récupération des valeurs des cases du sudoku
            if(grid_line[j]!='.'){ // Si la valeur est indiqué
                tab[i][j]=grid_line[j]-'0'; // On l'inscrit
            }else{
                tab[i][j]=0; // Sinon on lui assigne automatiquement la valeur 0
            }

            cage[i][j]=grid_cages[j]; // On crée un tableau avec les cages
        }
    }
    char cages[251];
    scanf("%[^\n]", cages);

    int j;
    int i=0;
    int k=0;
    int y=0;
    int x=0;
    char stock_nb[10];
    stock_nb[0]='\0';
    stock_nb[1]='\0';
    stock_nb[2]='\0';
    int count_tot=0;
    int trouve=0;
    int xsave,ysave;

    while(cages[i]!='\0'){ // Tant que l'on a pas lu toute la ligne
        if(((cages[i]<='Z')&&(cages[i]>='A'))||((cages[i]<='z')&&(cages[i]>='a'))){ // Si on détecte une lettre
            j=2;

            while((cages[i+j]<='9')&&(cages[i+j]>='0')){ // On récupère la valeur correspondante
                stock_nb[j-2]=cages[i+j];
                j++;
            }

            valeur[k]=atoi(stock_nb);
            count_tot++;
            lettre[k]=cages[i];

            while(trouve!=1){
                while((trouve!=1)||(x<9)){
                    if(lettre[k]==cage[y][x]){
                        trouve=1;
                        xsave=x;
                        ysave=y;
                    }
                    x++;
                }
                x=0;
                y++;
            }
            y=0;
            trouve=0;

            int teste[10][10]={0};  // Remplissage d'un tableau de 0
            compteur[k]=voisin(ysave,xsave,cage[ysave][xsave],0, teste); // Création d'un tableau avec le nombre d'élement de chaque cage.

            stock_nb[0]='\0';
            stock_nb[1]='\0';
            stock_nb[2]='\0';
            k++;
        }
        i++;
    }


    i=0;
    j=0;

    solve();

    return 0;

Dans le programme principal, on va récupérer les entrées fournies par Codingame, puis on va appeler la fonction solve, qui va résoudre le Sudoku. Pour récupérer les entrées, on va stocker dans un premier tableau la grille de sudoku, vide, avec uniquement les chiffres déjà préremplis dans les test. On va remplacer les . représentant les cases vides par des 0. Simultanemment, on stockera les cages dans un autre tableau. Ensuite, on va récupérer les valeurs des sommes pour chaque cage. Pour se faire, on va parcourir la ligne qui nous est fournie. Lorsque l’on trouvera une lettre, on la stockera, puis on cherchera la valeur correspondante. Les entrées sont données en une seule ligne sous la forme suivante: lettre=nombre et sont séparées par un espace. Pour récupérer le nombre il suffira donc de récupérer tout les caractères qui sont des chiffres jusqu’à rencontrer un espace. Ensuite, à l’aide de la fonction atoi(), on convertira la chaine de caractère obtenue en un entier. Enfin, on fera appel à la fonction voisin dans une double boucle afin d’obtenir le nombre d’élement de chaque cage.

Cliquez ici pour agrandir

Dans le schéma ci dessus, les flèches rouges représentent un test négatif, et les vertes un test positif.

Tout d’abord revenons sur ce qu’est un mécanisme de récursion. Ce mécanisme consiste en l’appel d’une fonction à l’intérieur d’elle même. Une fonction récursive mal définie/codée peut donc engendrer un nombre infini d’appel. Mais ce mécanisme bien utilisé peut être très puissant et extrémement utile.

C’est le cas de cette fonction qui l’utilise afin de trouver la solution au Sudoku de manière brute. C’est-à-dire qu’elle teste toutes les solutions possibles jusqu’à trouver la bonne. Dans cette fonction (solve()), on parcour le tableau, et dès que l’on trouve un 0, on essaye de remplir la case. Alors, on test tout les nombres de 1 à 9. Pour que le test soit validé il faut que la fonction test, et la fonction find_cage renvoient 1. Dès que l’on trouve un nombre qui fonctionne, on le place dans la grille, puis on appelle à nouveau la fonction, jusqu’à ce que la grille soit remplie. Alors, si les nombres placés bloquent la grille de Sudoku par la suite, les cases précedement remplies seront remises à 0, et les test seront fait avec d’autres nombres. Si la fonction find_cage renvoie -1 et que la fonction test renvoie 1, alors on sait qu’il n’est pas nécessaire de tester d’autres nombres pour cette case, et qu’il faut directement revenir en arrière.

Ainsi, suivant ce processus, la fonction ne s’arrétera que lorsque toute la grille sera remplie.

Nous allons maintenant nous intéresser à la fonction voisin et à son fonctionnement. Afin d’illustrer mes propos, voici ci dessous un schéma explicatif du fonctionnement de la fonction.

Cliquez ici pour agrandir

Dans le schéma ci dessus, les cases rouges représentent la cage dont on compte les élements, les cases plus clairs représentent les cases à tester, et les cases plus foncées représentent les cases testé au moment de l’étape. La seconde grille remplie de cases noirs et blanches représente le tableau test, servant à sauvegarder les cases rouges déja testées.

Pour rappel, la fonction voisin a pour but de compter le nombre d’élement d’une cage. On voudra ici compter les élements de la cage rouge.

Afin d’être certain de ne pas avoir de problèmes de mémoire et autres, que le compilateur n’aurait pas détecté, on utilise valgrind.

valgrind ./killer < killertest/test3

Cliquez ici pour agrandir

Le programme présenté passe bien valgrind pour les 3 premiers tests.