Utilisateur:Lehalle/Décompressions mathématiques/Les mathématiques des Sudoku
Un article de Wikipédia, l'encyclopédie libre.
[modifier] Les mathématiques des Sudoku
Il est tèrs difficile d'éviter ces grilles qui fleurissent partout: sur les journaux, les pages internet, le sachets des buralistes, dans les transports en commun, etc...
Un petit rappel: un Sudoku est une grille carrée de neuf cases de coté, découpée en neuf sous grilles carrées de trois cases de coté. La grille est partiellement remplie avec des chiffres entre 1 et 9. Le but de jeu est de terminer de la remplir de chiffre de 1 à 9, de telle sorte que:
- chaque ligne contienne exactement tous les chiffre de un à neuf
- de même pour chaque colonne
- et de même pour chaque sous grille.
Les mathématiciens étant plutôt habitués à manipuler des suites de chiffres, certains dentre eux se sont penchés sur le sujet (essentiellement des algébristes et des logiciens). La première question soulevée fûtd e trouver un Algorithme (une suite d'action pré déterminées) qui résoud n'importe quel Sudoku. La réponse a été vite trouvée: grâce à la puissance des ordinateurs, il est tout à fait possible de tester intelligemment toutes les solutions possibles.
Virent ensuite des questions plus délicates:
- combien de grilles différentes de Sudoku existe-t-il?
- quelle est la grille de départ comportant le moins de chiffres?
- le fait d'avoir neuf cases rend-il les choses spécifiques?
Tout d'abord, notons qu'un formalisme de mathématique bien connu permet de ramener tout Sudoku à un problème de coloriage: si on relie par un trait chaque case:
- à toutes celles de sa sous grille
- à toutes celles de sa ligne
- à toutes celles de sa colonne
et que l'on choisit une couleur par chiffre, alors résoudre un sudoku revient à colorier toutes les cases sans qu'aucune case voisine (qui lui est reliée par un trait tracé plus haut) n'ait la même couleur...
(couleurs du Sudoku)
Est-ce plus simple? En fait non puisqu'il s'agit exactement du même problème, en revanche les mathématiciens sont habitués à ce genre de coloriages: un des grands théorèmes mathématique résolu en YYYY s'appelle le Théorème des quatre couleurs et est de ce genre. Son énoncé est simple: est-il possible de colorier tout coloriage pour enfant en utilisant seulement quatre couleurs et de telle sorte que deux cases mitoyennes n'aient jamais la même couleur. Essayez-donc avec un coloriage pour enfant, vous verrez que cela n'est pas si facile.
Une autre branche des mathématiques s'applique aux Sudoku, il s'agit de l'étude des Permutations. On peut en effet se demander s'il est possible de transformer un Sudoku en un autre simplement en permutant des cases (un peut comme on passe d'un mélange de Rubiks cube à un autre). C'est ainsi que l'on peut regroupper les Sudoku en familles, et c'est comme cela que AAA et BBB ont dénombrés le nombre de grilles différents possibles (NNNN).
L'étude des groupes de permutations a de nombreuses autres applications que les Sudoku, notemment l'étude des Tresses. Un tresse est un ensemble de grins entrelaçés (formant des noeuds), tenus par les haut et par le bas. Les questions qu'on se pose est de savoir s'il est possible de dénouer tous les noeuds d'une tresse. Les résultats obtenus s'appliquent en chimie des Polymères et en Cryptographie.
Pour terminer ce bref tour d'horizon, nous pouvons nous interroger sur le pourquoi de ce soudain engouement pour les Sudoku (un peu comme le Rubix cube à son époque).
(conclusion sur la futilité)
