De la recherche

La combinatoire des Sudokus

En quoi le jeu du Sudoku est-il lié aux recherches en informatique ?
C'est par sa nature combinatoire : il y a un grand nombre de combinaisons possibles, et que ce soit dans le but de résoudre ou de générer une grille, il s'agit de trouver celle qui correspond à certains critères.

Cependant, les problèmes combinatoires ne sont pas toujours ludiques. Définir un emploi du temps pour les équipes d'infirmières d'un hôpital, organiser les tournées d'une équipe de livreurs, planifier un chantier... quel est le point commun entre tous ces problèmes a priori différents ? C'est leur nature combinatoire ! Là aussi, y a un grand nombre de combinaisons possibles, et il s'agit de trouver la meilleure d'entre elles selon un certain critère : temps, coût...

Problèmes combinatoires et techniques de résolution

Ces problèmes sont des problèmes discrets, car ils portent sur des variables entières. Contrairement à ce que pourrait laisser penser l'intuition, ces problèmes sont souvent plus difficiles à résoudre que les problèmes continus, portant sur des variables réelles. En effet, alors que la dérivation des fonctions est un outil puissant permettant d'aborder les problèmes d'optimisation continus, on manque cruellement d'outils mathématiques pour la résolution des problèmes discrets.

Il existe toutefois certaines techniques informatiques, programmation linéaire, programmation dynamique et programmation par contraintes (en abrégé PPC), qui permettent de résoudre ces problèmes sur ordinateur.

C'est pourquoi des liens étroits peuvent être montrés entre la programmation par contraintes et le problème combinatoire à la mode qu'est le Sudoku.

Sudokus et autres jeux

Depuis l'année 2005, de petites grilles de 9x9 cases envahissent le web et les journaux. Il s'agit du Sudoku. Ce jeu, inventé aux États-Unis en 1979, à partir du principe du carré latin, a été popularisé au Japon depuis 1986 et a alors pris un nom japonais.

Une des raisons de son succès est sa simplicité. Il peut en effet être décrit par une seule règle : chaque ligne, colonne et carré de 3x3 doit contenir tous les chiffres de 1 à 9.

Voici un exemple jouable, de niveau facile.

Cliquez dans une case de la grille et entrez le chiffre choisi. Les erreurs
s'affichent en rouge tandis que les valeurs en vert sont correctes.
Cliquez ici pour afficher la solution et pour recommencer à zéro.

 

Alors que le Sudoku original est une grille 9x9, il existe désormais de nombreuses variantes : Sudoku 4x4 pour les enfants, Monster Sudoku (16x16) pour les accros, Killer Sudoku où les grilles sont pavées par des zones associées à des sommes...

Un autre jeu a déjà détrôné le Sudoku au Japon, il s'agit du Kakuro, sorte de mots croisés numériques faisant aussi intervenir des sommes. Ce jeu peut également être résolu et généré avec des techniques de programmation par contraintes.

Techniques de résolution des Sudokus

Si le Sudoku passionne le grand public, c'est parce que chacun peut s'inventer ses propres techniques de résolution. Or ces techniques rejoignent celles mises en œuvre par les informaticiens dans le cadre de la programmation par contraintes.

On peut grossièrement classer ces techniques en deux catégories :

Pour les Sudokus difficiles, les joueurs sont souvent amenés à raffiner la deuxième technique, en considérant les ensembles de valeurs qui sont candidates pour une case donnée. Ces raisonnements sur des ensembles de valeurs sont identiques à ceux qui sont faits automatiquement par les résolveurs de contraintes et sont appelés filtrage ou bien maintien de la consistance par les spécialistes de la programmation par contraintes.

Enfin, pour les Sudokus de niveau expert, on est parfois amené à faire des hypothèses. Cette dernière technique est aussi classique dans la programmation par contraintes, du fait de la nature exponentielle des problèmes abordés.

La résolution de Sudokus est un cas d'école pour la programmation par contraintes. Un article du même auteur publié sur java.net (en anglais) explique en détail comment modéliser le problème des Sudokus en programmation par contraintes. Une traduction de cet article en français a été publiée par la revue La Recherche dans la rubrique Wxyz, n° 395 de mars 2006 (version en ligne). La bibliothèque de PPC utilisée dans cet article est Koalog Constraint Solver, écrite en Java, mais la modélisation n'est pas dépendante du choix du logiciel.

La résolution d'un Sudoku se fait en quelques millisecondes sur un PC de bureau.

Mise à part la résolution, d'autres problèmes sont à considérer : génération et calcul des niveaux, dont nous verrons qu'ils sont étroitement liés aux techniques de résolution.

Génération des Sudokus

Si la génération manuelle de Sudokus a encore ses adeptes (principalement au Japon), la plupart des grilles sont désormais générées par ordinateur.

Rappelons que l'objectif à atteindre est de générer une grille partiellement remplie conduisant à une unique solution. On dit que le Sudoku est bien formé. Une propriété supplémentaire est la minimalité des indications. Plus précisement, chaque indication doit être indispensable : si on la supprimait, alors le Sudoku n'aurait plus une solution unique. On dit que le Sudoku est localement minimal.

Un schéma d'algorithme pour générer un Sudoku bien formé et localement minimal est le suivant :

1 - on génère une grille aléatoirement
2 - on initialise une liste de cases à effacer avec toutes les cases du Sudoku
3 - on choisit au hasard une case dans cette liste (et on l'enlève de la liste)
4 - on efface, dans la grille, la valeur dans cette case
5 - si le Sudoku n'a pas une solution unique, alors on remet la valeur effacée
6 - si la liste est non vide, on va en 3, sinon on a terminé

 

Cet algorithme suppose que l'on sait résoudre n'importe quel Sudoku... ce qui est vrai grâce à la programmation par contraintes. À l'étape 1, pour générer une grille de façon aléatoire, il suffit d'appliquer une technique de résolution sur une grille vide, sans aucune donnée initiale. De même, à l'étape 5, il suffit de chercher deux solutions au Sudoku pour montrer que la solution n'est pas unique.

Par ailleurs, l'étape 3 enlève une case de la liste, de ce fait la longueur de la liste décroît strictement à chaque itération, et la liste va donc finir par être vide : ceci garantit que l'algorithme termine.

Calcul des niveaux

Le calcul des niveaux se révèle la partie la plus délicate. La difficulté doit en effet correspondre à celle qui est attendue par les joueurs pour le niveau annoncé, c'est un facteur primordial pour la satisfaction des joueurs. Ce point fait l'essentiel de la différence entre les producteurs de Sudokus concurrents.

Une technique (celle utilisée par la société Koalog pour noter ses Sudokus en six niveaux) consiste à définir un ensemble de règles de résolution de difficulté croissante, et à noter les Sudokus en fonction de la difficulté des règles nécessaires pour la résolution.

Par exemple, on peut considérer que la règle placement d'une valeur dans un carré est plus simple que la règle détermination de la valeur dans une case donnée. Les Sudokus qui peuvent être résolus uniquement à l'aide de la première de ces deux règles seront donc considérés comme plus simples que ceux qui nécessitent d'utiliser les deux règles.

Ainsi donc, les liens qui existent entre le Sudoku et les techniques de programmation par contraintes sont mis en évidence. En résolvant chaque jour le problème proposé par votre quotidien favori, vous ne ferez plus de la programmation sans le savoir.
Mais ce document ne cherche pas à présenter le Sudoku d'une manière exhaustive. D'autres éléments concernant ce jeu peuvent être trouvés dans l'article de Wikipédia.

Tags

Niveau de lecture

Aidez-nous à évaluer le niveau de lecture de ce document.

Il vous semble :

Si vous souhaitez expliquer votre choix, vous pouvez ajouter un commentaire (qui ne sera pas publié).