portraitSes activités de recherche portent sur la programmation par contraintes (voir la définition dans l'encyclopédie), sujet sur lequel il est auteur de près d'une centaine de publications tant au niveau national qu’international. Depuis 2004, Narendra Jussien est président de l'Association Française pour la Programmation par Contraintes. Il est également enseignant à l'École des Mines de Nantes (EMN), et notamment pour le cours de programmation par contraintes dans lequel il a introduit le Sudoku comme outil pédagogique.

grille sudokuMais au fait le Sudoku c’est quoi ? Le Sudoku est une grille de jeu carrée, de neuf cases de côtés, subdivisé en autant de carrés identiques, appelés régions. La grille contient des chiffres de 1 à 9 et des cases vides. Le but du jeu est de remplir les cases vides en respectant la règle suivante : chaque ligne, colonne et région ne doit contenir qu'une seule fois tous les chiffres de 1 à 9. Pour chaque grille, la solution est unique.

Les similitudes entre le Sudoku et la programmation

Les règles utilisées pour résoudre à la main un Sudoku sont la plupart du temps des règles intuitives ou inconscientes. Les internautes les ont répertoriées dans de nombreux sites qui fleurissent sur le sujet. Lorsqu'on examine de plus près ces règles, on se rend compte qu'elles se modélisent et se généralisent très facilement. On peut alors identifier un certain nombre de principes généraux de résolution d'un sudoku par un humain :

  1. Raisonner non pas sur la valeur que l'on cherche à attribuer à une case mais plutôt par élimination : quelles sont les valeurs qui NE peuvent PAS être dans cette case : dans nos domaines, on appelle cela la "réduction de domaine" ;
  2. Raisonner localement mais systématiquement et de manière "évoluée" : au Sudoku, on raisonne sur une ligne, sur une colonne, sur un sous-carré (parfois sur 2 de ces régions à la fois). Sur ces régions, on peut développer des raisonnements relativement évolués (la règle dites des "naked pairs" par exemple) pour déterminer une nouvelle information (le plus souvent une valeur impossible pour une case). Ce raisonnement local est lié à la notion de "contrainte" : une relation devant être vérifiée (ici la règle d'apparition unique de chacun des chiffres) ;
  3. Transmettre les déductions faites dans une région à toutes les autres régions potentiellement concernée : on appelle cela la "propagation de contraintes".

Ces trois principes sont au coeur de la programmation par contraintes et explique son classement dans les disciplines héritières de l'intelligence artificielle : il s'agit d'automatiser et de généraliser un raisonnement humain.

L'intérêt de tout ceci est que la programmation par contraintes n'est pas utilisée uniquement pour résoudre des Sudoku (ce qu'elle fait d'ailleurs très bien - le solveur proposé sur cette page utilise un solveur de contraintes - c'est ainsi qu'on appelle les logiciels à base de programmation par contraintes) mais plus généralement sur des problèmes combinatoires complexes tels que la planification d'horaires dans un hôpital ou dans un centre d'appels (qui sont soumis à des contraintes règlementaires très fortes) ou encore l'organisation des tournées de livraisons dans la grande distribution.

Plus généralement, la programmation par contraintes est utilisée dans des domaines comme la logistique, la production, la conception, les réseaux, etc.

L'introduction du Sudoku comme outil pédagogique...

Utiliser le Sudoku pour introduire à ces concepts récents et assez pointus permet une approche ludique assez pédagogique (le retour des élèves est positif sur ces sujets). Je l'utilise ainsi dans un cours de programmation par contraintes en dernière année à l'école des Mines de Nantes et aussi dans un cours nommé "Modèles et Algorithmes de Graphes" en troisième année (l'école des Mines de Nantes est en quatre ans).

Au delà de ces utilisations, j'ai lancé et j'encadre un projet informatique de 5 élèves autour du sudoku. L'objectif est triple :

grille sudoku

  • générer des grilles (c'est assez fortement lié à la résolution mais pose des problèmes spécifiques) ;
  • évaluer la difficulté des grilles (ce n'est pas facile, nombreux sont les joueurs qui ont constaté un décalage fort entre la difficulté affichée d'une grille et sa difficulté réelle - nous cherchons des modèles d'évaluation plus proche des méthodes de résolution employées par les joueurs) ;
  • fournir des outils d'aide à la résolution (fournir la solution d'un sudoku à un joueur n'a aucun intérêt - on veut comprendre pourquoi, avoir des indices pour pouvoir avancer, etc.).

Enfin, dès la première année, nous proposons aussi un projet informatique (dans le cadre de l'initiation à l'informatique) pour travailler à la résolution des grilles (c'est un collègue qui propose le sujet).

... amené à être utilisé par les autres niveaux d'éducation ?

Le Sudoku est un jeu logique dont les règles sont très simples et donc très accessibles (c'est ce qui explique sûrement en partie son succès actuel). Il me paraît adapté pour développer les capacités de raisonnement logique et résolution de problème. Nous réfléchissons actuellement à l'EMN à la mise en place dans le cadre d'opération de types "Main à la pâte" d'une initiation à l'informatique, la logique et le raisonnement dans le primaire, les collèges ou les lycées.

L'enseignement par le jeu, un concept pédagogique essentiel à l'éducation ?

Je ne sais pas si l'enseignement a BESOIN d'être de plus en plus ludique, ce que je constate simplement dans ma pratique quotidienne c'est que le jeu permet de captiver l'intérêt des étudiants et d'introduire des concepts avancés de manière plus douce. Trouver de temps en temps un exemple comme le Sudoku permet de renouveler son enseignement.

Narendra Jussien, enseignant-chercheur à l'EMN

Donner votre avis sur le blog