La difficulté d’un Sudoku : ce qui rend une grille difficile

Le nombre de chiffres ne suffit pas

Il faut au moins 17 chiffres de départ pour qu’une grille classique ait une solution unique : Gary McGuire et son équipe l’ont démontré en 2012 par une recherche exhaustive sur ordinateur, sans trouver aucune grille valide à 16 chiffres. Au-delà de ce minimum, le nombre de chiffres ne détermine pas la difficulté : une grille peu fournie peut se résoudre avec les seuls singles si ses chiffres sont bien placés, tandis qu’une autre, plus fournie, peut exiger des techniques avancées.

La disposition compte autant que la quantité. Des chiffres concentrés dans quelques blocs laissent de grandes zones sans information, alors que des chiffres répartis permettent des balayages dans toute la grille.

Mesurer la difficulté par les techniques

De nombreux sites et éditeurs classent leurs grilles selon les techniques nécessaires. On résout la grille en appliquant toujours la déduction la plus simple disponible, et l’on retient la plus difficile qu’il a fallu employer :

1. Singles nus : une case n’a plus qu’un candidat.
2. Singles cachés : un chiffre n’a plus qu’une place dans une unité (balayage).
3. Techniques essentielles : candidats verrouillés, paires et triplets.
4. Techniques avancées : X-Wing et Swordfish, XY-Wing et XYZ-Wing, chaînes simples.
5. Au-delà : chaînes longues, raisonnements par l’absurde élaborés et autres techniques non présentées ici.

Une grille qui demande un seul X-Wing au milieu de nombreux singles reste plus abordable qu’une grille qui exige plusieurs techniques avancées d’affilée. Les classements les plus fins tiennent donc aussi compte du nombre d’étapes difficiles.

Les niveaux de SudokuSimple

Nous avons analysé 100 grilles par niveau, produites par le générateur du jeu. Chaque cellule du tableau indique combien de grilles ont exigé, au plus, la catégorie de techniques de la colonne.

Ce que l’on peut en retenir

• Facile : toutes les grilles analysées se terminent avec les seuls singles nus.
• Moyen : toujours résoluble par singles ; 92 grilles sur 100 exigent au moins un single caché.
• Difficile : aucune grille ne se résout par les seuls singles. Les candidats verrouillés interviennent dans 87 grilles sur 100 (pointage), l’XY-Wing dans 25 ; 27 grilles demandent davantage que les techniques de ce wiki.
• Expert : 51 grilles sur 100 dépassent les techniques présentées ici. Ce niveau s’adresse aux joueurs à l’aise avec les chaînes.

Méthode et limites

• Les grilles proviennent du générateur du jeu, avec des graines fixes : la mesure est reproductible et revérifiée par les tests automatiques du projet.
• Le résolveur d’analyse applique toujours la technique la plus simple disponible, dans l’ordre de la liste ci-dessus. Chaque déduction est contrôlée par rapport à la solution.
• La catégorie « au-delà » signifie seulement que ces techniques ne suffisent pas. Elle ne signifie pas qu’il faut deviner : la solution est unique et reste accessible par déduction.
• Avec un autre ordre ou d’autres techniques, certaines grilles changeraient de catégorie. Les niveaux affichés par le jeu restent une estimation.
• Le générateur classe les grilles avec ses propres critères (singles disponibles, nombre de chiffres de départ, effort de recherche du solveur). L’analyse de cette page en est indépendante.

Choisir son niveau

Facile

Pour découvrir les règles et les singles nus. Aucune note n’est indispensable.

Moyen

Pour pratiquer le balayage et les singles cachés.

Difficile

Pour apprendre à utiliser les notes, les candidats verrouillés, les paires et l’XY-Wing.

Expert

Pour les joueurs qui maîtrisent les techniques avancées et souhaitent aborder les chaînes.

Passez au niveau suivant quand vous terminez régulièrement vos grilles sans indice. Vos temps et vos réussites par niveau sont visibles dans vos statistiques.