Qu’est-ce que la programmation par contraintes ? Quels en sont les avantages et les limites ? Peut-on faire en une heure un algorithme qui résout les Sudoku ?
Une de ces réponses est oui.
Introduction
Commençons par le commencement : Qu’est-ce que la programmation par contraintes ?
La PPC est un paradigme de programmation déclaratif, qui consiste à résoudre un problème en définissant les propriétés de sa solution plutôt que le problème lui-même. De tous les paradigmes de programmation, c’est à mon avis le plus élégant. Contrairement aux approches “classiques” basés sur une suite de blocs d’executions, on va ici se concentrer sur la déclaration de variables du problème et les contraintes qu’elles entretiennent entre elles. On se concentre sûr qu’est-ce qui défini le problème plutôt que comment le résoudre.
Ces contraintes sont ensuite satisfaites par un moteur de propagation de contraintes, qui nous dissimule la complexité de l’algorithme et nous redonne directement nos variables, réduites par les contraintes.
Un des avantages à travailler sur les contraintes de la solution plutôt que la façon de résoudre le problème est un des aspects le plus pratique de la PPC: Il est possible de prouver l’inexistence d’une solution, et ce très rapidement. La propagation des contraintes est un processus assez lourd, mais dans le cas d’un problème avec un ensemble de contraintes incompatibles, un état contradictoire est atteint très rapidement.
En résumé, voici les utilisations principales de cette méthode :
- Prouver l’existence d’une solution
- Prouver l’inexistence d’une solution
- Résoudre des problèmes non linéaires facilement (en robotique par exemple)
Avantages
Si le problème à résoudre s’y prête, programmer avec cette méthode est bien plus rapide que d’implémenter soit même un algorithme. L’exemple de résolution de Sudoku a la fin de ce post est assez parlant : Il m’a fallu une soirée, soit quelques heures de travail pour faire l’ensemble du programme de chargement d’un sudoku via OpenCV et sa résolution.
Le fait de pouvoir prouver qu’une solution n’existe pas sans calculer l’ensemble des solutions est également un avantage majeur de la PPC. Pour l’exemple du Sudoku, le programme peut déterminer très rapidement si l’utilisateur a rentré une grille impossible.
L’utilisation de contraintes différentielles permet de résoudre facilement des problèmes complexes en robotique, notamment des problèmes d’estimation d’état non linéaires, qui sont assez difficiles à résoudre avec les méthodes “classiques”. La PPC permet de traiter simplement les problèmes du “robot kidnappé”, de délais entre les données ou d’estimation de position.
Inconvénients
Évidemment et comme toujours dans la vie, rien n’est parfait et la PPC vient (ironiquement) avec son lot de contraintes.
Premièrement, la propagation des contraintes est un processus lourd en mémoire et CPU pour un ordinateur. Selon les méthodes, la propagation s’effectue à ma connaissance sur des graphs ou des matrices. Ce n’est donc pas vraiment une méthode portable, et une implémentation microcontrôleur efficace est pour le moment inexistante.
De plus, la PPC nous donne en sortie les variables d’entrée réduites au maximum. Même dans le cas où les variables sont réduites au maximum, elles restent comprises dans un interval de solutions. Eeeet oui, comme précisé dans l’introduction, la PPC donne l’ensemble des solutions possibles, sans distinctions. Si cet interval est grand, dans un contexte non discret comme l’estimation de la position d’un robot mobile, la PPC pourrait ne pas suffire.
À mon avis, la PPC ne devrait pas être utilisée seule, et nécessite d’autres algorithmes pour affiner les résultats.
Deuxièmement, la PPC est extrêmement sensible aux données aberrantes (outliers). Ces données sont normalement extrêmement rares, mais peuvent tout de même survenir et entrer dans notre système. Un outlier peut produire une contrainte incompatible, ce qui empêchera notre système de trouver une solution.
Exemple du Sudoku
Un petit exemple ? Essayez de visualiser un algorithme pour résoudre un Sudoku…
Comment gérer l’existence de plusieurs solutions ? Ajouter des contraintes de mouvements de cavaliers, une résolution d’un carré magique pour le carré central, un changement de layout, … On s’imagine assez rapidement des schémas de résolution assez complexes, mais ce genre d’algorithmes demanderait un certain temps à écrire et à tester. De plus une approche rapide et naïve serait assez difficile à adapter a des cas plus larges comme ceux mentionnés précédemment.
En utilisant la programmation par contraintes, il nous suffit de faire la liste des variables du problème (ici, l’ensemble des cases du Sudoku) et d’écrire les contraintes qui lient ces variables entre elles.
Il se trouve que j’ai déjà réalisé un petit projet en Python utilisant la PPC pour résoudre ce problème.
Dans le fichier “SudokuSolver.py”, la fonction set_constraints est responsable de la déclaration des variables (81 pour une grille de 9 * 9 cases) puis des contraintes.
Le cœur de l’algorithme final se résume en 81 + 27 contraintes :
- Chaque case peut prendre une valeur de 1 à 9, sauf les cases déjà remplies qui sont fixes
- 9 lignes dont chaque case doit avoir une valeur différente
- 9 colonnes dont chaque case doit avoir une valeur différente
- 9 carrés dont chaque case doit avoir une valeur différente