Les mathématiques du sudoku mènent à une «échelle plus riche» de la dureté du puzzle

La fascination mondiale pour le Sudoku a conduit à un intérêt soudain pour les propriétés mathématiques du puzzle. Au cours des derniers mois sur ce blog, nous avons examiné comment les mathématiciens ont résolu le problème du Sudoku minimum et même comment ils ont utilisé les mathématiques du Sudoku pour crypter des images.

Aujourd'hui, nous avons une vision différente du Sudoku grâce aux travaux de Maria Ercsey-Ravasz à l'Université Babes-Bolyai en Roumanie et de Zoltan Toroczkai à l'Université de Notre Dame en Indiana.

Ces gars ont développé un moyen de mesurer la difficulté d'un puzzle de Sudoku particulier et disent que leur échelle de difficulté de Richter pourrait être appliquée à un large éventail d'autres jeux.

Tout d'abord, un petit aperçu du Sudoku. Il s'agit d'un puzzle numérique composé d'une grille de 9 x 9 dans laquelle certaines cellules contiennent des indices sous la forme de chiffres de 1 à 9. Le travail du résolveur consiste à remplir les cellules restantes de sorte que chaque ligne, colonne et case 3×3 la grille contient les neuf chiffres. De plus, chaque grille ne peut avoir qu'une seule solution.

Les énigmes de sudoku sont généralement classées comme faciles, moyennes ou difficiles, les énigmes ayant généralement plus d'indices de départ, mais pas toujours plus faciles à résoudre. Mais quantifier mathématiquement la difficulté est difficile.

Maintenant, Ercsey-Ravasz et Toroczkai disent qu'ils ont trouvé un moyen de le faire en utilisant la théorie de la complexité algorithmique. Ils soulignent qu'il est facile de concevoir un algorithme qui résout le Sudoku en testant chaque combinaison de chiffres pour trouver celle qui fonctionne. Ce genre de solution de force brute vous garantit une réponse mais pas très rapidement.

Au lieu de cela, les concepteurs d'algorithmes recherchent des moyens plus intelligents de trouver des solutions qui exploitent la structure et les contraintes du problème. Ces algorithmes et leur comportement sont plus complexes mais ils obtiennent une réponse plus rapidement.

Le point central de l'argument d'Ercsey-Ravasz et Toroczkai est que, parce qu'un algorithme reflète la structure du problème, son comportement - les méandres qu'il suit dans l'espace d'états - est une bonne mesure de la difficulté du problème.

Pour le démontrer, ils abordent l'exemple du Sudoku. Au lieu de la solution de force brute, ils conçoivent un algorithme beaucoup plus élégant qui exploite les différentes contraintes du puzzle, comme le fait que chaque colonne de ligne et sous-grille doit contenir tous les chiffres de 1 à 9.

De cette façon, ils transforment le problème en un type connu des théoriciens de la complexité sous le nom de problème k-sat.

Ils commencent par insérer un ensemble aléatoire de nombres dans la grille et suivent la trajectoire de l'algorithme à travers l'espace d'état alors qu'il recherche une solution. Pour un problème simple, cette trajectoire est simple, comme le montre la partie supérieure des deux figures en haut de cet article.

Mais tout cela change pour un problème difficile. Ercsey-Ravasz et Toroczkai testent leur algorithme contre une grille de Sudoku si difficile qu'elle a son propre nom : le blond platine. Le résultat est affiché dans la moitié inférieure de la figure. Il est considérablement plus complexe et prend dix fois plus de temps à résoudre.

Ercsey-Ravasz et Toroczkai disent que pour les problèmes difficiles, la trajectoire devient chaotique avant de s'installer sur une solution. En fait, le temps qu'il faut pour échapper à cet état chaotique est une simple mesure de la difficulté.

Sur cette base, ils créent une «échelle de Richter» de difficulté de puzzle basée sur le taux d'évasion. L'échelle va de 1 à 4, un étant le plus facile et 4 étant ultradur.

Ils disent que cette échelle est étonnamment bien corrélée avec les évaluations humaines subjectives avec 1 correspondant aux énigmes faciles, 2 aux énigmes moyennes et 3 aux énigmes difficiles. Le blond platine a une difficulté de 3,5789.

Un corollaire intéressant est qu'aucun puzzle Sudoku n'est connu avec une difficulté de 4. Et le nombre d'indices n'est pas toujours une bonne mesure de la difficulté non plus. Ercsey-Ravasz et Toroczkai disent avoir testé de nombreux puzzles dont plusieurs avec les 17 indices, le nombre minimum, et quelques-uns avec 18 indices.

Ceux-ci étaient tous plus faciles à résoudre que le blond platine, qui a 21 indices. C'est parce que la dureté du puzzle dépend non seulement du nombre d'indices mais aussi de leur position.

Une question intéressante est maintenant de savoir si un puzzle ultradur avec une difficulté de 4 existe réellement et comment il peut être trouvé.

Plus important encore, la méthode d'Ercsey-Ravasz et Toroczkai se généralise à tous les problèmes k-sat de la même classe que Sudoku. Ainsi, la difficulté de ces problèmes peut tous être classée par des échelles similaires de type Richter.

Cela ne laisse qu'une question : comment appeler l'échelle de difficulté du puzzle ? La réponse évidente est l'échelle Ercsey-Ravasz et Toroczkai ou échelle ERT. Toute autre suggestion dans la section commentaires ci-dessous.

Réf : arxiv.org/abs/1208.0370 : Le chaos dans le sudoku

cacher