La résolution des Sudoku, une affaire de couleurs...
Publié par Michel le 09/06/2007 à 00:00
Source: Notices of the American Mathematical Society
Illustrations: Techno-science.net d'après Agnes M. Herzberg et M. Ram Murty
Si vous vous êtes déjà trouvé bloqué devant un problème de Sudoku, vous avez peut-être imaginé que l'énigme n'avait pas de solution, ou, lorsque finalement vous en résolviez un, que votre solution n'était pas forcément la seule.

Ces questions et d'autres sont explorées dans l'article Sudoku Squares and Chromatic Polynomials d'Agnes M. Herzberg et M. Ram Murty, paru dans l'édition de juin-juillet des Notes de l'AMS (American Mathematical Society) dans lequel les auteurs utilisent des outils mathématiques de la théorie des graphes (Le terme de graphe désigne en mathématiques une opération d'application. Il possède deux acceptions :) pour analyser systématiquement des problèmes de Sudoku. Ils y démontrent également que l'analyse de ce type de problèmes conduit vers certains problèmes non résolus de cette théorie (Le mot théorie vient du mot grec theorein, qui signifie « contempler, observer, examiner ». Dans le langage courant, une théorie est une idée ou une connaissance spéculative, souvent...).


Un problème de Sudoku à solution unique, dont 17 chiffres sont donnés

Dans ce contexte (Le contexte d'un évènement inclut les circonstances et conditions qui l'entourent; le contexte d'un mot, d'une phrase ou d'un texte inclut les mots...), un "graphe (Le mot graphe possède plusieurs significations. Il est notamment employé :)" est un ensemble (En théorie des ensembles, un ensemble désigne intuitivement une collection d’objets (les éléments de l'ensemble), « une multitude qui peut être comprise comme un...) de noeuds reliés par des segments. On peut représenter les 81 cases d'un Sudoku comme les 81 noeuds d'un graphe, et l'on attribue à chacun des chiffres de un à neuf une couleur (La couleur est la perception subjective qu'a l'œil d'une ou plusieurs fréquences d'ondes lumineuses, avec une (ou des) amplitude(s) donnée(s).) différente (En mathématiques, la différente est définie en théorie algébrique des nombres pour mesurer l'éventuel défaut de dualité d'une application définie à l'aide de la trace, dans l'anneau des entiers...). Dans un graphe de Sudoku, deux noeuds sont reliés par un segment si les deux cases qu'ils représentent appartiennent à une même ligne, une même colonne, ou à un même bloc de 3 sur 3 cases. Puisque aucune ligne, aucune colonne, ni aucun bloc ne doit contenir plus d'une fois le même chiffre (Un chiffre est un symbole utilisé pour représenter les nombres.), le graphe ne possédera aucun noeud relié à un nœud de la même couleur. (Par exemple, en supposant que l'on représente le 1 avec la couleur rouge (La couleur rouge répond à différentes définitions, selon le système chromatique dont on fait usage.), deux noeuds rouges reliés par un segment signifieraient qu'une ligne, une colonne, ou un bloc posséderait deux 1, ce qui est interdit par la règle du Sudoku).

Dans le langage de la théorie des graphes, un graphique coloré sans connexion entre les noeuds de même couleur est appelé une "coloration propre". Ce que les amateurs de Sudoku tentent de réaliser chaque jour (Le jour ou la journée est l'intervalle qui sépare le lever du coucher du Soleil ; c'est la période entre deux nuits, pendant laquelle les rayons du Soleil éclairent le ciel. Son début (par...) est d'étendre un graphe partiellement coloré à un graphe à coloration propre (le puzzle initial avec ses cases vides signifie que le graphe le représentant possède des nœuds qui demandent à être coloriés).

L'analogie entre les Sudoku et les graphes étant en place, Herzberg et Murty ont pu utiliser des outils de théorie des graphes pour démontrer des théorèmes sur ce type de problèmes. Par exemple, ils démontrent que le nombre (La notion de nombre en linguistique est traitée à l’article « Nombre grammatical ».) de façons différentes d'étendre une coloration partielle est donné par un polynôme (En mathématiques, un polynôme est la combinaison linéaire des puissances d'une variable, habituellement notée X. Ces objets sont largement utilisés en pratique, ne serait-ce que parce qu'ils...). Si la valeur de ce polynôme est zéro (Le chiffre zéro (de l’italien zero, dérivé de l’arabe sifr, d’abord transcrit zefiro en italien) est un symbole marquant une position vide dans l’écriture des nombres en notation...) pour un Sudoku donné, alors le puzzle n'a aucune solution ; si la valeur est 1, le puzzle n'a qu'une solution ; et ainsi de suite. Ils démontrent également que, pour qu'un Sudoku quelconque puisse n'avoir qu'une solution unique, au moins 8 des 9 chiffres doivent apparaître dans le problème posé ; si seulement 7 chiffres apparaissent, alors le puzzle possède au moins deux solutions. Et ceci évoque une question mathématique (Les mathématiques constituent un domaine de connaissances abstraites construites à l'aide de raisonnements logiques sur des concepts tels que les nombres, les figures, les...) non résolue: "il serait extrêmement intéressant de déterminer sous quelles conditions une coloration partielle peut être étendue à une coloration [propre] unique", écrivent les auteurs.

Certains Sudokus sont plus difficiles à résoudre que d'autres, les plus ardus ne contenant que très peu de chiffres au départ. La détermination de ce nombre minimum d'entrées nécessite de s'assurer qu'un problème n'a qu'une seule solution. Herzberg et Murty donnent un exemple d'un Sudoku avec 17 entrées qui ne possède qu'une solution (grille ci-dessus). Aussi le nombre minimum est au plus 17. Cependant cela pourrait être 16 ou plus petit encore, mais personne ne le sait. On pourrait penser par ailleurs qu'un problème avec de nombreux chiffres donnés au départ est susceptible de n'avoir qu'une seule solution, mais ce n'est pas forcément le cas. L'article donne l'exemple d'un puzzle à 29 chiffres donnés qui possède au final deux solutions différentes (grille ci-dessous).


Un problème de Sudoku à deux solutions, dont 29 chiffres sont donnés

Et si vous vous demandez quand votre revue préférée manquera de problèmes de Sudoku, les auteurs affirment que le nombre de Sudoku distincts se situe quelque part autour (Autour est le nom que la nomenclature aviaire en langue française (mise à jour) donne à 31 espèces d'oiseaux qui, soit appartiennent au genre Accipiter, soit constituent les 5 genres Erythrotriorchis,...) de 5,5 milliards, ce qui devrait s'avérer suffisant pour occuper les afficianados pendant de nombreuses années encore.

Page générée en 0.283 seconde(s) - site hébergé chez Amen
Ce site fait l'objet d'une déclaration à la CNIL sous le numéro de dossier 1037632
Ce site est édité par Techno-Science.net - A propos - Informations légales
Partenaire: HD-Numérique