Hélène prépare un dîner pour huit personnes. Elle a assez de places, mais son premier dessin ne peut pas satisfaire toutes les demandes qu’elle a notées. Une préférence ressemble à une condition, trois personnes veulent les mêmes deux positions, et une annulation changera bientôt les voisinages. Avant d’annoncer les places, elle va chercher ce qui bloque réellement, puis choisir ce qu’elle peut maintenir et ce qu’elle doit faire préciser.
Le dossier est entièrement construit. Hélène est désignée par H ; les sept autres personnes par A, B, C, D, E, F et G. Les demandes, réponses et décisions sont stipulées, sans dîner observé ni table essayée. Nous supposons huit places utilisables autour d’un même périmètre, numérotées de 1 à 8. Deux places consécutives sont voisines, y compris 8 et 1. Cette convention décrit notre dessin ; elle ne mesure ni la distance réelle, ni la facilité de converser, ni le confort d’une chaise. OR-Tools n’a pas été exécuté.
Huit places ne résolvent pas un manque de choix communs
Dans un premier exercice, H occupe la place 1. A, B et C n’acceptent chacun que les places 2 ou 3. Les quatre autres personnes peuvent choisir parmi les places 4 à 8. Hélène trouve bien une possibilité pour chaque nom pris séparément : A peut être en 2, B en 3, C en 2 ou 3. Mais ces réponses ne constituent pas encore un placement simultané.
Si elle attribue 2 à A et 3 à B, il ne reste aucune place acceptée par C. Si elle commence par C, le problème se reporte sur A ou B. Le blocage tient aux trois personnes limitées à deux positions, pas au nombre total de couverts. Déplacer D de 5 à 8 ne libérerait rien pour elles. Ajouter un couvert en 9 ne répondrait pas davantage à leurs demandes telles qu’elles sont écrites : aucune ne mentionne 9.
Dans une branche explicitement changée, C accepte aussi la place 4. Hélène peut alors retenir H en 1, A en 2, B en 3, C en 4, puis D, E, F et G en 5, 6, 7 et 8. Elle n’annonce pas avoir trouvé un arrangement caché dans le premier état. Elle a obtenu une possibilité supplémentaire et construit un plan sur cette réponse nouvelle. Les deux états restent différents, même si le nombre de convives demeure huit.
Préciser ce que signifie être ensemble
Un deuxième exercice abandonne ces restrictions de positions. H reste en 1, mais A, B et C demandent chacun à être voisin immédiat des deux autres. Cette fois, ils peuvent prendre toutes les places libres. Cela ne rend pas leur demande compatible avec le périmètre à huit positions.
Pour être voisin de B et de C, A doit les avoir de part et d’autre. S’il est en 3, B peut être en 2 et C en 4. A est bien voisin des deux ; B et C ne le sont pas entre eux. En déplaçant ce petit ensemble autour du périmètre, on retrouve le même obstacle. Les trois voisinages demandés ne peuvent pas exister ensemble sur notre dessin à huit places.
Dans la branche retenue, B et C précisent qu’ils souhaitent rester à la même table, sans demander à être voisins immédiats. A conserve sa demande de voisinage avec chacun. Hélène retient alors H en 1, B en 2, A en 3 et C en 4, puis les quatre autres noms. Les demandes désormais formulées sont satisfaites. Elle ne présente pas « même table » et « voisins immédiats » comme deux façons équivalentes d’écrire le souhait initial. C’est cette précision qui a rendu le placement possible.
Ces deux exercices préparent le dîner principal : identifier un sous-ensemble qui bloque et distinguer les relations demandées. Ils ne servent pas à déduire les affinités des personnes. Pour la suite, les données changent encore et sont énoncées entièrement.
Une annulation peut changer les voisins sans déplacer leurs noms
Le plan du dîner principal comporte, dans l’ordre de 1 à 8, H, A, B, C, D, E, F et G. H doit rester en 1. Les voisinages H–A, A–B et B–C sont des conditions retenues. E et G ne doivent pas être voisins immédiats. Aucun autre voisinage n’est imposé. Le dessin satisfait bien ces demandes : F, installé entre E et G, les sépare dans notre convention.
F annule et Hélène choisit de retirer sa place 7. Le nouveau périmètre comporte les positions 1, 2, 3, 4, 5, 6 et 8, désormais consécutives dans cet ordre. Les sept noms restants occupent encore leurs anciennes positions. Pourtant, E en 6 et G en 8 sont maintenant voisins. Leurs numéros diffèrent toujours de deux, mais il n’existe plus de place 7 entre eux. La différence des numéros ne décrit donc plus le voisinage.
Hélène pourrait conserver une position vide entre E et G. Ce serait un autre état matériel, avec huit positions dont une inoccupée. Dans la définition employée ici, leurs positions resteraient non consécutives. Cela ne prouverait pas qu’ils disposent de la même séparation dans une table réelle, ni qu’ils comprennent ainsi leur demande. Hélène retient dans notre cas les sept places rapprochées ; elle doit donc réparer le placement correspondant, plutôt que défendre l’ancien dessin en conservant ses numéros.
Elle échange D et E. Le nouveau tour de table devient H, A, B, C, E, D, G, aux positions 1, 2, 3, 4, 5, 6 et 8. H–A, A–B et B–C demeurent voisins. E en 5 et G en 8 ont désormais D en 6 entre eux. Toutes les conditions du dîner principal sont satisfaites. Deux personnes ont changé de position ; les cinq autres ont gardé la leur.
Cette réparation est minimale selon le nombre de personnes déplacées. Sans changement, E et G restent voisins. Avec sept personnes occupant les sept places, changer la position d’une seule personne laisserait une place vide et une autre occupée deux fois. Il faut donc au moins deux changements. L’échange D–E en utilise exactement deux. Ce résultat porte sur les positions de notre cas, pas sur l’effort réel que demanderait de déplacer des convives ou des chaises.
Une réparation minimale ne conserve pas toutes les préférences
Une information supplémentaire concerne D : il aimerait être voisin de C. Dans le plan initial à huit, D en 5 était bien voisin de C en 4. Après l’échange D–E, E occupe 5 et D occupe 6. Le voisinage souhaité disparaît. Hélène pourrait croire qu’elle le retrouverait en acceptant de déplacer davantage de noms. Il faut examiner cette question avant de promettre une meilleure proposition.
Les trois voisinages H–A, A–B et B–C réunissent ces quatre personnes dans un bloc consécutif. A a H et B pour voisins ; B a A et C. À sept places, il reste donc trois positions consécutives pour D, E et G. Puisque E et G ne peuvent pas être voisins, D doit se trouver au milieu de ces trois positions. C touche une extrémité de ce groupe, pas sa position centrale. D ne peut donc pas être voisin de C tant que les conditions précédentes sont conservées.
Le contrôle complet donne quatre placements possibles pour ce cas à sept. Dans l’ordre des positions 1, 2, 3, 4, 5, 6 et 8, ce sont : H–A–B–C–E–D–G ; H–A–B–C–G–D–E ; H–G–D–E–C–B–A ; H–E–D–G–C–B–A. Aucun ne rapproche D de C comme voisins immédiats. La seconde proposition montre qu’on peut inverser E et G ; les deux dernières orientent le bloc H–A–B–C dans l’autre sens. Le problème subsiste dans les quatre états.
Hélène n’a donc pas seulement trouvé un plan qui perd une préférence. Elle a établi que cette préférence ne peut pas être ajoutée aux conditions actuelles. Elle doit choisir entre modifier une condition, modifier le format ou renoncer à promettre ce voisinage. Dans notre scénario, D avait formulé un souhait, sans en faire une condition de sa participation. Hélène conserve les autres demandes et lui précise que le placement retenu ne le mettra pas près de C. Elle propose qu’ils puissent échanger au café ; aucun échange réel ni accord universel n’est prétendu.
Si D avait donné une condition indispensable, cette conclusion aurait demandé une nouvelle décision avec les personnes concernées. Le calcul n’autoriserait pas Hélène à supprimer silencieusement leur demande de séparation ou un autre voisinage. Il indique ce qui doit changer pour poursuivre ; il ne choisit pas à leur place ce qu’ils peuvent accepter. Dans notre cas effectivement renseigné, le souhait D–C reste visible parmi les éléments non retenus.
Comparer des réparations qui ne changent pas les mêmes demandes
Pour rendre cet arbitrage concret, Hélène prépare deux branches supplémentaires à sept. Dans la première, B et C acceptent de ne plus être voisins immédiats. H–A et A–B restent demandés, E et G restent séparés, et le souhait D–C devient réalisable. Le tour de table H–A–B–E–D–C–G satisfait cet ensemble modifié : C et D sont voisins, tandis que E et G ne le sont pas. Par rapport au dessin initial sans F, C passe de 4 à 6 et E de 6 à 4. Deux personnes bougent encore, mais ce sont C et E, non D et E.
Dans la seconde branche, E et G acceptent leur voisinage dans le périmètre réduit. Hélène peut garder H–A–B–C–D–E–G, aux anciennes positions des sept personnes. Les trois voisinages du bloc sont conservés, D reste voisin de C et personne ne change de position. Cette proposition est incompatible avec la demande de séparation initiale ; elle ne devient recevable que parce que E et G ont changé leur réponse dans cette branche construite. Le nombre nul de déplacements ne suffit pas à la rendre acceptable avant cet accord.
Hélène peut désormais nommer trois choix différents. Maintenir toutes les conditions initiales déplace D et E et laisse le souhait D–C insatisfait. Modifier B–C déplace C et E tout en réalisant D–C. Modifier E–G permet de conserver les sept positions et D–C, mais abandonne leur séparation. Les deux derniers choix ne sont pas des solutions supplémentaires du même problème : ils modifient ce qui est demandé. Dans l’état finalement retenu, aucune de ces nouvelles réponses n’a été choisie ; Hélène garde la réparation D–E. Les autres branches montrent exactement à qui et sur quoi porterait une nouvelle discussion.
Les positions déjà annoncées peuvent aussi limiter une réparation. Supposons que G souhaite conserver 8. Parmi les quatre placements admissibles à sept, seul H–A–B–C–E–D–G le permet. L’échange D–E devient alors l’unique proposition restante, et pas seulement la réparation qui bouge le moins de personnes. Si E demande au contraire de garder 6, aucun des quatre placements ne convient. Déplacer davantage de noms ne sauverait pas cette position : les quatre possibilités ont déjà été examinées. Une promesse de place peut ainsi supprimer une option ou supprimer toutes les options ; les deux réponses demandent une annonce différente.
Ces branches précisent la décision sans classer les convives. Le dessin ne dit pas que le souhait de D vaut plus que la demande de B ou celle d’E. Il montre quelles modifications produisent quels résultats. Hélène peut retenir la réparation initiale et expliquer sa limite, ou reprendre une demande particulière avec son auteur. Elle ne peut pas appeler « même plan » trois attributions qui changent des personnes et des engagements différents.
Choisir un plan commun avant une confirmation tardive
Revenons à un moment antérieur à l’annulation. La venue de F est encore incertaine. Hélène veut annoncer un placement qui ne changera pas pour les sept autres personnes, que F vienne ou non. Les conditions sont celles du dîner principal ; le voisinage D–C demeure seulement souhaité.
Le plan initial H–A–B–C–D–E–F–G convient si F est présent. Il ne convient plus si F et sa place sont retirés : E et G deviennent voisins. Hélène dispose néanmoins d’une proposition commune. À huit, elle peut annoncer H–A–B–C–E–D–F–G. Si F annule et que 7 disparaît, les autres noms forment H–A–B–C–E–D–G. Les trois voisinages du bloc initial restent conservés et E et G restent séparés dans les deux cas.
Cette proposition évite une modification tardive des positions des sept personnes dont la présence est confirmée. Son coût est précis dans notre exercice : D et E changent de position dès maintenant par rapport au premier dessin, et D n’est voisin de C dans aucun des deux états. Hélène ne peut pas promettre simultanément le plan commun décrit et ce voisinage préféré. Elle choisit le plan commun parce qu’elle souhaite annoncer une seule attribution aux personnes confirmées.
Elle aurait pu retenir deux plans conditionnels : le dessin initial si F confirme avant l’annonce, puis la réparation à sept si F annule. Dans le premier état, D resterait voisin de C ; dans le second, il ne le serait plus. Cette autre décision préserverait une préférence tant que huit personnes viennent, en acceptant que D et E puissent changer de position. Ce n’est pas un plan commun dont on aurait simplement retiré un nom.
Pour transmettre le choix réellement retenu, Hélène garde les positions de D et E telles qu’elles sont dans la proposition commune. Elle indique que F occupera 7 s’il vient et que cette position disparaîtra sinon. Elle ne laisse pas circuler le premier dessin à huit comme une variante interchangeable : les personnes qui le liraient attribueraient encore 5 à D et 6 à E. La différence tient à deux noms identifiés et à une préférence non retenue, pas à une nouvelle hiérarchie des invités.
Dire ce que le contrôle a établi
La recherche sous contraintes distingue une proposition admissible d’un optimum selon un critère. Ici, un placement qui respecte toutes les demandes retenues ne devient pas automatiquement le meilleur dîner. Notre critère de réparation comptait les personnes déplacées ; celui du plan commun conservait leurs positions dans deux états. Ni l’un ni l’autre ne mesure une conversation réussie. OR-Tools, cadre de la recherche sous contraintes.
Les exemples ont été contrôlés par énumération des permutations complètes des positions distinctes, selon la fonction décrite dans la documentation Python. Les demandes du cas filtrent ensuite les placements. Cette vérification fournit 24 propositions admissibles pour le dîner principal à huit, puis quatre à sept ; elle identifie aussi l’unique réparation à deux changements du dessin initial. Les noms et les positions restent distincts : aucune chaise n’accueille deux personnes dans ces contrôles. Python, permutations.
Un dessin raté ne prouve toutefois pas une impossibilité. La documentation CP-SAT distingue notamment un état démontré impossible d’un état encore inconnu. Pour nos cas, les preuves locales et le contrôle exhaustif donnent une conclusion ; essayer seulement deux permutations ne donnerait pas la même portée. Hélène peut annoncer une proposition vérifiée, une condition incompatible ou une question encore ouverte. Elle ne transforme pas l’absence de réponse après quelques essais en refus définitif d’une demande. CP-SAT, états de réponse.
Le plan retenu conserve ainsi une décision expliquée : quelles demandes ont été maintenues, laquelle n’a pas été satisfaite et quel état de présence il couvre. Il prépare les places sans prétendre préparer les relations à la place des convives. Pour Hélène, la difficulté n’était plus de trouver une jolie répartition des noms, mais de savoir ce qu’elle pouvait réellement annoncer.