Un solveur de contraintes est un programme qui cherche, parmi un nombre gigantesque de plannings possibles, ceux qui respectent toutes vos règles obligatoires, puis qui retient le meilleur selon vos préférences. Il ne devine pas et n'improvise pas : il teste, élimine, compare et explique. C'est le même principe qu'un joueur de sudoku, à une échelle qu'aucun humain ne peut parcourir.
Le principe : trois ingrédients
Tout problème de planning se décrit avec trois éléments, que vous manipulez déjà sans le savoir.
- Ce qu'il faut placer : les séances, les cours, les gardes, les rendez-vous. Le solveur les appelle des variables.
- Où on peut les placer : l'ensemble des créneaux, des salles et des personnes possibles pour chaque séance. C'est son domaine de choix.
- Les règles : ce qui est interdit ou souhaité. Ce sont les contraintes.
Exemple dans une école de musique : le cours de piano de Léa doit durer 45 minutes (ce qu'il faut placer), avec Karim ou Sophie, dans la salle 1 ou 2, du lundi au samedi (les choix possibles), sans jamais chevaucher un autre cours dans la même salle, et sans que Karim enchaîne plus de trois cours de suite (les règles).
Pourquoi un humain n'y arrive plus passé une certaine taille
Prenons un cas modeste : 15 séances à placer, 30 créneaux dans la semaine, 4 salles. Chaque séance a donc 30 × 4 = 120 emplacements possibles. Le nombre total de plannings imaginables est 120 puissance 15, soit environ 1,5 suivi de 31 zéros. Même en n'essayant qu'un milliard de combinaisons par seconde, il faudrait bien plus longtemps que l'âge de l'univers pour les passer toutes en revue.
Un humain s'en sort par intuition : il place d'abord les cours les plus contraints, puis comble. C'est exactement ce que fait un bon solveur, mais il le recommence des centaines de milliers de fois.
Contraintes obligatoires et contraintes souples
La distinction la plus utile à retenir :
| Type | Exemple | Si elle est violée |
|---|---|---|
| Obligatoire (dure) | Karim ne travaille jamais le mercredi | Le planning est rejeté |
| Obligatoire (dure) | Une salle ne peut pas accueillir deux cours à la fois | Le planning est rejeté |
| Souhait (souple) | Sophie préfère enseigner le matin | Le planning perd des points |
| Souhait (souple) | Limiter les trous entre deux cours | Le planning perd des points |
Les contraintes obligatoires définissent ce qui est possible. Les souhaits servent à choisir le meilleur parmi les possibles. C'est ce qui permet d'attribuer un score : plus le planning respecte les souhaits, plus il monte. Dans la démonstration d'Accord, le planning publié atteint 94 sur 100, le brouillon 85, et la différence s'explique ligne par ligne.
Comment il cherche : construire, puis améliorer
Il n'y a pas une méthode unique. Les solveurs combinent généralement deux étapes.
Étape 1 : construire un premier planning
On place les séances les plus difficiles d'abord (celles qui ont le moins de créneaux possibles), puis les plus faciles. C'est la méthode dite gloutonne : rapide, mais pas forcément optimale, car un choix précoce peut bloquer un choix tardif.
Étape 2 : améliorer par petits changements
Le solveur déplace une séance, échange deux intervenants, essaie un autre créneau, et compare le score avant et après. S'il progresse, il garde. S'il régresse légèrement, il l'accepte parfois, volontairement, pour sortir d'une impasse : c'est le principe du recuit simulé, inspiré du refroidissement lent d'un métal. Sur la démonstration d'Accord, le moteur examine de l'ordre de 300 000 à 500 000 variantes en deux secondes et demie environ.
À retenir : un solveur ne garantit pas toujours « le » meilleur planning mathématique, mais un planning très bon, valide, trouvé en secondes. Pour une association ou une école de musique, la différence avec l'optimum théorique est invisible, alors que la différence avec un placement manuel se voit tout de suite.
Quand il n'y a pas de solution
Un cas courant : vos règles se contredisent. Karim ne peut que le lundi, le cours de percussions exige Karim et la salle 3, qui est fermée le lundi. Aucun planning ne satisfait tout. Un bon solveur ne renvoie pas une page blanche : il indique quelles séances n'ont pas pu être placées, quelle règle les bloque, et ce qu'il faudrait assouplir. Ce diagnostic est parfois plus précieux que le planning lui-même, car il révèle des règles que personne n'avait vues entrer en conflit. Notre guide sur la rédaction de règles de planning montre comment les formuler pour que cela soit lisible.
Ce que le solveur ne fait pas
- Il ne connaît que ce que vous lui dites. Une règle jamais écrite (« Sophie déteste enchaîner deux élèves débutants ») n'existe pas pour lui.
- Il ne tranche pas les arbitrages humains. Entre l'équité de charge et la préférence de chacun, c'est vous qui réglez les curseurs.
- Il n'est pas une intelligence artificielle au sens des modèles de langage. Il applique des règles de façon exacte et vérifiable. C'est justement sa force. La frontière est expliquée dans notre guide sur l'IA et le planning.
Pourquoi c'est utile même sans expertise
Un solveur apporte trois bénéfices concrets à une équipe qui n'a rien d'informaticien : le gain de temps (la semaine entière en quelques secondes plutôt qu'une soirée), la vérification (aucun conflit de salle ou de personne ne passe entre les mailles) et l'explication (chaque placement se justifie, ce qui désamorce bien des discussions). Dans Accord, le panneau « Pourquoi ici » indique la raison de chaque séance, et propose des remplaçants quand quelqu'un est absent. Vous pouvez le constater sur la démo.
Questions fréquentes
Un solveur de contraintes, c'est de l'intelligence artificielle ?
C'est une branche de l'informatique plus ancienne que les modèles de langage actuels, rattachée à la recherche opérationnelle et à l'IA dite symbolique. Il suit des règles exactes, donne le même type de résultat à chaque calcul et peut justifier ses choix, ce qui n'est pas le cas d'un modèle de langage.
Quelle différence entre un solveur et un tableur avec des formules ?
Un tableur calcule ce que vous lui avez demandé, cellule par cellule, mais il ne cherche pas. Un solveur explore des milliers de combinaisons pour en trouver une qui respecte vos règles. Le tableur vérifie, le solveur construit.
Le planning produit sera-t-il toujours le même ?
Pas forcément. Quand plusieurs plannings sont aussi bons, le solveur peut en proposer un parmi eux. C'est pourquoi on peut verrouiller certaines séances : en recalculant, elles ne bougent plus.
À partir de quelle taille un solveur devient-il utile ?
Dès que le nombre de combinaisons dépasse ce qu'on tient dans sa tête, c'est-à-dire en pratique à partir d'une dizaine de personnes et de quelques salles, surtout si les disponibilités et les règles se croisent. En dessous, un tableur bien tenu suffit souvent.