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

Résumé : 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.
Type de document :
Communication dans un congrès
Deuxièmes Journées Francophones de Programmation par Contraintes (JFPC06), 2006, Nîmes - Ecole des Mines d'Alès / France, France. 2006
Liste complète des métadonnées

Littérature citée [3 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00085809
Contributeur : Laurent Henocque <>
Soumis le : vendredi 14 juillet 2006 - 15:30:08
Dernière modification le : vendredi 22 juin 2018 - 09:31:37
Document(s) archivé(s) le : mardi 6 avril 2010 - 00:09:57

Fichier

Identifiants

  • HAL Id : inria-00085809, version 1

Collections

Citation

François Laburthe, Guillaume Rochart, Narendra Jussien. Évaluer la difficulté d'une grille de sudoku à l'aide d'un modèle contraintes. Deuxièmes Journées Francophones de Programmation par Contraintes (JFPC06), 2006, Nîmes - Ecole des Mines d'Alès / France, France. 2006. 〈inria-00085809〉

Partager

Métriques

Consultations de la notice

417

Téléchargements de fichiers

179