vendredi 13 juillet 2012

17:44

Une échelle de Richter pour les grilles de sudoku

Plusieurs lecteurs de ma chronique Improbablologie, ayant du mal à supporter l'arrêt estival du supplément "Science & Techno" du Monde dans lequel elle est publiée, m'ont fait part de leur détresse et de leur sensation de manque. En attendant que la chronique reprenne, il y aura donc un zeste de science improbable chez le Passeur...

"L’homme a pris la mesure du monde, au sens propre comme au figuré. Il l’arpente autant qu’il le soupèse, il l’évalue, le mètre et le calcule. Il a créé des échelles pour presque tout : l’échelle de Richter pour la magnitude des séismes, l’échelle de Beaufort pour la vitesse des vents, l’échelle de Saffir-Simpson pour l’intensité des cyclones, l’échelle de Turin pour la menace que font peser les astéroïdes sur la Terre, des échelles de température (Kelvin, Celsius, Farenheit, Réaumur, etc), l’échelle de Kinsey pour l’orientation sexuelle, l’échelle de Bristol pour la typologie des excréments humains (à déconseiller à l’heure des repas), etc." Voilà ce que j'ai un jour écrit sur mon précédent blog, avant de m'empresser d'ajouter une nouvelle échelle à la liste, celle de la passion amoureuse, bel exemple de ce que j'appelle aujourd'hui l"'improbablologie", du nom de la chronique que je tiens chaque semaine dans le supplément hebdomadaire du Monde.

L'actualité scientifique vient aujourd'hui enrichir cette collection d'échelles. Donnons à la nouvelle venue les initiales de ses inventeurs, Maria Ercsey-Ravasz et Zoltan Toroczkai, et nommons-la l'échelle ERT. Mais que mesure-t-elle au juste ? Comme l'expliquent ses heureux parents dans l'étude qu'ils ont mise en ligne sur le site de pré-publications scientifiques arXiv, l'échelle ERT mesure... le niveau de difficulté des grilles de sudoku. Pour ceux qui auraient passé ces dernières années sur une île déserte ou qui se servent systématiquement des pages "Jeux" des journaux pour emballer le poisson, éplucher leurs légumes ou allumer leur barbecue, je rappelle que le sudoku est un jeu de chiffres et de logique. Comme vous pouvez le voir ci-dessus, il se présente sous la forme d'une grille carrée de 9 cases de côté, subdivisée en 9 blocs de 3 cases de côté. Certaines cases comportent des chiffres allant de 1 à 9 qui servent d'indices. Il faut, à l'aide de ces indices, remplir la grille de façon à ce que chaque rangée, chaque colonne et chaque bloc contiennent tous les chiffres de 1 à 9.

Les journaux ou les magazines de jeux indiquent le degré de difficulté des grilles, avec des graduations variables suivant les titres. Le plus souvent, cela va de "facile" à "difficile" en passant par "moyen", mais j'ai vu aussi du "débutant", de l'"expert", de l'"absurde" ou du "diabolique". Ces labels sont en général apposés par les sociétés qui fournissent les sudokus mais on est en droit de se demander quelle valeur scientifique ils ont. Comment ont-ils été testés ? Quels critères a-t-on retenus ? Le degré de difficulté est-il fonction du nombre d'indices disponibles ? L'échelle ERT est là pour répondre à ces questions ! Afin de rendre justice aux auteurs de l'étude, précisons que, pour eux, le sudoku n'est pas une fin en soi, mais seulement un exemple d'un certain type de problèmes mathématiques appartenant à la théorie de la complexité. Ajoutons également que l'engouement quasi planétaire pour ce jeu a, depuis quelques années, incité de nombreux mathématiciens à travailler dessus.

Afin de résoudre un sudoku, on fait tourner un algorithme – dans sa tête pour les courageux, sur un ordinateur pour les tricheurs ou les fainéants – comprenant des contraintes (les règles du jeu) et des données (les indices). L'échelle ERT mesure la difficulté que rencontre l'algorithme à trouver la solution. Pour la mettre au point, Maria Ercsey-Ravasz et Zoltan Toroczkai n'ont pas scanné le cerveau de centaines de joueurs en pleine action et ils n'ont pas non plus eu recours à un logiciel fonctionnant sur le principe de la force brute. Ce type de programme ne fait en quelque sorte que tester toutes les solutions les unes après les autres jusqu'à ce qu'il rencontre celle qui correspond aux indices de la grille (une véritable grille de sudoku n'accepte qu'une seule solution). Les auteurs de l'étude ont utilisé un algorithme plus évolué, qui recherche une solution de manière optimale en analysant la structure du problème. Et ils ont observé son comportement, la dynamique de son exploration.

Sur cette figure, on peut suivre la manière dont l'algorithme résout un bloc de 9 cases. Chaque chiffre testé est représenté par une couleur sur les courbes de droite. En haut, la grille est facile, avec 34 indices (les chiffres en noir), et on s'aperçoit que le programme hésite peu et trouve rapidement la solution. En bas, la grille est compliquée (c'est la même que celle qui ouvre ce billet). Disons même qu'il s'agit d'une des grilles les plus difficiles à résoudre selon les spécialistes, au point qu'elle en aurait gagné un surnom, la "Blonde Platine" (je vous laisse le loisir d'interpréter ce nom...). On constate que non seulement l'algorithme teste plusieurs chiffres pour chaque case, que la courbe suit une trajectoire tourmentée en faisant des allers-retours, mais qu'il faut aussi beaucoup plus de temps pour venir à bout du problème. Pour les auteurs, la dynamique de l'algorithme reflète la complexité du sudoku. Mais il ne s'agit pas pour autant de l'élément-clé de l'échelle ERT.

Maria Ercsey-Ravasz et Zoltan Toroczkai se sont aperçus que, lors de l'exploration de chaque case, l'algorithme traversait une phase en apparence chaotique. Ce passage est retranscrit graphiquement ci-dessus. Sur la ligne du haut, on est toujours dans une grille facile et l'on voit que l'épisode chaotique est bref (carré du milieu) et se réduit à sa plus simple expression : le logiciel a à peine le temps d'errer qu'il trouve déjà la solution (le chiffre 9, représenté par la couleur bleu ciel, après avoir hésité avec le 6, orange). En revanche, en bas, sur une grille plus compliquée, c'est le grand bazar pour l'algorithme qui, sur la même durée, n'est pas encore sorti de la phase chaotique. Il y parviendra après, je vous rassure... En testant plusieurs bases de données représentant des milliers de grilles, les auteurs de l'étude ont conclu que le meilleur indicateur de la difficulté d'un sudoku était précisément le temps que l'algorithme mettait à sortir de ce chaos. Plus il s'en dépêtrait vite, plus la grille était simple. Plus il vasouillait, plus la grille était difficile. Autre enseignement, le nombre d'indices joue un rôle mais n'est pas forcément déterminant. On sait par exemple que le nombre minimum d'indices nécessaires pour confectionner une grille avec une solution unique est de 17. Or, parmi toutes les grilles testées, celle qui est monté le plus haut est précisément la "Blonde Platine", avec une "note" de 3,5789, alors qu'elle dispose de 21 indices. Pour la petite histoire, la grille surnommée Al Escargot, qui avait connu son heure de gloire en 2006 en étant présentée comme la plus compliquée du monde, n'a obtenu qu'un score de 2,17...

Comme l'échelle de Richter, l'échelle ERT est une échelle logarithmique. Entre 0 et 1, on y trouve les grilles faciles, entre 1 et 2 les grilles moyennes, entre 2 et 3 les difficiles et au-delà de 3, les plus compliquées. Pour le moment, tout comme on n'a pas encore enregistré de séisme avec une magnitude de 10 sur l'échelle de Richter, il n'a pas été trouvé de grille atteignant la note de 4. Mais comme il existe 6,67 × 1021 grilles possibles, tout espoir de battre la Blonde Platine n'est pas perdu... Pour ne pas terminer sur une note trop futile, j'ajouterai qu'évidemment, cet essai de quantification des difficultés rencontrées par les algorithmes ne s'applique pas qu'au sudoku mais aussi à tous les problèmes mathématiques du même acabit.

Pierre Barthélémy (@PasseurSciences sur Twitter)

Collé à partir de <http://passeurdesciences.blog.lemonde.fr/2012/08/12/une-echelle-de-richter-pour-les-grilles-de-sudoku/>