Comment mesure-t-on la difficulté d'un sudoku ?

La difficulté d'une grille se définit par l'unique technique logique la plus difficile requise pour la résoudre sans deviner. Des solveurs comme Sudoku Explainer parcourent une grille avec une échelle fixe de techniques — des candidats uniques jusqu'aux chaînes forcées — et rapportent le barreau le plus difficile qu'ils ont dû utiliser sous forme de nombre, le grade SE. Comme la méthode est fixe et reproductible, la même grille obtient toujours le même grade, et c'est pourquoi nous notons chaque grille ainsi plutôt qu'avec des mots vagues comme « facile » ou « expert ».

Pas de façon fiable. Le nombre minimal de cases données qu'une grille de sudoku valide peut avoir tout en conservant exactement une solution est 17 — démontré par une recherche informatique exhaustive (McGuire, Tugemann et Civario, 2012). Mais le nombre de cases données ne suit que faiblement la difficulté : une grille à 17 cases données peut être douce, et une grille à 30 cases données peut exiger des chaînes avancées. Ce qui compte, c'est la technique que la disposition impose, pas le nombre de cases vides.

Il existe 6,670,903,752,021,072,936,960 — environ 6.67 × 10²¹ — grilles de sudoku entièrement résolues (Felgenhauer et Jarvis, 2005), qui se réduisent à 5,472,730,538 essentiellement différentes une fois la symétrie retirée. En pratique, cela signifie que les grilles inédites, jamais vues, ne s'épuiseront jamais, quelle que soit la difficulté.

Les célèbres « monstres » comme AI Escargot (Arto Inkala, 2006) ont autrefois été présentés comme les plus durs jamais créés. Le grade SE permet de les comparer objectivement plutôt que par réputation : les grilles les plus dures connues se situent autour du grade SE 11 et au-delà.

Va voir comment fonctionne le grade SE ou les grilles les plus dures pour la liste des monstres.