Satisfaction de contraintes : backtracking, propagation de contraintes et AC-3 sur un sudoku et une carte des régions tchèques

Variables, domaines et contraintes, le graphe de contraintes, le backtracking, les heuristiques MRV et LCV, le forward checking, AC-3 et min-conflicts — sur la coloration des régions tchèques, un sudoku et huit dames.

15 minutes Matěj Žalmánek 2026-10-15

Série Bases de l’IA Partie 23 sur 52

1. Carte de l’intelligence artificielle : qu’est-ce qui est quoi et comment tout s’emboîte
2. Brève histoire de l’intelligence artificielle : de Turing aux modèles de langage
3. Données, modèle, entraînement, inférence : les notions de base sur un seul exemple
4. Lire la notation mathématique : symboles, indices, sommes et quantificateurs
5. Ensembles et relations : les briques dont sont faites les définitions en IA
6. Fonctions et applications : pourquoi tout modèle d’IA est une fonction
7. Logique et démonstrations : les règles selon lesquelles on raisonne en IA
8. Graphes et arbres : la structure sur laquelle reposent la recherche et les réseaux de neurones
9. Algèbre linéaire pour l’apprentissage automatique : vecteurs, matrices et pourquoi l’IA multiplie surtout
10. Dérivées, gradient et règle de dérivation en chaîne : comment un modèle sait dans quelle direction apprendre
11. Descente de gradient : comment un modèle apprend
12. Qu’est-ce que la probabilité : du lancer de dé aux axiomes de Kolmogorov
13. Probabilité conditionnelle et théorème de Bayes : comment réviser une estimation quand on apprend du nouveau
14. Variable aléatoire et fonction de répartition : une seule fonction qui dit tout de la loi
15. Fonction de densité et fonction de masse : pourquoi une variable continue a une probabilité nulle en chaque point
16. Espérance, variance et covariance : où se situe une loi, quelle est sa largeur et ce qui varie avec quoi
17. Panorama des lois de probabilité : Bernoulli, binomiale, Poisson, uniforme, normale et exponentielle
18. Loi des grands nombres et théorème central limite : pourquoi les moyennes sont si prévisibles
19. Statistique et estimation de paramètres : maximum de vraisemblance, MAP et intervalles de confiance
20. Théorie de l’information : entropie, entropie croisée et divergence KL — d’où viennent les fonctions de perte
21. Recherche dans l’espace d’états : BFS, DFS, UCS et A* en animations
22. Jeux et adversaires : minimax, élagage alpha-bêta et Monte Carlo tree search
23. Satisfaction de contraintes : backtracking, propagation de contraintes et AC-3 sur un sudoku et une carte des régions tchèques
24. Logique et systèmes à base de connaissances : chaînage avant et arrière, résolution et systèmes experts
25. Planification : STRIPS, monde des blocs, heuristiques par relaxation et planification dans les agents IA
26. Recherche locale et recuit simulé : un voyageur de commerce à travers les chefs-lieux de région tchèques
27. Algorithmes génétiques : population, croisement, mutation et sélection sur un sac à dos de randonnée
28. Stratégies d’évolution et programmation génétique : de la règle du cinquième à la loi de Kepler
29. Optimisation par colonies de fourmis : comment une piste de phéromone trouve un chemin court
30. Optimisation par essaim de particules : inertie, expérience propre et expérience de l’essaim
31. Neuroévolution : faire évoluer les poids et la forme des réseaux de neurones, et l’algorithme NEAT
32. Ensembles flous et fonctions d’appartenance : comment écrire « un peu chaud »
33. Logique floue et probabilité : pourquoi « un peu chaud » ne veut pas dire « probablement chaud »
34. Logique floue : t-normes, implications et règles SI–ALORS
35. Commande floue : Mamdani et Sugeno, du ventilateur au pendule inversé sur un chariot
36. Clustering flou : l’algorithme fuzzy c-means et les points entre les clusters
37. Systèmes neuro-flous (ANFIS) : des règles floues qui apprennent à partir des données
38. Chaînes de Markov : matrice de transition, distribution stationnaire et PageRank
39. Modèles de Markov cachés : l’algorithme de Viterbi et le casino malhonnête
40. Réseaux bayésiens : pourquoi l’herbe est mouillée et ce que cela implique pour l’arroseur
41. Le filtre de Kalman : comment estimer, à partir de mesures imprécises, où se trouve une voiture et à quelle vitesse elle roule
42. Types d’apprentissage automatique : supervisé, non supervisé, semi-supervisé et plus
43. Prompts, contexte et RAG : comment donner au modèle les bonnes informations
44. Autoencodeurs variationnels (VAE) : de nouvelles images à partir d’un espace latent continu
45. Réseaux antagonistes génératifs (GAN) : le faussaire contre le détective
46. Modèles de diffusion : comment une image naît du bruit pur
47. Processus de décision markoviens : états, actions, récompenses et équations de Bellman
48. Q-learning et DQN : apprendre la valeur des actions, du tableau au réseau de neurones
49. Policy gradient et PPO : apprendre directement la politique
50. Comment fonctionne un agent IA : un modèle de langage en boucle avec des outils
51. Programmer avec des agents IA : consigne, tests et vérification
52. Évaluation et sécurité des systèmes d’IA : comment mesurer et comment surveiller

Programme complet de la série 52 sur 83 sujets publiés

Un emploi du temps dans lequel aucun enseignant n’a deux classes à la fois. Un sudoku. La disposition des composants sur une carte, les gardes à l’hôpital, l’attribution des avions aux portes d’embarquement. Toutes ces tâches ont en commun qu’on n’y cherche pas un chemin, mais une affectation : donner à chaque variable une valeur de sorte que toutes les règles soient respectées en même temps. Une telle tâche s’appelle un problème de satisfaction de contraintes et, contrairement à la recherche générale, elle a un grand avantage — les règles sont visibles, si bien que l’algorithme peut en raisonner, et pas seulement essayer.

Cette partie fait suite à Recherche dans l’espace d’états et à Graphes et arbres.

1. Qu’est-ce qu’un problème de satisfaction de contraintes

Définition — CSP

Un problème de satisfaction de contraintes (constraint satisfaction problem, CSP) est un triplet (X, D, C), où

• X = {X₁, …, X_n} est l’ensemble des variables,
• D = {D₁, …, D_n}, où D_i est le domaine — l’ensemble des valeurs que X_i peut prendre,
• C est l’ensemble des contraintes. Chaque contrainte est un couple (portée, relation) : la portée est une liste de variables, la relation indique quelles combinaisons de leurs valeurs sont autorisées.

Une contrainte dont la portée comporte deux variables est binaire, par exemple X₁ ≠ X₂.

Définition — affectation et solution

Une affectation donne à certaines variables une valeur de leur domaine. Elle est cohérente si elle ne viole aucune contrainte, et complète si chaque variable a une valeur.

Une solution du CSP est une affectation complète et cohérente.

Pourquoi ne pas traiter cela comme une recherche ordinaire ? Ce serait possible — l’état est une affectation en cours, l’action est « donne une valeur à la variable suivante ». Mais la recherche regarderait l’état comme une boîte noire. Le CSP voit à l’intérieur de la boîte : il sait quelles règles s’appliquent et quelles variables elles concernent. C’est sur cela que reposent toutes les astuces de cette partie.

2. Le graphe de contraintes : colorier une carte de régions

Un problème classique : colorier une carte de sorte qu’aucun couple d’États voisins n’ait la même couleur. Prenons les quatorze régions de la Tchéquie. Les variables sont les régions, le domaine est un jeu de couleurs et, pour chaque frontière commune, il y a la contrainte « couleurs différentes ».

Définition — graphe de contraintes

Le graphe de contraintes d’un CSP binaire a pour sommets les variables et une arête entre X_i et X_j si et seulement si une contrainte les relie.

Avec quatre couleurs, tout se passe sans accroc. Avec trois, c’est impossible — et le graphe montre pourquoi. La région de Bohême centrale est voisine de Prague et de sept régions qui forment autour d’elle un cercle fermé. Un cercle comportant un nombre impair de sommets a besoin à lui seul de trois couleurs (deux devraient alterner régulièrement, ce qui ne tombe pas juste avec un nombre impair). La Bohême centrale est voisine des sept, si bien qu’il doit lui rester une quatrième couleur :

Que quatre couleurs suffisent pour n’importe quelle carte, c’est le célèbre théorème des quatre couleurs. Appel et Haken l’ont démontré en 1976 — premier grand théorème mathématique démontré à l’aide d’un ordinateur, qui a vérifié près de deux mille cas.

3. Backtracking

Définition — backtracking

Le backtracking est une recherche en profondeur qui, à chaque étape, affecte une valeur à une seule variable de plus. Il n’essaie même pas une valeur qui viole une contrainte avec les variables déjà affectées. Quand il ne reste aucune valeur pour une variable, il revient à la variable précédente et essaie sa valeur suivante.

Dans le pire des cas, il parcourt O(dⁿ) affectations, où d est la taille du domaine et n le nombre de variables. Le CSP général est NP-difficile, si bien que dans le pire des cas, on ne sait pas faire mieux.

def backtracking(assignment, csp):
    if len(assignment) == len(csp.variables):
        return assignment                     # tout a une valeur : solution
    p = select_variable(assignment, csp)
    for h in csp.domains[p]:
        if consistent(p, h, assignment, csp):
            assignment[p] = h
            result = backtracking(assignment, csp)
            if result:
                return result
            del assignment[p]                 # impasse : reviens en arrière
    return None

Sur les régions avec quatre couleurs, le backtracking fait 14 affectations, une par région, et ne revient pas une seule fois en arrière. Avec trois couleurs, il doit prouver qu’aucune solution n’existe — et cela signifie tout essayer : 93 affectations avant d’abandonner.

4. Quelle variable et quelle valeur

Le squelette du backtracking laisse deux questions ouvertes : quelle variable prendre ensuite et dans quel ordre essayer ses valeurs. Les réponses comptent plus qu’on ne le croirait.

Définition — MRV, degré, LCV

MRV (minimum remaining values) : choisis la variable qui a le moins de valeurs pas encore en conflit avec l’affectation.

Heuristique du degré : en cas d’égalité, choisis la variable qui a le plus de contraintes avec des variables pas encore affectées.

LCV (least constraining value) : essaie les valeurs de la variable en commençant par celle qui supprime le moins de possibilités aux voisins.

Pour trois couleurs sur les régions, MRV combiné au forward checking du chapitre suivant réduit le nombre d’affectations de 93 à 45 — il commence par la région à laquelle il reste le moins de couleurs et trouve la contradiction deux fois plus vite.

5. Forward checking

Définition — forward checking

Après l’affectation X_i = v, parcours chaque variable non affectée X_j reliée à X_i par une contrainte et retire de D_j les valeurs incompatibles avec v. Si un domaine se retrouve vide, annule immédiatement l’affectation.

La différence se voit sur le sudoku plus bas. Le simple backtracking case par case, ligne après ligne, a besoin de plus de 14 millions d’affectations. Avec le forward checking, il en faut 11 400. Et si l’on y ajoute MRV, on tombe à 81 — 30 chiffres donnés et 51 complétés, sans un seul retour en arrière.

6. Arc-consistance et AC-3

Le forward checking ne regarde qu’un pas plus loin : les voisins de la variable que nous venons d’affecter. On peut faire plus minutieux — supprimer des valeurs aussi entre des variables qui n’ont pas encore de valeur.

Définition — arc-consistance

La variable X_i est arc-consistante par rapport à X_j si, pour chaque valeur x ∈ D_i, il existe y ∈ D_j tel que le couple (x, y) satisfait la contrainte entre elles. Un CSP est arc-consistant si c’est le cas pour chaque arête orientée (X_i, X_j) du graphe de contraintes.

Algorithme — AC-3

1. Place dans la file toutes les arêtes orientées (X_i, X_j).
2. Retire une arête de la file et supprime de D_i chaque valeur qui n’a pas de partenaire dans D_j.
3. Si D_i a rétréci, remets dans la file toutes les arêtes (X_k, X_i) pour les voisins X_k ≠ X_j — leurs valeurs viennent peut-être de perdre leur partenaire. Si D_i est vide, le CSP n’a pas de solution.
4. Répète jusqu’à ce que la file soit vide.

Pour c contraintes binaires et des domaines de taille au plus d, AC-3 prend O(c · d³).

from collections import deque

def ac3(csp):
    queue = deque((xi, xj) for xi in csp.variables for xj in csp.neighbors[xi])
    while queue:
        xi, xj = queue.popleft()
        if revise(csp, xi, xj):
            if not csp.domains[xi]:
                return False                  # domaine vide : pas de solution
            for xk in csp.neighbors[xi]:
                if xk != xj:
                    queue.append((xk, xi))
    return True

def revise(csp, xi, xj):
    before = len(csp.domains[xi])
    csp.domains[xi] = [x for x in csp.domains[xi]
                       if any(csp.allowed(xi, x, xj, y) for y in csp.domains[xj])]
    return len(csp.domains[xi]) < before

7. Sudoku : la propagation en pratique

Le sudoku est un CSP de manuel : 81 variables, des domaines {1, …, 9} et la contrainte « valeurs différentes » pour chaque couple de cases de la même ligne, de la même colonne ou du même carré 3 × 3. Chaque case a ainsi 20 voisines dans le graphe de contraintes.

Lançons AC-3 seul sur une grille de départ à 30 chiffres, sans une seule affectation à l’aveugle. Il raye 408 valeurs — et à chacune des 51 cases vides il en reste exactement une. Le sudoku est résolu par le seul raisonnement :

Avec les sudokus faciles, c’est ainsi que ça se passe ; avec les plus difficiles, la propagation se bloque quelque part et la recherche prend le relais — un backtracking qui relance la propagation après chaque affectation. Cette combinaison (maintien de l’arc-consistance, MAC) est la base de la plupart des vrais solveurs. Pour comparaison, sur la même grille :

De quatorze millions à zéro. La force brute et le raisonnement astucieux résolvent le même problème — seul l’un des deux lit les règles.

8. Recherche locale : min-conflicts

Une stratégie complètement différente : ne pas construire la solution morceau par morceau, mais partir d’une affectation complète qui viole tout un tas de contraintes, et la corriger progressivement. C’est la recherche locale de la partie sur la recherche, sauf que la fonction objectif est le nombre de contraintes violées.

Algorithme — min-conflicts

1. Commence par une affectation complète aléatoire.
2. Tant qu’une contrainte n’est pas satisfaite : choisis au hasard une variable en conflit et donne-lui la valeur avec laquelle elle viole le moins de contraintes (en cas d’égalité, au hasard).

L’épreuve classique est le problème des n dames : placer n dames d’échecs sur un échiquier n × n de sorte qu’aucune ne menace une autre. La variable est la ligne de la dame dans chaque colonne. Pour huit dames, notre exécution a commencé avec six paires de dames qui se menacent et s’est terminée après 8 étapes :

Remarquez les étapes du milieu : pendant quatre étapes, le nombre de conflits reste à un — l’algorithme déplace les dames « de côté » sur un plateau, avant de trouver le coup qui élimine le conflit. Ce qui surprend, c’est à quel point cela passe à l’échelle : un million de dames, min-conflicts le résout en moyenne en une cinquantaine d’étapes environ. C’est avec la même méthode qu’on a planifié les observations du télescope spatial Hubble.

9. Les contraintes en pratique

• Emplois du temps et planification. Les emplois du temps scolaires, les plannings de gardes, l’attribution des salles comme les plans de production se formulent en variables, domaines et contraintes. Des solveurs comme Google OR-Tools combinent propagation, recherche et amélioration locale.
• Les solveurs SAT résolvent des CSP où chaque variable est vrai/faux. Ils vérifient des conceptions de puces, cherchent des bogues dans les logiciels, et les gestionnaires de paquets (par exemple sous Linux) s’en servent pour assembler des versions de bibliothèques qui fonctionnent ensemble.
• Les compilateurs attribuent les variables d’un programme aux registres du processeur par coloration de graphe : deux variables vivantes en même temps ne peuvent pas partager un registre — exactement comme deux régions voisines une couleur.
• Les configurateurs des boutiques en ligne et de la production veillent à ce que les composants choisis aillent ensemble.
• Les agents IA et les modèles de langage n’excellent souvent pas dans les CSP : pour un sudoku ou un emploi du temps, un solveur est plus fiable. Un bon agent ne résout donc pas le problème « de tête » — il le traduit en variables et contraintes et appelle un outil dessus.

10. Résumé

• Un CSP est un triplet (X, D, C) : variables, domaines et contraintes. Une solution est une affectation complète qui ne viole aucune contrainte.
• Le backtracking affecte les variables l’une après l’autre et revient des impasses ; dans le pire des cas, il est exponentiel.
• Les heuristiques MRV et LCV choisissent la variable la plus difficile et la valeur la plus accommodante ; le forward checking détecte une impasse un pas plus tôt.
• AC-3 propage les suppressions dans le graphe de contraintes jusqu’à ce que chaque valeur ait un partenaire ; il résout un sudoku facile entièrement sans recherche.
• Min-conflicts corrige une affectation complète et vient à bout même de problèmes gigantesques, comme un million de dames.

Envie de mettre la main à la pâte ? Demandez à un agent IA d’écrire un solveur de sudoku avec backtracking, puis ajoutez-y le forward checking, MRV et AC-3 — et comptez combien d’affectations disparaissent.

Vous voyez les choses autrement ? Écrivez à support@coden-app.com.