Satisfaction de contraintes

Dans cette série, vous allez programmer des algorithmes de résolution de satisfaction de contraintes que vous appliquerez au Sudoku la semaine prochaine.

Durée estimée : 2 heures.

Objectifs de la série

  • Comprendre la consistance de nœuds et d’arcs.
  • Programmer l’algorithme de recherche backtrack.

Satisfaction de contraintes

Les fichers psc/Variable.py et psc/Contrainte.py implémentent les classes Variable et Contrainte (unaire ou binaire), tandis que le ficher psc.py implémente une libraire pour la gestion d’un ensemble de variables et de contraintes ainsi que la résolution d’un système de contraintes.

Commencez par lire et comprendre ces fichiers.

Exercice 1 : Consistance des noeuds et des arcs

Comme vous pouvez le constater dans le ficher psc.py, les fonctions consistance_noeuds et consistance_arcs ne sont pas remplies. Complétez ces fonctions.

Note

La fonction consistance_noeuds doit appeler la méthode est_valide de la classe ContrainteUnaire du fichier contrainte.py, que vous devez aussi compléter.

La fonction consistance_arcs doit appeler la méthode reviser de la classe ContrainteBinaire du fichier contrainte.py, qui implémente l’algorithme de Walz (consistance d’un arc), que vous devez aussi implémenter. Notez bien que, les contraintes binaires étant bidirectionnelles, vous devez implémenter la fonction reviser de telle sorte que les domaines des deux variables de la contrainte binaire soient réduits (si possible) par l’appel à la fonction reviser.

À son tour, la méthode reviser s’appuie sur les méthodes est_valide et est_possible de la classe ContrainteBinaire, que vous devez aussi compléter.

Enfin, testez votre programme sur le fichier test.py (affichez le domaine des variable après l’utilisation des algorithmes de consistance et commentez l’appel au backtracking).

Exercice 2 : Algorithme de backtrack

Le backtrack est un algorithme de recherche en profondeur d’abord :

  • noeud de recherche = instanciation de variables x1 = v1, x2 = v2, ..., xk = vk (où k est la profondeur du noeud dans l’arbre de recherche)
  • fonction de successeur = instanciation de la variable xk+1 = vk+1 de manière à respecter toutes les contraintes pour les variables x1, ..., xk
  • nœud initial = instanciation vide
  • nœud but = instanciation de toutes les variables x1, ..., xn

Programmez l’algorithme ci-dessous:

SOLUTIONS = []
VARIABLES = [v1,v2, ...,vn]

Backtrack(k, une_seule_solution)
  1. IF k >= n THEN
  2.   IF not une_seule_solution THEN
  3.     ajoute la solution actuelle à SOLUTIONS
  4.   ELSE
  5.     RETURN SOLUTIONS = [solution actuelle]
  6.   END IF
  7. ELSE
  8.   v = VARIABLES[k]
  9.   FOR ALL valeur de domaine d de la variable v
 10.     assigne la valeur d à la variable v
 11.     vérifie la consistance de v=d avec les variables précédentes
 12.     IF v=d est consistant THEN
 13.       reste = Backtrack(k+1, une_seule_solution)
 14.       IF reste != echec THEN
 15.         RETURN reste
 16.       END IF
 17.     END IF
 18.   END FOR
 19. END IF
 20. RETURN echec
 END Backtrack

L’algorithme prend 2 paramètres:

  • k : la profondeur courante (commence à 0).
  • une_seule_solution : si vraie, alors retourne la première solution trouvée, sinon retourne toutes les solutions possibles.

Les solutions seront stockées dans la variable de classe self.solutions, et chaque solution sera représentée par un dictionnaire qui, à un nom de variable donné, associera la valeur de cette variable.

Les étapes 11 et 12 de l’algorithme ci-dessus seront implémentées à l’aide de la fonction consistance_avec_vars_precedentes, que vous devez compléter.

Note

Au lieu de retourner ‘echec’ lancez l’exception NonSatisfiable implémentée dans exceptions.py

Ensuite, testez votre algorithme sur le fichier test.py.