Licence CC BY

Le backtracking par l'exemple : résoudre un sudoku

Publié :
Auteur :
Catégorie :

Le backtracking (retour sur trace) est une méthode communément employée pour résoudre des problèmes en programmation.

Nous allons l'étudier à travers un exemple concret : la résolution d'une grille de sudoku par ordinateur.

Pour pouvoir comprendre certaines parties de ce tutoriel, il est hautement souhaitable d'être à l'aise avec la notion de récursivité. Si ce n'est pas le cas pour vous, je vous invite à lire ce tutoriel.

Définition

Avant de commencer, permettez moi de citer la définition tirée de Wikipédia :

Citation : Wikipédia

Le retour sur trace, appelé aussi backtracking en anglais, consiste à revenir légèrement en arrière sur des décisions prises afin de sortir d'un blocage. La méthode des essais et erreurs constitue un exemple simple de backtracking. Le terme est surtout utilisé en programmation, où il désigne une stratégie pour trouver des solutions à des problèmes de satisfaction de contraintes.

Concrètement, le backtracking peut s'apparenter à un parcours en profondeur d'un arbre avec une contrainte sur les noeuds : dés que la condition n'est plus remplie sur le noeud courant, on stoppe la descente sur ce noeud.

Je sais que tout cela doit vous paraitre assez abstrait, alors qu'il s'agit d'une technique fort simple de programmation. C'est pourquoi, je vous propose d'écrire avec moi un code mettant en application ce concept : résolution d'un sudoku par force brute :) .

Analyse du cas

Supposons que nous devions écrire un programme qui permette de résoudre des grilles de sudoku.

On pourrait tenter de faire un programme «intelligent», qui remplisse la grille de façon logique. Seulement si cela est assez simple pour les sudokus faciles, il en va autrement avec les grilles plus rétives :( … En effet, les méthodes de résolution dans ce cas seront plutôt complexes à écrire, ce qui nous amène a nous demander s'il ne serait pas plus judicieux de passer directement par la force brute.

C'est là que le problème de la complexité se pose : un brute-force est-il envisageable en pratique ? Pour $N$ cases vides dans la grille, nous avons $9^N$ combinaisons possibles. Un brute-force naïf semble donc assez mal parti…

C'est là qu'intervient le principe du retour sur trace. Si nous remplissons la grille au fur et à mesure, en vérifiant constamment qu'elle reste toujours potentiellement valide, on arrive assez vite à des situations de blocage ou il ne sert à rien de continuer. Dans un tel cas, on reviendra en arrière en évitant de continuer une exploration inutile. Avec cette manière de faire - appelée backtracking, le nombre de combinaisons à explorer est considérablement réduit, et le brute-force sera une solution parfaitement envisageable pour résoudre une grille de sudoku. :)

Facile à dire ! Mais concrètement, on fait comment pour revenir sur ses pas, comme tu dis ? Je viens d'essayer de coder un truc, mais c'est le gros bordel…

Effectivement, l'écriture d'un tel code n'est pas forcement évidente dés le début. Sachez surtout que nous pouvons nous servir de la récursivité pour en simplifier l'écriture. C'est d'ailleurs ce que nous allons faire dans la prochaine partie ;) !

Codage de la solution

Pour des raisons de commodité et rester accessible au plus grand nombre, j'ai choisi le langage C99/C++ pour illustrer la solution. Mais n'importe quelle personne ayant déjà codé devrait pouvoir suivre sans problème.

Première étape : structurer les données

Une grille de sudoku.

Avant tout, nous allons prendre un exemple de grille pour pouvoir tester notre code. Pour une bête grille de sudoku, un simple tableau en 2 dimensions fera l'affaire. Voici un tableau correspondant à la grille ci-contre (les cases vides étant représentées par des zéros) :

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
int grille[9][9] =
    {
        {9,0,0,1,0,0,0,0,5},
        {0,0,5,0,9,0,2,0,1},
        {8,0,0,0,4,0,0,0,0},
        {0,0,0,0,8,0,0,0,0},
        {0,0,0,7,0,0,0,0,0},
        {0,0,0,0,2,6,0,0,9},
        {2,0,0,3,0,0,0,0,6},
        {0,0,0,2,0,0,9,0,0},
        {0,0,1,9,0,4,5,7,0}
    };

Deuxième étape : fonctions auxiliaires

Nous allons avoir besoin de fonctions pour tester si une valeur est bien absente d'une ligne, d'une colonne ou encore d'un bloc de la grille. Mieux vaut s'en occuper tout de suite, avant de passer au vif du sujet ;) .

La méthode la plus simple est de parcourir respectivement la ligne/colonne/bloc, et de retourner FAUX si la valeur est trouvée, sinon on retourne VRAI:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
bool absentSurLigne (int k, int grille[9][9], int i)
{
    for (int j=0; j < 9; j++)
        if (grille[i][j] == k)
            return false;
    return true;
}

bool absentSurColonne (int k, int grille[9][9], int j)
{
    for (int i=0; i < 9; i++)
        if (grille[i][j] == k)
            return false;
    return true;
}

bool absentSurBloc (int k, int grille[9][9], int i, int j)
{
    int _i = i-(i%3), _j = j-(j%3);  // ou encore : _i = 3*(i/3), _j = 3*(j/3);
    for (i=_i; i < _i+3; i++)
        for (j=_j; j < _j+3; j++)
            if (grille[i][j] == k)
                return false;
    return true;
}

Troisième étape : backtracking

Cette fois, nous sommes enfin arrivés à la partie vraiment intéressante ;) !

Procédons étape par étape. Nous allons tout d'abord définir le prototype de la fonction de résolution.

Prototype de la fonction

Cette fonction doit recevoir une grille en entrée et la résoudre. Doit-elle retourner quelque chose ?

Oui, car nous devons constamment vérifier que le choix fait en amont ne provoque pas de blocage en aval. On va donc utiliser le retour de la fonction pour nous indiquer si la grille est valide ou non.

Enfin, comme notre fonction doit être récursive, nous allons ajouter un paramètre pour savoir quelle case nous sommes en train de traiter. Une case (i,j) dans un tableau peut être représentée par un nombre (i*LARGEUR_TABLEAU) + j, que nous nommerons position.

Ce qui nous donne au final comme prototype : bool estValide (int grille[9][9], int position);.

Passons maintenant à l'intérieur de la fonction ;) .

Cas simples

Nous allons commencer par gérer les cas simples :

Si on a terminé de parcourir la grille, c'est qu'elle est valide, on retourne VRAI. Si la case est déjà remplie, on passe directement à la case suivante.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
bool estValide (int grille[9][9], int position)
{
    // Si on est à la 82e case (on sort du tableau)
    if (position == 9*9)
        return true;

    // On récupère les coordonnées de la case
    int i = position/9, j = position%9;

    // Si la case n'est pas vide, on passe à la suivante (appel récursif)
    if (grille[i][j] != 0)
        return estValide(grille, position+1);

    // A implémenter : backtracking
}

Backtracking

Il ne reste plus qu'à gérer le retour sur trace (eh oui, je vous ai laissé le plus dur pour la fin :p ).

Considérons le problème : il nous faut énumérer tous les chiffres possibles, puis tester chaque solution éventuelle pour vérifier si elle nous amène à une solution correcte, ou bien à un blocage.

Mais attention ! Pour que les tests sur la grille puissent fonctionner, il faut veiller à actualiser la grille au cours de la descente récursive. Et c'est là que beaucoup se font piéger : il ne suffit pas d'enregistrer le choix effectué dans la grille avant de passer à l'appel suivant, mais il faut aussi réinitialiser la case à zéro en cas d'échec. Sans quoi, la fonction a de grandes chances de se retrouver avec une grille invalide…

Voici le code avec actualisation de la grille :

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
// énumération des valeurs possibles
    for (int k=1; k <= 9; k++)
    {
        // Si la valeur est absente, donc autorisée
        if (absentSurLigne(k,grille,i) && absentSurColonne(k,grille,j) && absentSurBloc(k,grille,i,j))
        {
            // On enregistre k dans la grille
            grille[i][j] = k;
            // On appelle récursivement la fonction estValide(), pour voir si ce choix est bon par la suite
            if ( estValide (grille, position+1) )
                return true;  // Si le choix est bon, plus la peine de continuer, on renvoie true :)
        }
    }
    // Tous les chiffres ont été testés, aucun n'est bon, on réinitialise la case
    grille[i][j] = 0;
    // Puis on retourne false :(
    return false;

Code complet

Allez, je vous donne un code complet pour tester chez vous :) :

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
#include <stdlib.h>
#include <stdio.h>
#include <stdbool.h>


// Fonction d'affichage
void affichage (int grille[9][9])
{
    for (int i=0; i<9; i++)
    {
        for (int j=0; j<9; j++)
        {
            printf( ((j+1)%3) ? "%d " : "%d|", grille[i][j]);
        }
        putchar('\n');
        if (!((i+1)%3))
            puts("------------------");
    }
    puts("\n\n");
}

bool absentSurLigne (int k, int grille[9][9], int i)
{
    for (int j=0; j < 9; j++)
        if (grille[i][j] == k)
            return false;
    return true;
}

bool absentSurColonne (int k, int grille[9][9], int j)
{
    for (int i=0; i < 9; i++)
        if (grille[i][j] == k)
            return false;
    return true;
}

bool absentSurBloc (int k, int grille[9][9], int i, int j)
{
    int _i = i-(i%3), _j = j-(j%3);  // ou encore : _i = 3*(i/3), _j = 3*(j/3);
    for (i=_i; i < _i+3; i++)
        for (j=_j; j < _j+3; j++)
            if (grille[i][j] == k)
                return false;
    return true;
}

bool estValide (int grille[9][9], int position)
{
    if (position == 9*9)
        return true;

    int i = position/9, j = position%9;

    if (grille[i][j] != 0)
        return estValide(grille, position+1);

    for (int k=1; k <= 9; k++)
    {
        if (absentSurLigne(k,grille,i) && absentSurColonne(k,grille,j) && absentSurBloc(k,grille,i,j))
        {
            grille[i][j] = k;

            if ( estValide (grille, position+1) )
                return true;
        }
    }
    grille[i][j] = 0;

    return false;
}

int main (void)
{
    int grille[9][9] =
    {
        {9,0,0,1,0,0,0,0,5},
        {0,0,5,0,9,0,2,0,1},
        {8,0,0,0,4,0,0,0,0},
        {0,0,0,0,8,0,0,0,0},
        {0,0,0,7,0,0,0,0,0},
        {0,0,0,0,2,6,0,0,9},
        {2,0,0,3,0,0,0,0,6},
        {0,0,0,2,0,0,9,0,0},
        {0,0,1,9,0,4,5,7,0}
    };

    printf("Grille avant\n");
    affichage(grille);

    estValide(grille,0);

    printf("Grille apres\n");
    affichage(grille);
}

Pour aller plus loin

Analyse et critique du code

Le code ci-dessus est-il parfait ? Non, car on pourrait lui reprocher plusieurs points :

Pire des cas

Grille pire des cas pour backtracking naïf.

Même si notre code fournira en général la solution assez rapidement (moins d'une demi-seconde chez moi), les performances dépendent totalement de la grille passée en entrée. Certaines grilles spécialement conçues peuvent lui demander beaucoup plus de travail, ce qui montre bien que la complexité dans le pire des cas n'est pas si bonne que cela.

L'image ci-dessus (source - Wikipédia) est un exemple d'une telle grille. Le programme ci-dessus met chez moi environ 20 secondes pour la résoudre. La raison est que la bonne solution vient vers la fin de la descente récursive, et le nombre d'essais/erreurs est ainsi multiplié.

Pour pallier à cet inconvénient, essayons de réfléchir si l'on peut améliorer l'exploration des possibilités de manière à ce que la bonne solution sorte au plus tôt. La réponse est oui :) !

Optimisation

Ordre du parcours

On peut ici effectuer le backtracking dans n'importe quel ordre, le choix que nous avons fait de parcourir linéairement la grille est arbitraire. Le nombre de valeurs possibles pour chaque case vide n'est pas identique. Plus on remplit de cases (autrement dit : plus on s'enfonce dans la récursion), plus augmentent les chances de créer un blocage. Il apparaît que si nous effectuons le backtracking depuis les cases avec un minimum de solutions vers les cases avec un maximum de solutions, nous minimisons sensiblement l'exploration des possibilités. Cette méthode garantit aussi que la recherche sera toujours effectuée de façon optimale, et nous évitons ainsi le pire des cas mentionné plus haut.

Concrètement, on peut implémenter cette méthode en créant une liste de cases vides, qui enregistre les coordonnées et le nombre de valeurs possibles de chaque case. On triera la liste en ordre croissant, puis on la passe en argument de notre fonction de backtracking.

Cette optimisation est en réalité incomplète. En effet, ici on se contente de trier la liste des cases à parcourir avant de commencer la recherche. Une optimisation plus efficace serait de réorganiser l'ordre des cases à parcourir au cours de la descente récursive : on augmente encore considérablement les chances de tirer la bonne solution au plus tôt. Mais en pratique, ce n'est pas évident à réaliser correctement, c'est à dire en évitant que le coût des opérations ajoutées ne soit supérieur au gain escompté. C'est pourquoi nous n'aborderons pas ce point ici.

Voici un code possible :

Implémentation des listes "maison"
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
////////////////////////////////////////////
//    implémentation de la liste
////////////////////////////////////////////

typedef struct _list
{
    int i, j;
    int nbValeursPossibles;
    struct _list *next;
} LIST;

// retourne un nouvel élément initialisé
static LIST* new_elem (int i, int j, int n)
{
    LIST* ret = (LIST*) malloc(sizeof* ret);
    if (ret != NULL)
        ret->i = i, ret->j = j, ret->nbValeursPossibles = n, ret->next = NULL;
    return ret;
}

// supprime intégralement une liste chainée
void liste_delete (LIST** list)
{
    LIST* tmp;
    while ( (tmp = *list) != NULL)
        *list = (*list)->next, free(tmp);
}

// ajoute en tête
void liste_cons (LIST** list, int i, int j, int n)
{
    LIST* elem = new_elem (i, j, n);
    if (elem != NULL)
        elem->next = *list, *list = elem;
}

// insertion dans une liste triée
void insertion (LIST** list, LIST* elem)
{
    if (*list == NULL)
        *list = elem, elem->next = NULL;
    else if ((*list)->nbValeursPossibles < elem->nbValeursPossibles)
        insertion (&(*list)->next, elem);
    else
        elem->next = *list, *list = elem;
}

// tri insertion sur liste chainée
LIST* list_sort (LIST* list)
{
    LIST *curr, *list2 = NULL, *tmp;
    for (curr = list; curr != NULL; curr = tmp)
    {
        tmp = curr->next;
        insertion (&list2, curr);
    }
    return list2;
}
Code optimisé
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
bool absentDeLigne (int k, int grille[9][9], int i)
{
    for (int j=0; j < 9; j++)
        if (grille[i][j] == k)
            return false;
    return true;
}

bool absentDeColonne (int k, int grille[9][9], int j)
{
    for (int i=0; i < 9; i++)
        if (grille[i][j] == k)
            return false;
    return true;
}

bool absentDeBloc (int k, int grille[9][9], int i, int j)
{
    int _i = i-(i%3), _j = j-(j%3);  // ou encore : _i = 3*(i/3), _j = 3*(j/3);
    for (i=_i; i < _i+3; i++)
        for (j=_j; j < _j+3; j++)
            if (grille[i][j] == k)
                return false;
    return true;
}

bool estValide (int grille[9][9], LIST* position)
{
    // Si la liste est vide (fin de liste)
    if (position == NULL)
        return true;

    int i = position->i, j = position->j;

    for (int k=1; k <= 9; k++)
    {
        if ( absentDeLigne(k,grille,i) && absentDeColonne(k,grille,j) && absentDeBloc(k,grille,i,j) )
        {
            grille[i][j] = k;

            if ( estValide(grille, position->next) )
                return true;
        }
    }
    grille[i][j] = 0;

    return false;
}

// Calcule le nombre de valeurs possibles pour une case vide
int nb_possibles (int grille[9][9], int i, int j)
{
    int ret = 0;
    for (int k=0; k < 9; k++)
        if ( absentDeLigne(k,grille,i) && absentDeColonne(k,grille,j) && absentDeBloc(k,grille,i,j) )
            ret++;
    return ret;
}

bool resolution (int grille[9][9])
{
    // crée et remplit une liste pour les cases vides à visiter
    LIST* positions = NULL;
    for (int i=0; i < 9; i++)
        for (int j=0; j < 9; j++)
            if ( grille[i][j] == 0 )
                liste_cons ( &positions, i, j, nb_possibles2(grille, i, j) );

    // Trie la liste (ordre croissant)
    positions = list_sort (positions);

    // Appelle la fonction de backtracking récursive estValide()
    bool ret = estValide (grille, positions);
    // Détruit la liste
    liste_delete (&positions);
    // retourne le resultat
    return ret;
}

Optimisation du test

Un autre point que l'on pourrait reprocher à notre code, c'est sa méthode coûteuse pour tester si le nombre à insérer est absent de la ligne/colonne/bloc. En effet, cette fonction est dite "critique", car étant au cœur de la récursion, elle est appelée de très nombreuses fois. On a donc fort intérêt à l'optimiser…

Dans notre code, la méthode employée requiert au pire des cas un parcours de toute les cases de ces dernières, ce qui représente tout de même 27 cases. On peut améliorer sensiblement en mémorisant les valeurs présentes dans chaque ligne/colonne/bloc.

Si nous construisons au départ une liste des valeurs possibles pour chaque ligne/colonne/bloc, en utilisant des tableaux pour matérialiser ces listes, nous bénéficions d'un temps de lecture/écriture en $O(1)$. Le test de possibilité d'insertion d'une valeur se fait alors en 3 opérations, ce qui est un gain considérable. Même en prenant en compte l'actualisation des listes au cours de la descente récursive, sachant que l'on fera bien plus de tests que d'actualisations, cette solution sera meilleure que celle proposée plus haut.

En combinant cette optimisation avec l'autre ci-dessus, on peut s'affranchir de la plupart des opérations sur la grille, et c'est tant mieux ;) ! Il ne nous reste plus qu'a écrire la bonne valeur une fois trouvée.

Exemple :

Code avec optimisation 1 et 2
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
// Variables globales (tableaux) pour la mémorisation
bool existeSurLigne[9][9];
bool existeSurColonne[9][9];
bool existeSurBloc[9][9];


bool estValide (int grille[9][9], LIST* position)
{
    if (position == NULL)
        return true;

    int i = position->i, j = position->j;

    for (int k=0; k < 9; k++)
    {
        // Vérifie dans les tableaux si la valeur est déjà présente
        if ( !existeSurLigne[i][k] && !existeSurColonne[j][k] && !existeSurBloc[3*(i/3)+(j/3)][k] )
        {
            // Ajoute k aux valeurs enregistrées
            existeSurLigne[i][k] = existeSurColonne[j][k] = existeSurBloc[3*(i/3)+(j/3)][k] = true;

            if ( estValide(grille, position->next) )
            {
                // Ecrit le choix valide dans la grille
                grille[i][j] = k+1;
                return true;
            }
            // Supprime k des valeurs enregistrées
            existeSurLigne[i][k] = existeSurColonne[j][k] = existeSurBloc[3*(i/3)+(j/3)][k] = false;
        }
    }

    return false;
}

// Calcule le nombre de valeurs possibles pour une case vide
int nb_possibles (int grille[9][9], int i, int j)
{
    int ret = 0;
    for (int k=0; k < 9; k++)
        if ( !existeSurLigne[i][k] && !existeSurColonne[j][k] && !existeSurBloc[3*(i/3)+(j/3)][k] )
            ret++;
    return ret;
}

bool resolution (int grille[9][9])
{
    // Initialise les tableaux
    for (int i=0; i < 9; i++)
        for (int j=0; j < 9; j++)
            existeSurLigne[i][j] = existeSurColonne[i][j] = existeSurBloc[i][j] = false;

    // Enregistre dans les tableaux toutes les valeurs déjà présentes 
    int k;
    for (int i=0; i < 9; i++)
        for (int j=0; j < 9; j++)
            if ( (k = grille[i][j]) != 0)
                existeSurLigne[i][k-1] = existeSurColonne[j][k-1] = existeSurBloc[3*(i/3)+(j/3)][k-1] = true;

    // crée et remplit une liste pour les cases vides à visiter
    LIST* positions = NULL;
    for (int i=0; i < 9; i++)
        for (int j=0; j < 9; j++)
            if ( grille[i][j] == 0 )
                liste_cons ( &positions, i, j, nb_possibles(grille, i, j) );

    // Trie la liste (ordre croissant)
    positions = list_sort (positions);

    // Appelle la fonction de backtracking récursive estValide()
    bool ret = estValide (grille, positions);
    // Détruit la liste
    liste_delete (&positions);
    // retourne le resultat
    return ret;
}

Concernant la résolution logicielle de sudokus

Le code fourni ici pourrait, avec de légères modification, servir à vérifier que le nombre de solutions d'un sudoku ne dépasse pas 1. Pour cela, il suffit de retourner non pas si la grille est valide ou non, mais plutôt le nombre de solutions possibles. Je vous laisse trouver tout seul comment faire ;) .

Aussi, pensez qu'un backtracking appliqué à une grille vide fournit une grille remplie (la première possible). En assignant à chaque case une liste de valeurs ordonnée aléatoirement pour l'énumération des possibilités, on peut obtenir une grille remplie aléatoirement. Mais cela n'est pas l'objet de ce tuto ;)

Bien entendu, il est possible de mettre en place des algorithmes plus sophistiqués pour résoudre un sudoku. Vous pouvez évidement vous inspirer des méthodes de résolution utilisées par les vrais joueurs pour cela.

En pratique, le backtracking présenté ici n'est pas la meilleure méthode de résolution pour le sudoku, et sera par exemple impraticable pour des grilles extrêmes (25x25). Faites un tour ici pour avoir un aperçu des autres approches connues.

Enfin, pour les curieux, sachez que le problème de savoir s'il existe une solution pour une grille de sudoku est classé NP-complet, ce qui revient à dire qu'aucune méthode n'est connue à ce jour pour trouver efficacement la réponse pour une grille $N^2 \times N^2$ avec $N$ un peu grand (même s'il n'existe pas non plus de preuve que ce soit impossible :p ).


Comme vous avez pu le voir, cette méthode du retour sur trace permet de résoudre certains types de problèmes assez facilement et efficacement. Et nous avons vu par ailleurs que cette technique reste quand même assez limitée.

Décider si une solution de ce type est adaptée à un problème n'est pas toujours aussi évident que pour le problème du sudoku. L'étape de modélisation d'un problème reste très importante, et seule une bonne modélisation du problème permettra de savoir si le backtracking est une solution potentielle ou non.

Pour vous familiariser avec le backtracking et ses subtilités, vous pouvez aller voir ces autres grands classiques : problème des N reines, perles de Dijkstra

11 commentaires

Je tiens à préciser que ce tuto est le rapatriement de mon tuto depuis le SdZ (lien). Il y en a d'autres, mais je ne sais pas s'ils en valent la peine.

le langage C99/C++

Mes yeux brulent

En dehors du code lui même qui n'est pas du C++, c'est bien écrit et intéressant !

Davidbrcz

Il va de soi que je veux dire le langage C99 OU C++.

C'est vrai que ça fait bizarre de dire que j'ai choisi le langage C99 OU C++, je veux simplement dire que le code est compilable dans les deux langages. Et oui, en fait c'est bien du C99.

L'idée est qu'un mec qui ne sait pas ce qu'est le C99 puisse compiler en C++ sans se prendre la tête.

Édité

+0 -0

Merci pour ton tuto. :)

Au sujet de ton code source, comment dire … Les autres Zeste n'ont pas dû l'avoir testé (je parle du code complet).

Tu ne retournes à aucun moment le tableau "grille".

1
2
3
4
5
6
7
    printf("Grille avant\n");
    affichage(grille);

    estValide(grille,0);

    printf("Grille apres\n");
    affichage(grille);

Du coup, ta méthode main() ne peut pas fonctionner. La fonction estValide() devrait retourner la grille du Sudoku.

Voici donc mon code Python (oui je l'ai recodé) avec la rectif juste pour les tests (faudrait faire mieux que ça) :

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
#!/usr/bin/python3
import os

def absentSurLigne (k, grille, i):
  for j in range(0,9):
      if grille[i][j] == k:
          return 0
  return 1

def absentSurColonne (k, grille, j):
  for i in range(0,9):
      if grille[i][j] == k:
          return 0
  return 1

def absentSurBloc (k, grille, i, j):
  xi = i-(i%3)
  xj = j-(j%3)
  for i in range(xi,xi+3):
      for j in range(xj,xj+3):
          if grille[i][j] == k:
              return 0
  return 1

def estValide (grille, position):

  os.system("cls")
  affichage(grille)

  # SORTIE DU TABLEAU
  if position == 9*9:
      return 1

  # COORDONNEES
  i = int(position/9)
  j = position%9

  # CHANGE DE CASE
  if not grille[i][j] == 0:
      return estValide(grille, position+1)

  # BACKTRACKING
  for k in range(1,10): # correction
      testA = absentSurLigne(k,grille,i)
      testB = absentSurColonne(k,grille,j)
      testC = absentSurBloc(k,grille,i,j)
      if testA == 1 and testB == 1 and testC == 1:
          grille[i][j] = k
          if estValide(grille, position+1) == 1:
              return 1
  grille[i][j] = 0
  return 0

def affichage (grille):
  for i in range(0,9):
      line = ""
      for j in range(0,9):
          line += str(grille[i][j])
          line += " " if ((j+1)%3) else "|"
      print(line)
      if not ((i+1)%3):
          print("------------------")

def main ():
  grille = [
      [9,0,0,1,0,0,0,0,5],
      [0,0,5,0,9,0,2,0,1],
      [8,0,0,0,4,0,0,0,0],
      [0,0,0,0,8,0,0,0,0],
      [0,0,0,7,0,0,0,0,0],
      [0,0,0,0,2,6,0,0,9],
      [2,0,0,3,0,0,0,0,6],
      [0,0,0,2,0,0,9,0,0],
      [0,0,1,9,0,4,5,7,0]
  ]
  estValide(grille,0)

main()

Le problème c'est que ça ne fonctionne pas.

L'algorithme s'arrête sur cette grille :

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
9 7 6|1 3 8|4 0 5|
0 0 5|0 9 0|2 0 1|
8 0 0|0 4 0|0 0 0|
------------------
0 0 0|0 8 0|0 0 0|
0 0 0|7 0 0|0 0 0|
0 0 0|0 2 6|0 0 9|
------------------
2 0 0|3 0 0|0 0 6|
0 0 0|2 0 0|9 0 0|
0 0 1|9 0 4|5 7 0|
------------------

Édité

Tant de choses, tant de vies, tant de possibilités.

+0 -0

La fonction estValide() devrait retourner la grille du Sudoku.

Pourquoi ? La fonction travaille avec un tableau (~un pointeur) ce qui permet de modifier les éléments

Je viens de tester, le code marche bien.

Édité

+0 -0

Okay, ça fonctionne. J'ai fait une erreur à la ligne 43, il faut écrire range(1,10) au lieu de range(1,9).

Pour ce qui est de l'arrêt, je persiste. Si les variables sont globales en C99, c'est un langage très mal implémenté. Normalement on devrait retourner la matrice. Je vais regarder comment le modifier.

Sinon c'est plus rapide en JS qu'en Python (faut créer une balise <xmp> en HTML) :

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
var sudoku = (function () {
  var self = {};
  self.output = [];

  self.absentSurLigne = function (k, grille, i) {
      for(var j=0; j < 9; j++) {
          if(grille[i][j] == k) {
              return false;
          }
      }
      return true;
  };

  self.absentSurColonne = function (k, grille, j) {
      for(var i=0; i < 9; i++) {
          if(grille[i][j] == k) {
              return false;
          }
      }
      return true;
  };

  self.absentSurBloc = function (k, grille, i, j) {
      var xi = i-(i%3);
      var xj = j-(j%3);
      for(var i=xi; i < xi+3; i++) {
          for(var j=xj; j < xj+3; j++) {
              if(grille[i][j] == k) {
                  return false;
              }
          }
      }
      return true;
  };

  self.estValide = function (grille, position) {
      this.output = grille;

      // SORTIE DU TABLEAU
      if(position == 9*9) {
          return true;
      }

      // COORDONNEES
      var i = Math.floor(position/9);
      var j = position%9;

      // CHANGE DE CASE
      if(grille[i][j] != 0) {
          return this.estValide(grille, position+1);
      }

      // BACKTRACKING
      for(var k=1; k < 10; k++) {
          var testA = this.absentSurLigne(k,grille,i);
          var testB = this.absentSurColonne(k,grille,j);
          var testC = this.absentSurBloc(k,grille,i,j);
          if(testA && testB && testC) {
              grille[i][j] = k;
              if(this.estValide(grille, position+1)) {
                  return true;
              }
          }
      }

      grille[i][j] = 0;
      return false;
  };

  self.affichage = function (grille) {
      for(var i=0; i < 9; i++) {
          var line = "";
          for(var j=0; j < 9; j++) {
              line += grille[i][j];
              line += (((j+1)%3) ? " " : "|");
          }
          this.print(line+"\n");
          if(!((i+1)%3)) {
              this.print("------------------\n");
          }
      }
      this.print("\n\n");
  };

  self.print = function (msg) {
      var obj = document.querySelector('xmp');
      if(msg !== undefined) {
          obj.innerHTML += msg;
      } else {
          obj.innerHTML = "";
      }
  };

  self.main = function () {
      var grille = [
          [9,0,0,1,0,0,0,0,5],
          [0,0,5,0,9,0,2,0,1],
          [8,0,0,0,4,0,0,0,0],
          [0,0,0,0,8,0,0,0,0],
          [0,0,0,7,0,0,0,0,0],
          [0,0,0,0,2,6,0,0,9],
          [2,0,0,3,0,0,0,0,6],
          [0,0,0,2,0,0,9,0,0],
          [0,0,1,9,0,4,5,7,0]
      ];
      this.affichage(grille);
      this.estValide(grille, 0);
      this.affichage(this.output);
      return self;
  };

  return self;
})().main();

Ça donne ce résultat :

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
9 3 4|1 7 2|6 8 5|
7 6 5|8 9 3|2 4 1|
8 1 2|6 4 5|3 9 7|
------------------
4 2 9|5 8 1|7 6 3|
6 5 8|7 3 9|1 2 4|
1 7 3|4 2 6|8 5 9|
------------------
2 9 7|3 5 8|4 1 6|
5 4 6|2 1 7|9 3 8|
3 8 1|9 6 4|5 7 2|

Édité

Tant de choses, tant de vies, tant de possibilités.

+0 -0

Pour ce qui est de l'arrêt, je persiste.

Je viens de re-tester, et le code fonctionne bien… Tu as un exemple qui ne va pas ?

Si les variables sont globales en C99, c'est un langage très mal implémenté. Normalement on devrait retourner la matrice. Je vais regarder comment le modifier.

Yarflam

C'est du grand n'importe quoi, où est-ce que tu as vu une variable globale ici ?

Simplement, pour des raisons évidentes d'efficacité, on utilise autant que possible le passage pas référence plutôt que par copie lorsqu'on fait du backtracking, du coup il est parfaitement inutile de retourner le tableau, puisqu'il est modifié en place.

Édité

+0 -0

Non c'est bon, je viens de retester l'ensemble. Ça fonctionne. C'était sans doute lié à la première erreur. Le tableau repartait depuis zéro pour je ne sais quelle raison. Excusez moi.

Tant de choses, tant de vies, tant de possibilités.

+0 -0

Très bon tuto :)

Est-ce que ce paradigme de programmation est proche de la "programmation dynamique" ? (Je ne sais pas si c'est une appellation officielle ..)

PS : L'avant dernier lien wikipédia (problème des N reines) ne fonctionne pas.

Édité

+0 -0

Est-ce que ce paradigme de programmation est proche de la "programmation dynamique" ? (Je ne sais pas si c'est une appellation officielle ..)

Non, c'est sans rapport.

PS : L'avant dernier lien wikipédia (problème des N reines) ne fonctionne pas.

Merci, je vais corriger.

EDIT: il semble que c'est un problème dû au site, en édition le lien est le bon (http://fr.wikipedia.org/wiki/Probl%C3%A8me_des_huit_dames), mais à l'affichage ça devient http://fr.wikipedia.org/wiki/Probl%25C3%25A8me_des_huit_dames.

Édité

+0 -0
Vous devez être connecté pour pouvoir poster un message.
Connexion

Pas encore inscrit ?

Créez un compte en une minute pour profiter pleinement de toutes les fonctionnalités de Zeste de Savoir. Ici, tout est gratuit et sans publicité.
Créer un compte