Le Sudoku le plus dur au monde à l’épreuve d’un moteur d’indices

Il n’existe pas de Sudoku officiellement reconnu comme le plus dur : tout dépend de la façon de mesurer la difficulté. Nous l’avons mesurée comme un joueur résout une grille, une étape à la fois avec la technique la plus simple qui fonctionne, grâce au moteur d’indices de notre application de Sudoku.

Notre méthode de mesure

Le moteur d’indices utilise le même code que l’indice de notre application. Il trouve la technique la plus simple qui permet de placer un chiffre, le place, puis recommence jusqu’à ce que la grille soit remplie. La technique Chaîne de forçage est la dernière qu’il essaie ; quand elle ne fonctionne pas non plus, le moteur connaît tout de même le chiffre, mais ne dispose d’aucune étape pour l’expliquer. Vous pouvez voir toutes les étapes dans le solveur de Sudoku.

Les résultats

Ce que cela montre

• Moins de chiffres donnés ne rendent pas une grille plus difficile. La grille conçue contre la force brute contient 17 chiffres donnés, le minimum pour un Sudoku avec une seule solution, et une personne la résout uniquement avec des singletons. La grille de 2012 d’Inkala contient 21 chiffres donnés et nécessite pourtant des essais.
• La difficulté pour un ordinateur n’est pas celle d’une personne. Un programme qui essaie chaque chiffre à tour de rôle doit en essayer un très grand nombre sur la grille conçue contre la force brute ; une personne n’a jamais besoin de deviner pour la résoudre.
• Le niveau le plus difficile de l’application ne va pas jusqu’aux essais. Aucune de ses 60 000 grilles ne nécessite la technique Chaîne de forçage ; le niveau Extrême est surtout déterminé par ALS-XZ, dans 86,3 % des grilles de niveau Extrême.

La grille la plus difficile dépend de la mesure choisie. Selon la mesure propre à SudokuWiki, la grille de 2012 d’Inkala arrive en troisième position, derrière deux grilles de David Filmer. SudokuWiki: Arto Inkala Sudoku