Métrique du Sudoku
DIVERS
+ DE 2 ANS
Le 09/11/2019 à 10h42
3033 vues
Question d'origine :
Bonjour le guichet du savoir,
Des interrogations un peu délayées sur le sudoku. N'en retenez, bien sûr, que ce qui vous convient, en particulier si ma question devient olé-olé. Une réponse à la première question serait déjà précieuse.
Certaines grilles de sudoku proposées par des journaux sont assorties d'un niveau de difficulté, de 'très facile' à 'expert', par exemple. Il m'arrive de buter sur une 'facile' et de réussir une 'expert'. Quelles métriques sont-elles mises en oeuvre pour établir le niveau de difficulté d'une grille ?
Deux joueurs confrontés à la même grille ne suivent bien sûr pas les mêmes cheminements mentaux. Cependant certains types d'observations et de déductions se répètent. Existe-t-il une typologie (et donc des noms) des inférences classiques du sudoku ? Est-ce que les démarches des joueurs ont été étudiées ?
Est-ce qu'il existe des lois pas trop compliquées sur le Sudoku : par exemple sur l'unicité de la solution de la grille du jour, sur le moment où la grille est totalement résolue (il ne reste qu'une seule possibilité pour écrire chaque chiffre), même s'il reste encore des cases vides, etc.
Mes excuses pour ce foisonnement, et merci d'exister.
Vercoquin
Réponse du Guichet
gds_et
- Département : Équipe du Guichet du Savoir
Le 13/11/2019 à 09h18
Bonjour,
Voici les explications fournies par le-sudoku.fr sur les niveaux de difficulté :
« Niveaux de difficulté
Comment définir la difficulté d'une grille de sudoku ?
Plusieurs paramètres sont à prendre en compte :
• la taille du sudoku : plus il est petit, plus vite vous l'aurez terminé
• le nombre de cases pré-remplies : plus elles sont nombreuses, plus le sudoku sera facile - quoi que en fait, ce nombre de cases ne soit pas vraiment une mesure exacte de la complexité
• la disposition des chiffres : leur placement dans la grille
Aussi curieux que cela puisse paraître, deux grilles de sudoku peuvent tout à fait placer des cases pré-remplies de façon totalement identique, mais avoir une difficulté complètement différente en fonction de la valeur des chiffres qui sont placés.
On peut en fait mesurer la complexité d'un puzzle de sudoku en analysant les différentes techniques nécessaires à sa résolution. En ce qui concerne Le Sudoku, les règles de classification suivantes ont été adoptées :
• facile : la déduction de chaque chiffre est directe ; aucune technique avancée n'est nécessaire
• moyen : soit la déduction est directe, soit il faut utiliser la technique du ...
• difficile : il faut utiliser la technique du ... ou la technique du ...
• expert : c'est seulement à l'aide de la technique du ... que vous pourrez résoudre cette catégorie de puzzles »
Dans un billet publié sur le site du Monde, Une échelle de Richter pour les grilles de sudoku, Pierre Barthélémy présente une échelle inventée par deux physiciens, permettant de mesurer le degré de difficulté des grilles de sudoku :
« 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. »
L’analyse (en anglais) de Maria Ercsey-Ravasz et Zoltan Toroczkai peut être consultée directement en ligne : The Chaos Within Sudoku.
Les joueurs de sudoku ont recours à certaines techniques pour la résolution des grilles, en particulier les plus difficiles. On en trouve facilement des présentations en ligne. En voici quelques exemples :
- Aide et technique de résolution
- Les techniques de résolution
- Sudoku: une méthode de résolution simple et infaillible!
- Les techniques plus compliquées pour résoudre les Sudoku
Vous constaterez qu’en fin de compte le nombre de techniques pour résoudre un sudoku est assez limité, et chaque technique est adaptée à un degré de difficulté spécifique ; nous supposons donc que, pour une grille donnée, les différents joueurs sont plus ou moins contraints de suivre les mêmes étapes pour aboutir à la résolution.
Pour aller plus loin, quelques casse-têtes qui pourront vous intéresser :
• Les carrés magiques : du lo shu au sudoku, Arno van den Essen
Le récit de l'histoire des carrés magiques, du premier carré gravé sur une carapace de tortue jusqu'aux sudokus modernes, est accompagné de multiples exemples à résoudre.
• Jeux logiques et énigmes policières [Livre] / sous la direction de Bernard Myers ; rédaction Denis Auroux, Raymond Bloch, Michel Criton... [et al.]
Le lecteur doit résoudre une enquête policière en trouvant la clé des différentes énigmes qui se présentent au fil de la lecture (par la logique, le raisonnement mathématique, le décryptage, l'observation, etc.).
• Tests de logique [Livre] : (en)jeux de société / sous la direction de Bernard Myers ; rédaction Denis Auroux, Raymond Bloch, Michel Criton... [et al.]
Des jeux de logique (quiz, psychotest, jeux de lettres, de maths, etc.) de difficulté croissante, autour de l'univers des jeux de société. Avec les solutions en fin d'ouvrage.
Bonne journée.
Voici les explications fournies par le-sudoku.fr sur les niveaux de difficulté :
« Niveaux de difficulté
Comment définir la difficulté d'une grille de sudoku ?
Plusieurs paramètres sont à prendre en compte :
• la taille du sudoku : plus il est petit, plus vite vous l'aurez terminé
• le nombre de cases pré-remplies : plus elles sont nombreuses, plus le sudoku sera facile - quoi que en fait, ce nombre de cases ne soit pas vraiment une mesure exacte de la complexité
• la disposition des chiffres : leur placement dans la grille
Aussi curieux que cela puisse paraître, deux grilles de sudoku peuvent tout à fait placer des cases pré-remplies de façon totalement identique, mais avoir une difficulté complètement différente en fonction de la valeur des chiffres qui sont placés.
On peut en fait mesurer la complexité d'un puzzle de sudoku en analysant les différentes techniques nécessaires à sa résolution. En ce qui concerne Le Sudoku, les règles de classification suivantes ont été adoptées :
• facile : la déduction de chaque chiffre est directe ; aucune technique avancée n'est nécessaire
• moyen : soit la déduction est directe, soit il faut utiliser la technique du ...
• difficile : il faut utiliser la technique du ... ou la technique du ...
• expert : c'est seulement à l'aide de la technique du ... que vous pourrez résoudre cette catégorie de puzzles »
Dans un billet publié sur le site du Monde, Une échelle de Richter pour les grilles de sudoku, Pierre Barthélémy présente une échelle inventée par deux physiciens, permettant de mesurer le degré de difficulté des grilles de sudoku :
« 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. »
L’analyse (en anglais) de Maria Ercsey-Ravasz et Zoltan Toroczkai peut être consultée directement en ligne : The Chaos Within Sudoku.
Les joueurs de sudoku ont recours à certaines techniques pour la résolution des grilles, en particulier les plus difficiles. On en trouve facilement des présentations en ligne. En voici quelques exemples :
- Aide et technique de résolution
- Les techniques de résolution
- Sudoku: une méthode de résolution simple et infaillible!
- Les techniques plus compliquées pour résoudre les Sudoku
Vous constaterez qu’en fin de compte le nombre de techniques pour résoudre un sudoku est assez limité, et chaque technique est adaptée à un degré de difficulté spécifique ; nous supposons donc que, pour une grille donnée, les différents joueurs sont plus ou moins contraints de suivre les mêmes étapes pour aboutir à la résolution.
Pour aller plus loin, quelques casse-têtes qui pourront vous intéresser :
• Les carrés magiques : du lo shu au sudoku, Arno van den Essen
Le récit de l'histoire des carrés magiques, du premier carré gravé sur une carapace de tortue jusqu'aux sudokus modernes, est accompagné de multiples exemples à résoudre.
• Jeux logiques et énigmes policières [Livre] / sous la direction de Bernard Myers ; rédaction Denis Auroux, Raymond Bloch, Michel Criton... [et al.]
Le lecteur doit résoudre une enquête policière en trouvant la clé des différentes énigmes qui se présentent au fil de la lecture (par la logique, le raisonnement mathématique, le décryptage, l'observation, etc.).
• Tests de logique [Livre] : (en)jeux de société / sous la direction de Bernard Myers ; rédaction Denis Auroux, Raymond Bloch, Michel Criton... [et al.]
Des jeux de logique (quiz, psychotest, jeux de lettres, de maths, etc.) de difficulté croissante, autour de l'univers des jeux de société. Avec les solutions en fin d'ouvrage.
Bonne journée.
DANS NOS COLLECTIONS :
Commentaires 0
Connectez-vous pour pouvoir commenter.
Se connecter