Modéliser un problème par des contraintes

Le parcours sur la recherche traitait un problème comme une boîte noire : un état initial, un ensemble d’actions, un test de but. Cela fonctionne, mais le solveur n’apprend rien sur les raisons pour lesquelles un état est mauvais. Un problème de satisfaction de contraintes ouvre la boîte. Énoncez le problème sous une forme standard et un solveur générique pourra raisonner sur sa structure sans savoir de quoi il parle.

La forme standard

Un PSC, c’est trois choses.

• Un ensemble de variables $X_1, \dots, X_n$.
• Un domaine $D_i$ pour chacune, les valeurs qu’elle peut prendre.
• Un ensemble de contraintes, chacune restreignant les valeurs qu’un sous-ensemble de variables peut prendre simultanément.

Une affectation donne des valeurs à une partie ou à la totalité des variables. Elle est cohérente si elle ne viole aucune contrainte, complète si chaque variable a une valeur, et c’est une solution si elle est les deux à la fois.

L’exemple : colorier une carte

Coloriez chaque région de l’Australie de sorte que deux régions voisines n’aient jamais la même couleur. Sept variables - l’Australie-Occidentale, le Territoire du Nord, le Queensland, la Nouvelle-Galles du Sud, le Victoria, l’Australie-Méridionale et la Tasmanie - chacune de domaine $\{\text{red}, \text{green}, \text{blue}\}$, et une contrainte par frontière commune :

$$\mathrm{WA} \neq \mathrm{NT},\quad \mathrm{WA} \neq \mathrm{SA},\quad \mathrm{NT} \neq \mathrm{SA},\quad \mathrm{NT} \neq \mathrm{Q},\quad \mathrm{SA} \neq \mathrm{Q},$$ $$\mathrm{SA} \neq \mathrm{NSW},\quad \mathrm{SA} \neq \mathrm{V},\quad \mathrm{Q} \neq \mathrm{NSW},\quad \mathrm{NSW} \neq \mathrm{V} .$$

Neuf contraintes. La Tasmanie est une île : elle n’apparaît dans aucune d’elles.

Le graphe de contraintes

Tracez un nœud par variable et une arête par contrainte binaire et vous obtenez le graphe de contraintes. Sa forme est la seule carte du problème dont dispose le solveur, et ce qu’il est le plus utile d’y lire est le degré, le nombre de contraintes auxquelles une variable participe :

$$\begin{array}{ll} \mathrm{SA} & 5 \\ \mathrm{NT},\ \mathrm{Q},\ \mathrm{NSW} & 3 \\ \mathrm{WA},\ \mathrm{V} & 2 \\ \mathrm{T} & 0 \end{array}$$

L’Australie-Méridionale borde toutes les régions continentales. Choisir sa couleur restreint immédiatement cinq autres variables, et c’est pourquoi la troisième leçon affecte tôt les variables de degré élevé. La Tasmanie ne restreint rien, sa couleur est donc libre : cela seul vous indique que les solutions vont par groupes de trois.

Il y a 18 coloriages propres au total, six coloriages continentaux distincts multipliés par trois choix pour la Tasmanie.

Coloriez vous-même ci-dessous, et surveillez le second affichage plutôt que le premier. Il compte les coloriages propres qui prolongent encore ce que vous avez affecté, et il corrige deux lectures du paragraphe précédent.

Fixer une seule région laisse exactement six complétions. L’Australie-Méridionale avec cinq frontières, la Tasmanie avec aucune : six dans les deux cas, car les trois couleurs sont interchangeables et chaque région prend donc chaque couleur dans un tiers des solutions. Un degré élevé achète moins de recherche, non moins de réponses. La thèse est plus faible qu’elle n’en a l’air, et c’est celle dont la leçon sur les heuristiques a réellement besoin.

Appuyez ensuite sur l’impasse silencieuse. L’Australie-Occidentale en rouge avec le Queensland en vert ne viole aucune contrainte, et compte zéro complétion : le Territoire du Nord et l’Australie-Méridionale n’ont plus que le bleu, et ils se touchent. Une affectation partielle cohérente n’est pas forcément extensible. Rien dans la forme standard ne s’en aperçoit, et c’est précisément pour cela que la leçon suivante existe.

La commutativité, et pourquoi elle vaut 5 040

Une recherche naïve traiterait « affecter WA, puis NT » et « affecter NT, puis WA » comme deux branches différentes. Comptez les feuilles de cet arbre : $n!$ ordres multipliés par $d^n$ combinaisons de valeurs,

$$7! \times 3^7 = 5{,}040 \times 2{,}187 = 11{,}022{,}480 .$$

Mais les PSC sont commutatifs : appliquer un ensemble d’affectations dans n’importe quel ordre mène à la même affectation partielle. L’ordre ne porte donc aucune information, et un solveur peut fixer une seule variable par niveau de l’arbre. Le nombre de feuilles devient

$$d^n = 3^7 = 2{,}187 ,$$

soit un facteur $5{,}040$ de moins, et rien n’a été abandonné. Ce n’est ni une heuristique ni une approximation : c’est une redondance de la formulation naïve qui n’aurait jamais dû s’y trouver. Tous les algorithmes de ce parcours la supposent acquise.

La même forme, d’autres problèmes

L’intérêt d’une forme standard, c’est que des problèmes sans rapport y entrent.

• Ordonnancement. Une variable par tâche, valuée par sa date de début. La contrainte de précédence disant que la tâche $T_1$, de durée $d_1$, se termine avant que $T_2$ ne commence s’écrit $T_1 + d_1 \le T_2$. Une échéance est une restriction sur chaque domaine. Un outil partagé devient une contrainte disjonctive : soit $A + 10 \le B$, soit $B + 10 \le A$.
• Sudoku. Quatre-vingt-une variables, une par case, de domaine $\{1, \dots, 9\}$, avec des domaines singletons pour les cases données. Vingt-sept contraintes de différence deux à deux, une par ligne, par colonne et par bloc.
• Huit reines. Une variable par colonne, valuée par la ligne, avec des contraintes interdisant deux reines sur une même ligne ou une même diagonale.

Aucun de ces problèmes n’exige un solveur sur mesure. Le même code s’applique aux trois parce que le raisonnement qu’il mène - réduire les domaines, choisir la prochaine variable à essayer - est piloté par les contraintes, et non par le sujet traité.

La forme est standard ; la difficulté ne l’est pas. La satisfaction de contraintes est NP-complète en général, et écrire un problème sous cette forme ne le rend pas facile. Ce qu’on y gagne, c’est que toute l’ingéniosité peut vivre dans un seul solveur au lieu d’être réinventée pour chaque problème.

Au-delà des domaines finis

Les domaines n’ont pas besoin d’être petits, ni même finis. Un domaine discret peut être infini, comme les entiers, auquel cas les contraintes ne peuvent plus être énumérées sous forme de paires autorisées et il faut un langage de contraintes pour exprimer directement $T_1 + d_1 \le T_2$. Les contraintes linéaires sur les entiers ont des solveurs spécialisés ; les contraintes non linéaires générales sur les entiers n’en ont aucun, et ne peuvent pas en avoir, puisqu’aucun algorithme pour elles n’existe.

Avant le quiz

Sachez écrire un problème sous forme de variables, de domaines et de contraintes, tracer le graphe de contraintes et y lire le degré, expliquer ce que la commutativité supprime et ce qu’elle vaut ici, et reconnaître la même forme dans l’ordonnancement et le Sudoku.