Lab 6 : 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 (lab 7).

Durée estimée : 2 heures.

Fichiers

• libPSCTemplate.py
• PSCTemplate.py
• test.py

Objectifs de la série

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

Satisfaction de contraintes

Le ficher libPSCTemplate.py implémente une libraire pour la gestion d’une variable et d’une contrainte (unaire ou binaire), tandis que le ficher PSCTemplate.py implémente une libraire pour la gestion d’un ensemble de variables et de contraintes.

Commencez par lire et comprendre ces fichiers.

Exercice 1 : Consistance des nœuds et des arcs

Comme vous pouvez le constater dans le ficher PSCTemplate.py, les fonctions consistanceDesNoeuds() et consistanceDesArcs() ne sont pas remplies. Complétez ces fonctions.

Note

la fonction consistanceDesArcs doit appeler la méthode reviser() de la classe ContrainteBinaire du fichier libPSCTemplate.py, qui implémente l’algorithme de Walz (consistance d’un arc), et que vous devez aussi implémenter.

Notez bien que, les contraintes binaires étant bidirectionnelles, vous devez implémenter cette 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.

Enfin, testez votre programme sur le fichier testPSC.py.

Exercice 2 : Algorithme de Backtrack

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

• nœud de recherche = instanciation de variables x₁ = v₁, x₂ = v₂, ..., x_k = v_k (où k est la profondeur du nœud dans l’arbre de recherche)
• fonction de successeur = instanciation de la variable x_k+1 = v_k+1 de manière à respecter toutes les contraintes pour les variables x₁, ..., x_k
• nœud initial = instanciation vide
• nœud but = instanciation de toutes les variables x₁, ..., x_n

Programmez l’algorithme ci-dessous (similaire à celui de la Figure 8.7).

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

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

L’algorithme prend 2 paramètres :

• k : la profondeur courante (commence à 0)
• toutesLesSolutions : si vraie, alors retourne toutes les solutions possibles ; sinon, retourne la première

Les solutions seront stockées dans la variable globale 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 consistanceAvecVarsPrecedentes, que vous devez compléter.

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