Titre. Sudoku

Encadrant(s). C. Bessiere, E. Bourreau

Lieu. LIRMM

Sujet.

Le jeu de Sudoku se définit très simplement. Il consiste en une grille carrée de 9 cases sur 9, soit 81 cases, déjà partiellement remplie de chiffres de 1 à 9. Le but du jeu est de compléter le remplissage uniquement avec des chiffres de 1 à 9 de sorte que tous les chiffres de 1 à 9 apparaîssent sur chaque ligne, chaque colonne et chacun des neuf pavés de 9 cases obtenus en groupant les lignes et les colonnes trois par trois de la première à la troisième, de la quatrième à la sixième et de la septième à la neuvième.

Bien sûr, on peut utiliser un solveur à contraintes pour remplir les cases manquantes, mais l'intérêt est limité. Le problème intéressant est de générer de telles grilles. En effet, une multitude de journaux sont friands de ces grilles car ils en publient une chaque matin. Or, ces grilles ne se génèrent pas simplement en lançant au hasard quelques chiffres. Il faut respecter un certain nombre de points qui rendent le problème non trivial :

• la grille publiée doit comporter au moins une solution pour ne pas laisser le joueur finir sur une note négative;
• elle ne doit pas comporter plus d'une solution car on publie la solution le lendemain;
• la grille doit avoir un niveau de difficulté donné (il existe en effet des grilles très faciles à compléter, d'autres beaucoup plus dures);
• un jeu de grilles doit être suffisamment varié selon certains critères (par exemple, si on publie la même grille que la veille avec simplement une permutation sur les chiffres ou sur lignes, le lecteur risque de se lasser);
• le publieur peut vouloir une grille avec un certain nombre de chiffres déjà placés (minimal ?) ou placés d'une certaine façon (pour obtenir des motifs particuliers).

Les questions qui se posent vont donc bien au-delà du simple remplissage aléatoire. La programmation par contraintes, avec les notions de consistance locale, de contrainte globale, de 'backdoor', de symétries, etc. est un candidat idéal pour ce genre de problème.

Le but du stage est triple :
D'abord, on cherchera des réponses théoriques aux questions que pose le problème du Sudoku.
Ensuite, on appliquera les techniques trouvées dans une implémentation du problème avec le solveur à contraintes public Choco.
Enfin, on analysera la facilité de mise en oeuvre dans Choco des techniques proposées. Les difficultés rencontrées, s'il y en a, seront étudiées, et des adaptations de l'architecture du solveur seront proposées.