Évaluer la difficulté d'une grille de sudoku à l'aide d'un modèle contraintes - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Communication Dans Un Congrès Année : 2006

É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.
Fichier principal
Vignette du fichier
47.pdf (443.32 Ko) Télécharger le fichier
Loading...

Dates et versions

inria-00085809 , version 1 (14-07-2006)

Identifiants

  • HAL Id : inria-00085809 , version 1

Citer

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. ⟨inria-00085809⟩
391 Consultations
789 Téléchargements

Partager

Gmail Facebook X LinkedIn More