Sudoku et programmation par contraintes

Le Nouvel Observateur, 2 mars 2006

Vous êtes un adepte du sudoku […]? Alors, sans le savoir, plus fort que monsieur Jourdain avec sa prose, vous êtes aussi un spécialiste de la «programmation par contraintes» (PPC) [1]. Cette jeune discipline informatique est peu à peu devenue indispensable à la gestion de l'univers complexe dans lequel nous baignons. Construire l'emploi du temps de toutes les classes d'un lycée? Optimiser les itinéraires d'une flotte d'avions de ligne ou de véhicules de livraison? Planifier la production d'une usine? Partager le spectre des fréquences hertziennes entre tous les utilisateurs qui en ont besoin? Ce sont quelques-unes des innombrables applications de la PPC, et on voit bien que la conciliation d'un nombre important de paramètres contradictoires ressemble fort à l'amusant exercice du sudoku. Lequel consiste, comme on sait, à caser des chiffres de 1 à 9 dans un ensemble de 9 carrés, en veillant bien à ce que jamais le même chiffre n'apparaisse deux fois ni dans la même ligne, ni dans la même colonne, ni dans le même carré. […]
Maître assistant à l'École des Mines de Nantes (EMN), informaticien spécialiste des «structures cachées», président de l'Association française pour la Programmation par Contraintes, Narendra Jussien a «comme tout le monde découvert le sudoku en lisant les journaux». Il […] été frappé d'y retrouver à l'identique les opérations mentales impliquées dans ses sujets de recherche habituels. […] ce jeu offre à l'informaticien des perspectives vertigineuses: «Sans compter toutes celles déduites par des symétries ou des transpositions de chiffres, il y a pas moins de 5 472 730 538 combinaisons essentiellement différentes […]! Ce qui rend assez dérisoire l'habitude qu'ont certains fabricants de grilles (d'ailleurs toutes générées par des programmes automatiques) de revendiquer un copyright. [N.J.]» Le cas échéant, ils auraient beaucoup de mal à démontrer qu'on les a piratés... Mais le plus intéressant, c'est que face à une grille «la démarche naturelle de résolution est la même que celle utilisée en informatique». Spontanément, tels des spécialistes chevronnés de la PPC, les monsieur Jourdain du sudoku se livrent aux trois étapes de la programmation par contraintes: 1) «réduction de domaine», par élimination des valeurs qui ne conviennent pas; 2) «raisonnement local évolué», en considérant chaque région de la grille; 3) «propagation des contraintes», en faisant communiquer entre elles les différentes régions. […] les chercheurs nantais se proposent de prendre en compte la complexité des opérations mentales requises, ceci d'une façon mesurable, pour créer un instrument objectif de mesure de la difficulté de résolution. Laquelle ne dépend d'ailleurs pas - du moins pas essentiellement - du nombre de chiffres donnés au départ, et c'est là un autre sujet de recherche très intéressant: jusqu'ici, on considère qu'il faut un minimum de 17 cases remplies (sur 81) pour pouvoir compléter une grille de sudoku, mais il ne s'agit que d'une constatation empirique, et la question reste ouverte. «Toutes proportions gardées, c'est comme le théorème de Fermat [2]: un énoncé simple et une démonstration très complexe. Or ce serait fantastique d'apporter la preuve mathématique que le nombre minimal de cases préremplies est par exemple de 17, ou de 16, ou moins encore.» Quant à savoir si une pareille démonstration apporterait quelque chose de concret à la PPC, Narendra Jussien répond: «Je pense que oui. Mais je ne peux pas vous dire quoi, car cela supposerait que le problème soit résolu.» ■ Fabien Gruhier

1. UniLyon

2. Wikipédia | UniBordeaux