Évaluer la difficulté d'une grille de sudoku à l'aide d'un modèle contraintes

摘要

Le sudoku est un jeu de logique qui est devenu en quelques mois un phénomène de société en France. Il envahit les métros, les trains, les bus, les salles de cours et même le journal Le Monde. Grâce à ce jeu, le grand public est devenu le M. Jourdain de la Programmation Par Contraintes. En effet, l'intérêt de ce jeu pour montrer très rapidement et très simplement les principes premiers de la programmation par contraintes n'est plus à démontrer. De plus, la technologie contraintes est très performante pour modéliser à l'aide de quelques contraintes globales ce problème et le résoudre quasiment simplement par propagation. Par contre, la mesure de la difficulté d'une grille – qui laisse à désirer pour de nombreuses instances publiées actuellement – n'a pas encore été capturée de manière satisfaisante par un modèle contraintes. Une raison est qu'une telle mesure est totalement subjective car elle dépend de la façon dont un joueur aborde son instance. Dans cet article, nous montrons qu'il est possible de définir des modèles contraintes permettant de retrouver des combinaisons de règles utilisées par les joueurs. Ces modèles ouvrent la porte à une évaluation de la difficulté d'une instance par une approche purement contraintes et même de fournir des systèmes d'aide eux-aussi basés sur un telle approche.