12.4 Le Sodoku
205
12.4 Le Sodoku
Un problème de Sodoku est une matrice 9x9 telle que chaque ligne et chaque colonne
ne contient qu'une seule fois les entiers de 1 à 9. Une grille 9x9 est décomposée en
carrés 3x3. En plus des contraintes sur les lignes et les colonnes, chaque carré 3x3 ne doit
contenir qu'une seule fois les chiffres de 1 à 9.
Il n'y a que 9 valeurs possibles pour chaque entrée de la matrice.
Exercice : Utiliser le Backtrack pour résoudre le Sodoku.
12.5 Le Forward Checking
Dans l'algorithme Forward Checking, après chaque affectation d'une valeur à une variable, on ôte des domaines des variables restantes les valeurs qui ne sont pas compatibles
avec l'affectation. Cette mise à jour à chaque affectation des domaines de chaque variable
permet de détecter les domaines contraints et les domaines vides.
Exercice : Modifier le programme de résolution de Sodoku pour qu'il fasse du forward
checking.
12.6 L'ordre d'instanciation des variables
Lorsqu'on explore un arbre entièrement l'ordre d'instanciation des variables importe
peu, mais si on permet de couper l'arbre dès qu'une contrainte n'est plus vérifiée comme
pour l'algorithme de Backtrack, il est alors préférable de couper le plus tôt possible une
branche qui ne va pas amener à la solution. On va donc essayer d'instancier en priorité
les variables qui amènent à violer une contrainte; cette heuristique s'appelle le principe
de l'échec d'abord. On peut choisir l'ordre des variables une fois pour toutes avant l'exécution ou dynamiquement lors de l'exécution.
Une bonne heuristique statique est l'heuristique de cardinalité maximum qui consiste
à choisir la variable qui est liée par des contraintes au plus grand nombre de variables déjà
choisies. On peut aussi prendre en compte la taille du domaine de la variable, le nombre de
contraintes dans lesquelles la variable est présente ou encore la difficulté des contraintes
contenant la variable.
Une bonne heuristique dynamique est de choisir la variable ayant le nombre minimal
de valeurs vérifiant les contraintes étant donné les instanciations déjà effectuées.
L'ordre d'instanciation des valeurs n'a pas d'influence sur les problèmes inconsistant
ou sur les problèmes où l'on cherche toutes les solutions, car il faudra vérifier toutes les
205
12.4 Le Sodoku
Un problème de Sodoku est une matrice 9x9 telle que chaque ligne et chaque colonne
ne contient qu'une seule fois les entiers de 1 à 9. Une grille 9x9 est décomposée en
carrés 3x3. En plus des contraintes sur les lignes et les colonnes, chaque carré 3x3 ne doit
contenir qu'une seule fois les chiffres de 1 à 9.
Il n'y a que 9 valeurs possibles pour chaque entrée de la matrice.
Exercice : Utiliser le Backtrack pour résoudre le Sodoku.
12.5 Le Forward Checking
Dans l'algorithme Forward Checking, après chaque affectation d'une valeur à une variable, on ôte des domaines des variables restantes les valeurs qui ne sont pas compatibles
avec l'affectation. Cette mise à jour à chaque affectation des domaines de chaque variable
permet de détecter les domaines contraints et les domaines vides.
Exercice : Modifier le programme de résolution de Sodoku pour qu'il fasse du forward
checking.
12.6 L'ordre d'instanciation des variables
Lorsqu'on explore un arbre entièrement l'ordre d'instanciation des variables importe
peu, mais si on permet de couper l'arbre dès qu'une contrainte n'est plus vérifiée comme
pour l'algorithme de Backtrack, il est alors préférable de couper le plus tôt possible une
branche qui ne va pas amener à la solution. On va donc essayer d'instancier en priorité
les variables qui amènent à violer une contrainte; cette heuristique s'appelle le principe
de l'échec d'abord. On peut choisir l'ordre des variables une fois pour toutes avant l'exécution ou dynamiquement lors de l'exécution.
Une bonne heuristique statique est l'heuristique de cardinalité maximum qui consiste
à choisir la variable qui est liée par des contraintes au plus grand nombre de variables déjà
choisies. On peut aussi prendre en compte la taille du domaine de la variable, le nombre de
contraintes dans lesquelles la variable est présente ou encore la difficulté des contraintes
contenant la variable.
Une bonne heuristique dynamique est de choisir la variable ayant le nombre minimal
de valeurs vérifiant les contraintes étant donné les instanciations déjà effectuées.
L'ordre d'instanciation des valeurs n'a pas d'influence sur les problèmes inconsistant
ou sur les problèmes où l'on cherche toutes les solutions, car il faudra vérifier toutes les