.gif) |
Le SUDOKU |
|
Le SUDOKU |
|
L Les grilles du sudoku !Le
Soir
Le sudoku déchaîne les passions. La combinaison de chiffres, juste pour le plaisir, remonte au moins au XVIIIe siècle.Une bizarre sensation de stress nous prend quand on cherche des yeux la première case. Celle qui ne peut être remplie que par un chiffre, et un seul. Pas désagréable, mais un peu énervant. Comme quand je cherche quelque chose dans l'appartement et que je ne mets pas la main dessus tout de suite, décrit Guillaume, 33 ans, accro de sudoku depuis à peine une semaine. L'inscription du premier chiffre dans la grille procure une pointe de satisfaction, juste assez forte pour ne plus pouvoir lâcher. Ce qu'il y a de meilleur, c'est le plaisir de la résolution, quand les derniers chiffres se logent comme par magie dans les bonnes cases, quand un 1 indispensable dans une ligne l'est aussi dans sa colonne et dans son carré de 9 cases. Je me sens alors des pouvoirs de superhéros, raconte Jasmine, 39 ans, qui rentre de deux semaines de plage. C'est si bon quand l'harmonie s'installe... Le sudoku s'est imposé comme le jeu de l'été. En Europe, la fièvre a d'abord pris les Anglais, à l'automne dernier, quand les premières grilles sont apparues dans le " Times ". Dimanche dernier, Edward Billig, un jeune Londonien de 23 ans, a remporté le championnat national du sudoku en remplissant une grille plus rapidement que ses milliers de concurrents. Au début de cet été, emportés par la vague anglo-saxonne, plusieurs quotidiens ont suivi, partout en Europe. Et cette fois c'est au tour du " Soir ". Où que vous passiez vos vacances, vous n'échapperez donc pas aux 81 cases de casse-tête : Ça fait fonctionner mes méninges et il paraît que c'est bon pour la mémoire, lance un jeune retraité qui a beaucoup voyagé. L'histoire récente du sudoku se raconte comme une fable. Celle d'un juge néo-zélandais, Wayne Gould, retiré en Asie, qui découvre le jeu au Japon en 1997 et passe six ans à imaginer un logiciel permettant de créer de nouvelles grilles. A l'automne 2004, il vend sa trouvaille au " Times " puis à une soixantaine d'autres journaux dans une vingtaine de pays. A l'heure où vous vous plongez dans votre premier sudoku, il est pratiquement millionnaire. C'est donc l'informatique qui a permis le succès de cet été. Au Japon, le jeu existe depuis 1984 sous le nom de sudoku. Mais l'éditeur nippon n'a rien inventé : il avait lui-même importé ce casse-tête des Etats-Unis où, depuis 1979, le " Dell Puzzles Magazine " publie des grilles du genre appelées " Number Place ". Parce qu'il n'y a aucune opération à faire (contrairement au " carré magique "), le sudoku s'apparente à la combinatoire, la science du dénombrement et de la classification des configurations. La combinatoire, utilisée notamment dans l'informatique et la cryptologie pour coder des messages et tester l'efficacité des codages, n'est pas seulement ludique, mais beaucoup de jeux mathématiques s'y réfèrent. Le sudoku est de la famille des " carrés latins " : disposer un certain nombre de chiffres (neuf par exemple) dans une grille de 9 9 cases afin que les chiffres ne se répètent jamais sur une même ligne ou sur une même colonne. Le carré latin peut se compliquer. Accrochez-vous : on parle de carré gréco-latin quand on superpose deux carrés latins pour former des couples de chiffres qui eux-mêmes ne doivent se répéter qu'une fois dans la grille. L'un des précurseurs de la combinatoire est le Bâlois Leonhard Euler (1707-1783), génie des maths et auteur d'une quantité considérable de travaux. " Sudokiste " avant l'heure, il posa notamment le problème des " trente-six officiers ". Le voici : prenez une assemblée de 36 officiers, de six différents grades et issus de six régiments différents. Comment peut-on les ranger dans un carré, de manière que les officiers de chaque ligne et de chaque colonne soient de grade et de régiment différents ? Vous voulez essayer ? Ce problème vous donnera plus de fil à retordre que le sudoku " diabolico " que le " Corriere della Sera " livre chaque dimanche en pâture à ses lecteurs : en trois siècles, il n'a jamais été résolu. car il ne peut pas l'être. Le problème d'Euler doit passer par la résolution d'un carré gréco-latin comptant six cases de chaque côté et Euler soupçonnait que son problème était une colle. Il a fallu attendre 1901 pour que le mathématicien français Gaston Tarry démontre que le carré gréco-latin d'ordre 6 n'a pas de solution... Leonhard Euler s'est également attaqué à une énigme sur laquelle avaient planché beaucoup de mathématiciens avant lui : comment peut-on faire parcourir à un cavalier toutes les cases d'un échiquier, mais une seule fois chacune, en respectant bien sûr son mode de déplacement ? Le Bâlois a trouvé la solution et l'a publiée en 1759 dans les " Mémoires de l'Académie des Sciences de Berlin ". Pour toutes ces raisons, les Anglais tiennent Leonhard Euler pour le précurseur du sudoku.
Leonhard Euler, génie des maths
Leonhard Euler devait être pasteur, comme son père. Il est devenu l'un des plus grands mathématiciens de l'histoire. Euler ? Une capacité d'abstraction et une intelligence hors du commun, résume un historien des mathématiques. Son apport a été considérable dans le domaine des maths, mais aussi de l'astronomie, de la mécanique, de la physique, de l'optique et de l'acoustique notamment. Un homme pour qui tout pouvait faire l'objet de réflexion mathématique, dit Jean-Claude Pont, épistémologue. Celui que l'on peut considérer comme le père du sudoku, grâce à ses avancées dans la combinatoire, est né à Bâle, en Suisse, en 1707. Diplômé de la Faculté de philosophie à 18 ans, Euler déposa en 1726 sa candidature à l'Université de Bâle pour une place de professeur de physique. Mais on la lui refusa. Leonhard Euler partit alors pour Saint-Pétersbourg, où ses deux acolytes, Nicolaus et Daniel Bernoulli, avaient été invités par l'Académie des sciences. C'est là qu'il publia la moitié de ses travaux, l'autre paraîtra à Berlin pendant les vingt-cinq ans qu'il passa à l'Académie des sciences dès 1741. Mais Euler, profondément pieux et attaché aux valeurs de l'Eglise réformée, ne partageait pas les idées voltairiennes soutenues par Frederic II. En 1766, le savant bâlois retourna à Saint-Pétersbourg. Aveugle dès 1771, mais encore très actif, il est mort en 1783. Il y a quarante ans, son tombeau a été transporté au cimetière du monastère Alexandre-Nevski.
Le sudoku est un jeu de logique d'origine japonaise La grille de départ se compose de 9 carrés (appelés "boîtes") de 9 cases, soit d'un total de 81 cases, sur laquelle de 25 à 30 chiffres sont déjà disposés
Les règles
Le but du jeu: remplir toute la grille en ajoutant un chiffre (de 1 à 9) par case. Attention: le même chiffre ne doit figurer qu'une seule fois dans chaque colonne verticale, qu'une seule fois dans chaque ligne horizontale et qu'une seule fois dans chaque boîte de 9 cases. Pas besoin de calculer le total des lignes ou des colonnes. Le remplissage de la grille ne réclame aucune compétence pour le calcul mental, juste une certaine logique. Et de la patience! Pour débuter, une astuce consiste à raisonner par bloc de trois boîtes alignées horizontalement ou verticalement. Identifiez un chiffre qui se trouve dans deux des trois boîtes et cherchez la case oµ il devrait se situer dans la troisième. Dans les cas les plus faciles, vous n'aurez pas le choix; sinon, deux ou trois cases peuvent convenir. Et par recoupements successifs, la solution apparaîtra. Un dernier conseil: travaillez au crayon et prévoyez une bonne gomme! Explication animée des règlesSUR le site
TACTIQUES
Sur la toile
Des astuces, des explications ou des grilles supplémentaires? Rendez-vous sur: Logiciel de création (logiciel libre pour générer des Sudokus). http://naxossudoku.sourceforge.net.fr.free.fr/sudoku/ (pour générer des Sudokus à usage privé)
Exploitation pédagogique Narendra Jussien introduit le Sudoku dans une école d'ingénieur
[ 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.
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 :
- 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.
http://www.e-tud.com/une_portrait-nj.htm
|
NDLR]
Né en 1973, diplômé de l'Institut de Mathématiques Appliquées,
Narendra Jussien est titulaire d’un doctorat de l'université de
Rennes 1, et d'une habilitation à diriger des recherches à l'université
de Nantes depuis 2003. Ses activités de recherche portent sur la
programmation par contraintes (
Mais
au fait le Sudoku c’est quoi ?