← Retour au blog

Où se cache la difficulté d'un sudoku : les moments de blocage, mesurés sur 6 000 grilles

On imagine volontiers qu'une grille expert est difficile de bout en bout, comme une longue montée. Pour le vérifier, nous avons fait résoudre par notre solveur les 6 000 grilles du site, 1 500 par niveau : ce sont celles que tu reçois en solo, en multijoueur, sur les feuilles à imprimer et au défi du jour, à une permutation des chiffres et des lignes près, qui ne change rien à leur logique. À chaque étape, nous avons noté combien de cases il était possible de remplir tout de suite. Le résultat est net : la difficulté ne s'étale pas, elle se concentre. Entre facile et moyen, aucune grille ne bloque jamais ; c'est la largeur du chemin qui change. En difficile et en expert, tout se joue le plus souvent en un ou deux moments précis, après lesquels il reste en moyenne plus de la moitié des cases à remplir, avec les seules techniques de base.

🎮 Jouer au sudoku

Comment on a mesuré

Le solveur utilisé est celui du bouton Indice du jeu. Il cherche toujours la déduction la plus simple d'abord : les singletons (une case qui n'a plus qu'un candidat, ou un chiffre qui n'a plus qu'une place dans une ligne, une colonne ou un bloc), puis les candidats verrouillés et les paires nues, puis les paires cachées et les triplets, puis le X-Wing, le XY-Wing et le Swordfish. Trois mots reviennent dans la suite :

Un détail compte pour la suite : dans ce solveur, les techniques avancées ne posent jamais de chiffre. Elles retirent des candidats, et c'est toujours un singleton qui remplit la case ensuite. Sur les 6 000 grilles, chaque chiffre posé l'a été par un singleton.

Facile et moyen : aucun blocage, un chemin plus étroit

Le tableau compare les quatre niveaux. Les indices et les cases trouvables au départ sont des moyennes sur 1 500 grilles ; la largeur moyenne est calculée sur toutes les étapes où le solveur pose un chiffre.

NiveauIndicesTrouvables au départLargeur moyenneGrilles qui bloquent
Facile42,822,513,6aucune
Moyen32,712,99,2aucune
Difficile27,36,35,2toutes
Expert27,67,15,4toutes

Une grille moyenne ne bloque jamais : à chaque instant, au moins un singleton est disponible. Ce qui la distingue d'une grille facile, c'est qu'il y a moins de portes ouvertes en même temps : 13 cases trouvables au départ au lieu de 22 à 23, et 9 en moyenne au fil de la partie au lieu de 14. Le chemin se resserre aussi plus souvent : 12,3 % des grilles moyennes passent au moins une fois par un moment où il n'y a que deux cases trouvables ou moins, alors qu'il reste encore 20 cases vides ou plus. En facile, cela n'arrive que dans 4 grilles sur 1 500.

Concrètement, en moyen, tu ne bloques pas parce que la grille exige une technique que tu ne connais pas. Tu bloques parce que la case qui se trouve est ailleurs que là où tu regardes.

Ce que ça change pour ta façon de balayer

Nous avons ensuite rejoué les grilles en n'autorisant qu'une seule manière de chercher, pour voir jusqu'où elle mène.

Seule méthode autoriséeGrilles faciles finiesGrilles moyennes finies
Balayer les blocs : la seule place d'un chiffre dans un bloc98,6 %61,8 %
Balayer blocs, lignes et colonnes99,9 %95,9 %
Chercher les cases à un seul candidat98,7 %55,8 %
Les deux familles de singletons100 %100 %

En facile, n'importe quelle méthode suffit presque toujours : le balayage des blocs, à lui seul, finit 98,6 % des grilles. En moyen, il ne finit que 61,8 % d'entre elles. Pour plus d'une grille moyenne sur trois, il faut donc, à un moment, regarder un chiffre le long d'une ligne ou d'une colonne, et pas seulement dans un bloc. Avec lignes et colonnes, on arrive à 95,9 %. Les 4,1 % restants demandent en plus, au moins une fois, de repérer une case qui n'a plus qu'un candidat possible. Notre article bloc par bloc ou ligne par ligne décrit ces deux façons de regarder ; ces chiffres disent quand passer de l'une à l'autre.

Difficile et expert : un ou deux blocages, puis la descente

Aux deux niveaux supérieurs, toutes les grilles bloquent au moins une fois. Mais rarement beaucoup plus :

Le moment du premier blocage est lui aussi parlant. En difficile, il arrive tôt : après 15,6 chiffres posés en moyenne, soit 29 % des cases à remplir. En expert, après 21,8 chiffres, soit 41 %. Et après la dernière technique avancée, il reste en moyenne 69 % des cases à remplir en difficile et 53 % en expert, que les singletons suffisent à terminer. Autrement dit, quand tu as franchi le passage difficile, la plus grande partie de la grille est encore devant toi, mais elle se remplit au rythme d'une grille moyenne.

Une précision honnête : le nombre de blocages et d'étapes avancées dépend du chemin suivi, donc de l'ordre dans lequel on cherche. Sur une même grille présentée autrement, le solveur ne fait pas toujours exactement les mêmes étapes. Nous avons vérifié que les moyennes, elles, ne bougent pas : sur les mêmes 3 000 grilles transformées, la part de grilles à un seul blocage passe de 77,7 % à 77,9 % en difficile et de 53,1 % à 53,0 % en expert.

Le nombre d'indices ne dit presque rien

Les niveaux difficile et expert ont presque le même nombre d'indices, 27,3 et 27,6 en moyenne. Plus surprenant : 16,1 % des grilles expert en comptent 30 ou plus, autant que les grilles moyennes les moins fournies, et la plus généreuse en a 36. À l'intérieur d'un niveau, les indices jouent un peu :

Une grille expert à 30 indices reste une grille expert : elle exige au moins un X-Wing, un XY-Wing ou un Swordfish, comme toutes les autres de ce niveau. Ne te fie pas au nombre de chiffres de départ pour juger de ce qui t'attend.

Que chercher quand tu bloques

Le solveur dit aussi quelle technique a levé chaque blocage. En difficile, les candidats verrouillés servent dans 1 458 grilles sur 1 500, soit 97,2 %. Les paires nues ne servent que dans 24,3 % des grilles, les paires cachées dans 7,9 %, et les triplets presque jamais (16 grilles pour le triplet nu, 4 pour le triplet caché). Le solveur cherche les candidats verrouillés en premier, ce qui favorise leur part ; mais s'il les emploie dans 97,2 % des grilles, c'est qu'il en trouve d'utiles dans presque toutes. Au premier blocage d'une grille difficile, commence donc par les intersections entre bloc et ligne, ou bloc et colonne : un chiffre qui, dans un bloc, ne tient que sur une ligne.

En expert, le XY-Wing sert dans 94,3 % des grilles, le X-Wing dans 29,2 % et le Swordfish dans 2,5 %, alors même que le solveur cherche le X-Wing avant le XY-Wing. Et sur 65,4 % des grilles expert, le solveur n'emploie qu'une seule fois l'une de ces trois techniques. C'est l'idée centrale : une grille expert, c'est le plus souvent une déduction avancée, entourée de déductions ordinaires.

Le solveur ne connaît que ses propres techniques. D'autres motifs peuvent lever le même blocage, comme le gratte-ciel et le cerf-volant, présentés dans notre article qui leur est consacré. Les techniques elles-mêmes sont expliquées pas à pas dans le guide des techniques.

Ce qu'il faut retenir

Pour mettre tout ça à l'épreuve, lance une grille difficile sur Sudoku en ligne et note à quel moment tu bloques pour la première fois. Sur nos grilles, c'est le plus souvent une seule fois, et le reste suit.

À lire aussi

← Retour au blog Jouer au sudoku
Nouveautés 1/6
Voir tous nos défis du jour
Tu aimeras aussi
Voir tous les jeux →