Rapport : Sudoku solver

Table des matières

1. Introduction
2. Méthode de résolution
- 2.1. Implémentation complète
3. Tests
4. Solution de la communauté
5. Conclusion

1. Introduction

1.1. Principe de focntionnment

Url du challenge : https://www.codingame.com/training/medium/sudoku-solver

L’objectif de ce challenge est de résoudre une grille de sudoku classique.

Rappel des règles du sudoku :

Chaque ligne doit contenir les chiffres de 1 à 9
Chaque colonne doit contenir les chiffres de 1 à 9
Chaque carré de 3x3 doit contenir les chiffres de 1 à 9

1.2. Données fournies

On reçoit en entrée une grille de sudoku sous forme de chaîne de caractères, 9 lignes de 9 caractères chacune.

1.3. Données à fournir

On doit fournir en sortie une grille de sudoku complétée.

2. Méthode de résolution

La fonction lire_grille permet de lire la grille de sudoku en entrée et de la stocker dans un tableau à deux dimensions. On transforme chaque caractère en entier en soustrayant la valeur ASCII du caractère ’0’.

void lire_grille(int grille[TAILLE][TAILLE]) {
    int i, j;
    for (i = 0; i < TAILLE; i++) {
        char line[10];
        scanf("%[^\n]", line);
        fgetc(stdin);
        for (j = 0; j < TAILLE; j++) {
            grille[i][j] = line[j] - '0';
        }
    }
}

La fonction est_valide permet de vérifier si un nombre peut être placé dans une case de la grille. On vérifie que le nombre n’est pas déjà présent dans la ligne, la colonne et la sous-grille.

bool est_valide(int grille[TAILLE][TAILLE], 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;
            }
        }
    }
    return true;
}

La fonction resolution permet de résoudre la grille de sudoku. On parcourt la grille de gauche à droite et de haut en bas. Si on trouve une case vide, on essaie de placer un nombre de 1 à 9. Si le nombre est valide, on le place dans la case et on appelle la fonction récursivement. Si la fonction retourne true, on a trouvé une solution, sinon on remet la case à 0 et on essaie avec un autre nombre. Si on a essayé tous les nombres et qu’aucun n’est valide, on retourne false.

bool resolution(int grille[TAILLE][TAILLE]) {
    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, i, j, num)) {
                        grille[i][j] = num;
                        if (resolution(grille)) {
                            return true;
                        } else {
                            grille[i][j] = 0;
                        }
                    }
                }
                return false;
            }
        }
    }
    return true;
}

La fonction afficher_grille permet d’afficher la grille de sudoku en sortie.

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];

    lire_grille(grille);
    resolution(grille);
    afficher_grille(grille);

    return 0;
}

2.1. Implémentation complète

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

#define TAILLE 9

void lire_grille(int grille[TAILLE][TAILLE]) {
    int i, j;
    for (i = 0; i < TAILLE; i++) {
        char line[10];
        scanf("%[^\n]", line);
        fgetc(stdin);
        for (j = 0; j < TAILLE; j++) {
            grille[i][j] = line[j] - '0';
        }
    }
}

bool est_valide(int grille[TAILLE][TAILLE], 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;
            }
        }
    }
    return true;
}

bool resolution(int grille[TAILLE][TAILLE]) {
    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, i, j, num)) {
                        grille[i][j] = num;
                        if (resolution(grille)) {
                            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];

    lire_grille(grille);
    resolution(grille);
    afficher_grille(grille);

    return 0;
}

3. Tests

3.1. Compilation

Compilation avec gcc :

✅ Compilation sans erreur/warning OK

3.2. Test de Codingame

3.2.1. Test 1 : Very Easy

Input:

Expected output:

Actual output:

Run test:

Test 1: Very Easy
✅ Test passed

3.2.2. Test 2 : Easy

Input:

Expected output:

Actual output:

Run test:

Test 2: Easy
✅ Test passed

3.2.3. Test 3 : Intermediate/Hard

Input:

Expected output:

Actual output:

Run test:

Test 3: Intermediate/Hard
✅ Test passed

3.2.4. Test 4 : World’s Hardest Sudoku

Input:

Expected output:

Actual output:

Run test:

Test 4: World's Hardest Sudoku
✅ Test passed

3.2.5. Résumé global

✅ Test 1 : Very Easy passed
✅ Test 2 : Easy passed
✅ Test 3 : Intermediate/Hard passed
✅ Test 4 : World's Hardest Sudoku passed
Passed: 4 (100.0%)
Failed: 0 (0.0%)

3.3. Test Valgrind

✅ Valgrind check
==13523== Memcheck, a memory error detector
==13523== Copyright (C) 2002-2022, and GNU GPL'd, by Julian Seward et al.
==13523== Using Valgrind-3.20.0 and LibVEX; rerun with -h for copyright info
==13523== Command: ./temp/code
==13523== 
123874569
567932184
849651237
916247853
358196472
472385916
291768345
685423791
734519628
==13523== 
==13523== HEAP SUMMARY:
==13523==     in use at exit: 0 bytes in 0 blocks
==13523==   total heap usage: 2 allocs, 2 frees, 8,192 bytes allocated
==13523== 
==13523== All heap blocks were freed -- no leaks are possible
==13523== 
==13523== For lists of detected and suppressed errors, rerun with: -s
==13523== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)

4. Solution de la communauté

Solution de Juanmv94 : https://www.codingame.com/training/medium/sudoku-solver/solution?id=20944563

#include <stdio.h>

typedef struct {
    unsigned char val : 4;
    unsigned char pred : 1;
} scell;

int main() {
    scell s[9][9];
    for (int i=0;i<9;i++) {
        for (int j=0;j<9;j++) {
            s[i][j].val=getchar()-'0';
            s[i][j].pred=s[i][j].val?1:0;
        }
        getchar();
    }

    int p=0;
    while(p<9*9) {
        int i=p/9,j=p%9;
        if (s[i][j].pred) p++;
        else {
            while (++s[i][j].val<=9) {
                int t;
                for(t=0;t<9;t++) {
                    int si=i/3*3+(t%3);
                    int sj=j/3*3+(t/3);
                    if ((t!=i && s[t][j].val==s[i][j].val) ||
                        (t!=j && s[i][t].val==s[i][j].val) ||
                        ((si!=i || sj!=j) && s[si][sj].val==s[i][j].val)) break;
                }
                if (t>=9) break;
            }
            if (s[i][j].val>=10) {
                s[i][j].val=0;
                do {p--;} while (s[p/9][p%9].pred);
            } else p++;
        }
    }


    for (int i=0;i<9;i++) {
        for (int j=0;j<9;j++) putchar(s[i][j].val+'0');
        putchar('\n');
    }
    return 0;
}

J’ai choisi cette solution car elle est très simple et efficace. Elle utilise des structures de données simples et efficaces. Elle utilise aussi une approche itérative pour résoudre le problème, contrairement à ma solution qui utilise une approche récursive. On note aussi que le code utilise la technique de brute force pour résoudre le problème. C’est une technique qui est très simple à implémenter mais qui est très coûteuse en temps de calcul. En effet, pour résoudre un sudoku, il faut tester toutes les possibilités. C’est pourquoi, il est préférable d’utiliser une approche plus intelligente pour résoudre le problème.

5. Conclusion

Lors de cet exercice, j’ai pu mettre en place un algorithme récursif pour résoudre un sudoku.

Retour vers ma page Web personnelle

Crédits :

Template : github