Lab 6b : Satisfaction de contraintes


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

Durée estimée : 2 heures.

Fichiers :

libPSCTemplate.py
PSCTemplate.py
sudoku.py
test.py.

Objectifs de la série

Exercice 1 : Variable Ordering

Comme vous avez pu le constater lors du backtracking, les variables sont instanciées les unes après les autres d'après l'ordre où elles apparaissent dans VARIABLES. L'heuristique Variable Ordering (VO) va trier les variables de façon à instancier les variables avec les plus petits domaines en premier. L'idée est d'instancier en premier les variables les plus restrictives car ce sont elles qui ont le plus de chances d'aboutir à une instanciation inconsistante et donc à un backtracking.

Implémentez cet algorithme, et vérifiez s'il améliore la performance de l'algorithme de backtracking sur le fichier test.py.

Indication : Comme dans le labo 5, appelez la méthode sort() de la liste VARIABLES, mais cette fois-ci en donnant comme paramètre key à la méthode sort() une fonction lambda qui retourne la taille du domaine. Vous pouvez vous inspirer de la documentation ici. 

Exercice 2 : Algorithme Forward Checking

Afin d'améliorer la recherche (par rapport au backtracking), des heuristiques peuvent être employées. L'heuristique que vous devez programmer est le Forward Checking. Elle a pour but d'éviter à l'avance des instanciations inconsistantes en appliquant le critère de la consistance des arcs pendant la recherche. Pour cela, il faut ajouter un label label[i] à chaque variable, qui sera initialement égal à son domaine. Le Forward Checking met à jour ces labels en appliquant la règle suivante : à chaque instanciation d'une variable xk, éliminer toutes les valeurs inconsistantes avec xk des labels des variables qui ne sont pas encore instanciées.

L'algorithme de Forward Checking que vous allez implémenter est le suivant : 

 
  SOLUTIONS = []
  VARIABLES = [v1, v2, ..., vn]
 
  ForwardChecking(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.   sauvegardeDesLabels <- labels des variables vk, ..., vn
   10.   FOR ALL valeur de label v de la variable var DO
   11.     assigne la valeur v à la variable var
   12.     réduit le label de var à la seule valeur v
   13.     propage var=v aux labels des variables suivantes
   14.     IF var=v est consistant THEN
   15.       reste = forwardChecking(k+1, toutesLesSolutions)
   16.       IF reste != echec THEN
   17.         RETURN reste
   18.       END IF
   19.     END IF
   20.     labels des variables <- sauvegardeDesLabels   
   21.   END DO
   22. END IF
   23. RETURN echec
  END ForwardChecking
 

L'algorithme prend 2 paramètres :


La solution sera stockée 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 13 et 14 de l'algorithme ci-dessus seront implémentées à l'aide de la fonction propageAuxVarsSuivantes, que vous devez compléter. Pour chaque contrainte portant sur la variable courante et sur au moins une deuxième variable non encore instanciée, cette fonction va appeler la méthode propage de cette contrainte pour tenter de réduire le label de cette deuxième variable. Vous devez aussi implémenter cette méthode propage de la classe ContrainteBinaire, qui, pour chaque valeur possible de la deuxième variable, vérifie si cette valeur est consistante avec la contrainte, et sinon, la retire du label de la variable. Les deux méthodes propageAuxVarsSuivantes et propage devront retourner True si les contraintes peuvent être satisfaites, et False si au moins une des variables non encore instanciées n'a plus aucune valeur possible dans son label après propagation.


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

Exercice 3 : Dynamic Variable Ordering

L’heuristique Variable Ordering (VO) trie la liste des variables une seule fois, et avant la recherche. Une heuristique encore plus efficace est Dynamic Variable Ordering (DVO), qui, à chaque étape de la recherche, trie la liste des variables par ordre croissant de la taille du label. A chaque étape k, l’idée est de retrier la liste des variables, mais seulement à partir de la position k (car le forward checking vérifie la consistance des variables non instanciées).

Implémentez cet algorithme, et appelez-le dans l'algorithme de Forward Checking entre les lignes 7 et 8 de l'algorithme ci-dessus.

Indication : Vous n’avez pas besoin de trier toute la liste : il est beaucoup plus efficace de chercher la variable avec le plus petit label (depuis la position k) et de l’inverser avec la variable à la position k (en supposant que vous êtes à l’étape k). Pour interchanger les valeurs de deux variables a et b, utilisez la syntaxe suivante : a, b = b, a.


Testez à nouveau votre algorithme sur le fichier test.py.

Exercice 4 : Sudoku

Afin de comprendre plus en détail ces algorithmes, testez-les sur le fichier contenant le jeu sudoku.py. Essayez votre algorithme avec la grille A et B. Que constatez-vous?

Essayez maintenant d'utiliser le backtracking. Que constatez-vous?

Copyright LIA – 2006-2007. Author: vincent.schickel-zuber@epfl.ch - le 3 Mai 2006 - Last modified 4th April 2011 by Florent Garcin