Sudoku ?!?

On ne peut plus y échapper. Ces petites grilles de chiffres fleurissent dans le train, dans les salles d'attente, sur les bureaux des collègues, etc. En japonais, su signifie chiffre et doku, unique. Mais, ce jeu a été inventé par un américain ! Les premières grilles composées au début à la main sont en effet apparues aux USA en 1979. Wikipedia nous informe que leur auteur est sans doute Howard Garns un architecte à la retraite, mort en 1989, bien avant le succès du Sudoku que l'on impute à Wayne Gould, un juge néo-zélandais, lui aussi à la retraite à Hong-Kong.

Les règles

Les règles sont simples : une grille carrée de 81 cases est divisée en 9 blocs plus petits de 9 cases chacun. Dans certaines des 81 cases, des chiffres sont inscrits. Il faut remplir les cases vides, en utilisant les chiffres de 1 à 9, de façon qu'aucun chiffre n'apparaisse deux fois dans la même ligne, ni deux fois dans la même colonne, ni deux fois dans le même sous-carré. La solution est unique. Il existe de nombreuses méthodes informatiques pour résoudre très rapidement un problème de sudoku. La plupart du temps ces méthodes sont basées sur des algorithmes dits de retour en arrière systématique (backtracking). L'idée est la suivante : affecter une valeur à une case vide et continuer ainsi tant que les choix sont cohérents. Dès qu'une incompatibilité est détectée, le programme revient sur son choix précédent (le retour arrière) et essaie une autre valeur. Si aucune valeur n'est alors disponible, il continue à retourner en arrière, jusqu'à ce qu'il puisse repartir en avant. Cette méthode est systématique et permet à coup sûr de résoudre un problème de sudoku. Mais, aucun joueur humain ne procède de cette façon ! Notre mémoire est trop peu performante pour bien l'appliquer.

Diverses techniques pour résoudre les sudoku tant à la main qu'à l'aide d'un programme informatique sont très bien décrites sur Wikipedia.

Sudoku et IA

Différentes techniques et règles existent et sont même répertoriées sur les innombrables sites sur le sudoku que l'on trouve sur internet. Certaines sont très simples et n'ont besoin d'aucun artifice comme la méthode de la case forcée ou celle du chiffre fixé.

Des règles simples : case forcée et chiffre forcé

Considérons la case marquée d'un point rouge dans l'exemple ci-contre. En observant les autres chiffres présents dans le même bloc (2,7,8,9), la même ligne (3,4,6,7,9) et la même colonne (2,3,5,8), on découvre qu'il ne reste qu'une unique possibilité (1). C'est une case forcée. Considérons maintenant un chiffre donné. Par exemple, le 4. Dans le bloc qui contient la case marquée d'un point bleu, il n'y a pas de 4. Où peut-il être ? Les différents 4 déjà portés contraignent fortement les possibilités. Le 4 ne peut être placé qu'à la place du point bleu. C'est un chiffre forcé.

Ces deux techniques utilisées de manière alternée permettent déjà d'avancer largement dans la résolution des sudoku et même de résoudre certaines instances faciles.

Ces techniques faciles d'accès et d'applications atteignent assez vite leurs limites. Il est alors nécessaire d'utiliser des approches plus subtiles. Mais, pour cela il faut se munir d'une ... gomme !

Principes du raisonnement humain

Diverses techniques existent mais la grande majorité respecte des principes simples. Le premier principe est de ne pas chercher à affecter une valeur à une case mais plutôt d'écarter pour chaque case les valeurs qui NE pourront PAS lui être affectée. On réduit de fait l'espace des possibilités. C'est là où la gomme est utile. Les joueurs prennent note des chiffres encore possibles dans chaque case.

Avec cette information, toutes sortes de raisonnement sont possibles. Sur la figure à droite sont mentionnées en bleu les valeurs possibles pour chaque case. Par exemple, considérons la septième colonne de la figure précédente (nous prenons toujours le même exemple). Deux cases ne contiennent comme valeurs possibles que 7 et 5. Ils ne peuvent apparaître ailleurs. La troisième case ne peut donc que contenir un 6 (c'est d'ailleurs la seule case pour cette colonne qui accepte un 6).

Le raisonnement ici était évident mais ce n'est pas toujours le cas. Considérons la figure de gauche, les valeurs possibles sur la troisième colonne sont reportées. On constate que les valeurs 4 et 8 sont les seules possibilités pour les cases 4 et 5. Ces deux valeurs ne peuvent donc être affectées à aucune autre des cases. Cette constatation conduit à ne laisser que la valeur 3 possible dans la case 6 et donc la valeur 7 dans la case 2 et enfin la valeur 1 dans la case 3. On voit donc que cette démarche peut être très puissante.

Ce raisonnement (qui s'appelle parfois la simplification des séries de possibilités) se généralise très bien à un nombre quelconque de cases (toujours dans une même région) présentant cette particularité. Il est même prouvé qu'il n'est pas possible de déduire dans une région donnée plus de valeurs qu'en utilisant cet ensemble de techniques. On peut appliquer ce raisonnement local à toutes les régions de notre grille (les lignes, les colonnes et les blocs). Il est important de noter que les déductions qui sont alors réalisées peuvent (et doivent) être réutilisées d'une région à l'autre.

Les principes de raisonnement «humain» que l'on peut mettre en évidence ici sont les suivants :

Vers une intelligence artificielle

Ces trois principes sont à la base d'une technique récente issue de l'intelligence artificielle et de la recherche opérationnelle : la programmation par contraintes.

La programmation par contraintes permet donc de résoudre le problème plus comme le ferait un être humain que comme le ferait une machine. D'autant plus que les trois-quarts des raisonnements imaginés pour résoudre le sudoku s'attaquent en fait à une problématique déjà explorée par les chercheurs en Intelligence Artificielle : le problème du «tous différents». Un solveur de contraintes (comme choco) possède ainsi tous les atouts pour «raisonner» efficacement sur, entre autres, ce type de problématique et résoudre alors le sudoku comme un joueur humain sans avoir été conçu spécifiquement pour le ce problème en particulier.

Remarque : idéalement, l'itération des raisonnements locaux conduit à une solution. Dans la plupart des instances de sudoku, c'est exactement le cas. Mais, cette phase de propagation n'est pas toujours suffisante. Les solveurs de contraintes (les outils logiciels mettant en œuvre ces principes) basculent alors dans une phase d'énumération des solutions basée sur le principe de retour arrière systématique évoqué précédemment.

Programmation par contraintes

Le développement des moyens de calcul dans les années 1960 a engendré une multitude de travaux autour de la résolution de problèmes. Cette dynamique a permis de créer des domaines comme la recherche opérationnelle, l'analyse numérique, le calcul symbolique, le calcul scientifique et une part importante de l'intelligence artificielle et des langages de programmation. La programmation par contraintes est une discipline qui rassemble, hybride et unifie les idées communes à ces domaines pour s'attaquer à des problèmes d'aide à la décision.

La technologie des contraintes, d'origine française et où l'Europe est au premier plan, est devenue en quinze ans un outil important de modélisation et de résolution automatiques de problèmes, académiques et industriels. Ainsi, elle a été appliquée avec succès en planification de production, gestion du trafic dans les villes et les aéroports, allocation de fréquences, vérification de circuits électroniques, biologie moléculaire, robotique et conception de produits industriels.

L'association française de programmation par contraintes est une association de loi 1901. Sa vocation est de réunir toutes les personnes s'intéressant, professionnellement ou non, à la programmation par contraintes : son étude, ses fondements théoriques, ses applications, son évolution, son enseignement et sa diffusion. Les domaines couverts incluent : la programmation en logique, la programmation par contraintes et leurs extensions, la logique, les problèmes de satisfaction de contraintes discrets et continus (SAT, CSP), la programmation mathématique et l'optimisation combinatoire.