Satisfaction de contraintes et propagation

La recherche classique traite un problème comme une boîte noire : un état initial, quelques actions, un test de but. Le solveur sait dire s’il est arrivé, mais jamais pourquoi un état est mauvais : toute son intelligence doit donc lui venir de l’extérieur, sous la forme d’une heuristique écrite à la main. La satisfaction de contraintes ouvre la boîte, et le gain est qu’un solveur unique, dépourvu de toute connaissance du domaine, peut battre une recherche sur mesure sur des problèmes qui n’ont rien en commun.

A. La forme standard

Un PSC est un ensemble de variables, un domaine de valeurs permises pour chacune, et des contraintes restreignant les combinaisons qui peuvent apparaître ensemble. Une affectation est cohérente si elle ne viole rien, complète si chaque variable a une valeur, et c’est une solution si elle est les deux.

Coloriez les sept régions de l’Australie avec trois couleurs de sorte que deux régions voisines ne se ressemblent jamais. Sept variables, de domaine $\{\text{red}, \text{green}, \text{blue}\}$, et neuf contraintes, une par frontière commune. La Tasmanie est une île et n’apparaît dans aucune d’elles.

Les contraintes binaires induisent un graphe de contraintes, dont la lecture la plus utile 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 touche toutes les régions continentales : l’affecter en contraint donc cinq autres d’un coup. La Tasmanie ne contraint rien, ce qui vous apprend déjà que les 18 solutions sont six coloriages continentaux multipliés par trois choix libres pour la Tasmanie.

La même forme avale des problèmes sans rapport. L’ordonnancement devient une variable par tâche, valuée par la date de début, avec des contraintes de précédence $T_1 + d_1 \le T_2$ et une échéance comme restriction sur chaque domaine. Le Sudoku devient 81 variables et 27 contraintes de différence deux à deux. Aucun n’exige son propre solveur.

B. La commutativité, gratuitement

Un arbre naïf distingue « affecter WA puis NT » de « affecter NT puis WA ». Comptez ses feuilles : $n!$ ordres multipliés par $d^n$ combinaisons,

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

Mais l’affectation est commutative - n’importe quel ordre mène à la même affectation partielle - l’ordre ne porte donc aucune information et un solveur peut fixer une variable par niveau. Cela donne $d^n = 2{,}187$ feuilles, un facteur 5 040 de moins, sans rien abandonner. Ce n’est pas une heuristique. C’est une redondance que la formulation naïve n’aurait jamais dû comporter.

C. La propagation, et ce qu’elle peut prouver

Avant de deviner, supprimez les valeurs qui ne peuvent figurer dans aucune solution. Une variable est cohérente d’arc par rapport à une autre lorsque chaque valeur de son domaine a un partenaire dans le domaine de l’autre qui satisfait leur contrainte. L’algorithme AC-3 impose cela partout : on tient une file d’arcs, on révise chacun en supprimant les valeurs sans soutien, et dès qu’un domaine rétrécit on rempile les arcs des voisines de cette variable, car leur soutien a pu disparaître lui aussi.

Lancez-le sur le problème australien intact et il effectue zéro révision. Chaque région a encore trois couleurs : quelle que soit la valeur envisagée, la voisine en a deux autres et rien ne peut être supprimé. La propagation n’est pas un solveur ; elle exploite les asymétries entre domaines, et au départ il n’y en a aucune. Ce qui les crée, c’est une affectation.

Faisons-en donc deux. Posez $\mathrm{WA} = \text{red}$ et $\mathrm{Q} = \text{green}$.

La vérification en avant, l’inférence utile la moins coûteuse, supprime la valeur affectée de chaque voisine non affectée. Elle laisse $\mathrm{NT} = \{\text{blue}\}$ et $\mathrm{SA} = \{\text{blue}\}$ - deux singletons, rien de vide - et la recherche continue.

La cohérence d’arc va un cran plus loin. NT est maintenant un singleton ; SA est voisine de NT ; la seule valeur restante de SA est le bleu, celle de NT aussi, le bleu perd donc son soutien et $D_{\mathrm{SA}}$ se vide. La branche est morte, et AC-3 le dit avant qu’une autre affectation ne soit faite.

Elle est bel et bien morte. Une énumération exhaustive sur les cinq régions restantes trouve zéro complétion, pour une raison assez courte pour se vérifier à la main : NT et SA doivent toutes deux éviter le rouge et le vert, elles sont donc forcées au bleu, et elles se bordent l’une l’autre.

La différence tient à la portée. La vérification en avant se propage vers l’extérieur depuis la variable qui vient d’être affectée puis s’arrête : elle ne compare donc jamais NT et SA. AC-3 propage jusqu’à ce que plus rien ne change.

La propagation est correcte : elle ne supprime jamais une valeur susceptible de figurer dans une solution. Elle n’est pas complète. Essayez de colorier l’Australie avec deux couleurs : AC-3 déclare le problème cohérent d’arc sans rien supprimer, alors qu’il n’y a zéro solution. La cohérence d’arc inspecte deux variables à la fois, et aucune paire n’est contradictoire ; ce qui est contradictoire, c’est un cycle de trois régions exigeant trois couleurs. Le voir demande la cohérence de chemin, et la $k$-cohérence complète coûte un temps et un espace exponentiels en $k$. La cohérence d’arc est le point où l’inférence reste assez bon marché pour être lancée à chaque nœud.

D. La recherche, et l’heuristique qui ne fait rien

Ce qui comble l’écart, c’est le retour arrière : une affectation en profondeur d’abord, qui revient sur ses pas quand une variable n’a plus de valeur légale. Trois heuristiques standard le pilotent.

Les valeurs restantes minimales retiennent la variable qui a le moins de valeurs restantes. C’est le principe échouer d’abord : on se dirige vers la variable la plus susceptible d’échouer, si bien que les impasses apparaissent près du sommet de l’arbre. Le degré départage les égalités en préférant la variable engagée dans le plus de contraintes - l’Australie-Méridionale, au début du problème de carte, où chaque domaine a encore trois valeurs. La valeur la moins contraignante retient la valeur qui écarte le moins de choix pour les voisines, ce qui relève d’échouer en dernier.

L’asymétrie est délibérée. Toute variable devra finir par être affectée : exposer tôt celle qui est condamnée élague à bon compte ; mais il suffit qu’une seule valeur convienne, essayez donc la plus permissive en premier. Si vous énumériez toutes les solutions, l’ordre des valeurs cesserait d’avoir de l’importance.

Passons à la mesure. Prenez les $N$-reines comme PSC, une variable par colonne valuée par la ligne, et comptez les affectations effectuées (une valeur en conflit avec une reine déjà placée est rejetée sans être comptée ; en les comptant aussi, le retour arrière simple en essaie 876 à 8 reines) :

$$\begin{array}{r|rrrr} n & \text{plain} & \text{MRV} & \text{FC} & \text{MRV + FC} \\ \hline 8 & 113 & 113 & 88 & 75 \\ 16 & 10{,}052 & 10{,}052 & 7{,}560 & 44 \\ 24 & 411{,}608 & 411{,}608 & 286{,}963 & 43 \end{array}$$

Regardez la deuxième colonne. Les valeurs restantes minimales, à elles seules, ne changent rien - pas approximativement, exactement rien, à toutes les tailles. Une fois vue, la raison est évidente : MRV classe les variables par taille de domaine restante, et le retour arrière simple ne supprime jamais rien. Il confronte une candidate à l’affectation courante et passe à la suite. Toute variable non affectée est à égalité, à la taille pleine du domaine, et MRV n’a donc aucune information sur laquelle agir : départageant les égalités par ordre de colonne, elle choisit exactement ce que choisit le retour arrière simple.

La vérification en avant seule en épargne environ un quart : 22 % à 8 reines, 30 % à 24. Ensemble, elles font tomber 411 608 affectations à 43.

Un tableau pareil mérite d'être vérifié plutôt que cru : la figure ci-dessous exécute donc la recherche au lieu de la citer. Passez à MRV et le compte ne bouge pas ; changez de taille de plateau et il ne bouge toujours pas. Passez ensuite à la paire, allez jusqu'à 16, et regardez 10 052 affectations devenir 44. Le curseur s'arrête là parce que la dernière ligne, 24 reines, demande 411 608 affectations, ce qui est du calcul et non un simple redessin.

Où cela vous laisse

Décrire correctement un problème n’est pas de la paperasse : c’est ce qui permet à un solveur de raisonner au lieu de deviner. La commutativité retire un facteur $n!$ avant que quoi que ce soit ne s’exécute. La propagation supprime ce qui ne peut pas marcher et tue parfois une branche d’emblée, tout en restant honnête sur le fait que la franchir ne prouve rien. Et les célèbres heuristiques d’ordonnancement ne sont pas des astuces autonomes : MRV est une consommatrice d’inférence, qui ne vaut exactement rien tant que rien d’autre ne réduit les domaines pour lui donner à lire. Le parcours Satisfaction de contraintes travaille chacun de ces points à la main et en code.