Les Mines de Nantes ont fait du Su Doku un support pour l'enseignement en informatique ! Car ce jeu de logique présente des similitudes avec la « programmation par contraintes »...

Ils sont partout ! Armés d'un crayon à papier et d'une gomme, concentrés sur ces grilles de 81 cases... Les amateurs de Su Doku ont fait des transports en commun leur terrain de jeu. Bien qu'il porte un nom japonais - « su » pour « chiffre », « doku » pour « unique » -, le jeu a été inventé par un Américain. Les premières grilles, composées à la main, sont apparues aux Etats-Unis dès 1979. Un juge zélandais, retraité à Hong Kong, met ensuite au point un programme permettant d'engendrer automatiquement des grilles d'énoncés. Il obtient de les publier dans le Times fin 2004 et le Daily Telegraph en 2005. Arrivé en France cet été, le Su Doku suscite un véritable engouement. Tout simplement parce qu'il permet de tuer le temps ? Ou bien parce qu'il réveille l'esprit logique qui sommeille en nous ?

« Les étudiants jouent au Su Doku pendant et entre les cours ! », lance Narendra Jussien, professeur depuis 1998 au département informatique des Mines de Nantes. Ses thèmes de recherche portent sur la programmation par contraintes. Or celle-ci présente des similitudes frappantes avec le Su Doku ! A l'initiative de l'enseignant-chercheur, le jeu est ainsi devenu un « outil pédagogique » pour les cours de programmation par contrainte en troisième année, ainsi que pour l'option Génie informatique pour l'aide à la décision en quatrième année. « La programmation par contraintes est un peu ardue... L'introduire par le Su Doku permet de mieux faire passer les choses. Je présente une grille aux élèves, et je leur demande de m'expliquer par des mots de quelle manière ils la résolvent. » Les règles du Su Doku se formalisent très bien, et elles constituent les bases des règles de la programmation par contraintes. Une des stratégies de résolution du Su Doku consiste à identifier ce qui ne peut pas être retenu comme une solution, ce que nous appelons « la réduction de domaines ». Par ailleurs, le raisonnement sur une ligne a des impacts sur les colonnes et sous-carrés. Repérer les contraintes qui s'appliquent dans un sous-carré permet ensuite de les transmettre à une autre zone, ce que l'on appelle la « propagation des contraintes ».

Dans le cadre de leur projet d'études de quatrième année, cinq étudiants de l'école ont choisi de s'intéresser au Su Doku... Objectifs du projet : réaliser une application de résolution du Sudoku, évaluer la difficulté d'une grille, fournir une génération de grilles pour le site de l'école, trouver le nombre minimal de cases préremplies, sachant qu'aujourd'hui ce nombre se situe à 17. Tristan Grädener, 21 ans, participe à ce travail. Comme ses camarades, il a choisi l'option Génie informatique pour l'aide à la décision. « La programmation par contraintes est très importante dans cette option. C'est relativement nouveau pour nous ». Et apparemment passionnant : « On arrive à programmer des trucs complexes avec juste quelques lignes de code ! J'ai envie d'aller plus loin dans cette discipline. Eventuellement faire un doctorat ».

DE LA PROGRAMMATION PAR CONTRAINTES A L'INTELLIGENCE ARTIFICIELLE
La programmation par contraintes, d'origine française, est devenue en 15 ans un outil indispensable à la modélisation et la résolution automatique de problèmes, académiques et industriels. Plus concrètement, la technologie des contraintes est appliquée en planification de production, gestion du trafic dans les villes et les aéroports, vérification de circuits électroniques, robotique, conception de produits industriels. « C'est de la programmation par contraintes qu'hérite l'intelligence artificielle, dont le but est d'automatiser le raisonnement. » Aussi Narendra Jussien utilise-t-il également le Su Doku au sein de l'option Génie informatique pour l'aide à la décision. « Il s'agit de problèmes combinatoires : il y a beaucoup de solutions mais très peu permettent d'optimiser les coûts », explique l’enseignant. Cette année, le tronc commun d'informatique a été complètement réformé aux Mines de Nantes. « A l'issue de leur scolarité, nous estimons que nos étudiants doivent être capables de mettre en œuvre une application informatique non triviale (algorithmes), de manipuler les bases de données et d'interagir avec les utilisateurs, explique-t-il. Il ne suffit pas de résoudre un problème, il faut être capable d'en rendre compte ! »

Réagir dans le Forum

- Vous êtes en accord avec ce texte ou en profond désaccord. Faites entendre votre voix

..........................