Dans les journaux ou sur Internet, on parle parfois du « sudoku le plus difficile du monde ». Ce sont des grilles présentées comme exceptionnellement difficiles, créées par des mathématiciens ou des auteurs de puzzles. Mais il n’existe pas de critère officiel pour décerner ce titre. Quelle grille est la plus difficile dépend de la façon dont on mesure la difficulté.
Le nombre d’indices ne décide pas
On croit souvent qu’une grille est plus difficile quand il y a moins de chiffres au départ, mais ce n’est pas toujours vrai.
Voici le nombre de chiffres de départ des grilles 9×9 de l’app NumberPlace.
| Difficulté | Nombre de chiffres |
|---|---|
| ★1 Facile | 36 à 40 |
| ★2 Normal | 30 à 35 |
| ★3 Difficile | 24 à 31 |
| ★4 Expert | 22 à 31 |
| ★5 Maître | 22 à 31 |
Pour ★3 à ★5, les fourchettes se recoupent. Il existe des ★5 avec 30 chiffres, et des ★3 avec 24. Ce qui fait la difficulté, c’est moins le nombre de chiffres que l’endroit par où l’on peut commencer.
La difficulté dépend des techniques nécessaires
La difficulté d’un sudoku se mesure en général par le niveau des techniques nécessaires pour le résoudre. Les ★ de l’app NumberPlace sont fixées selon cette idée.
- Résolution avec les seuls singletons (« ce chiffre ne peut aller que dans cette case », « seul ce chiffre peut aller dans cette case ») : facile
- Il faut des candidats verrouillés ou des paires : difficile
- Il faut des triplets, un X-Wing, un XY-Wing, un Swordfish, etc. : expert ou maître
Le nombre de fois où l’on utilise une technique avancée compte aussi. Dans l’app, ★4 est une grille où une technique avancée est nécessaire une fois, et ★5 une grille où elle l’est au moins deux fois.
Les grilles que l’on appelle « les plus difficiles du monde » sont celles où l’on reste bloqué même en utilisant toutes ces techniques, et que l’on ne résout qu’avec des techniques encore plus complexes ou de longues chaînes d’hypothèses.
À quel point les grilles difficiles sont-elles rares ?
Avec la même méthode de fabrication que l’app NumberPlace (partir d’une grille complète et effacer des chiffres symétriquement par rapport au centre), j’ai créé 300 grilles 9×9 pour les étudier. On continue d’effacer des chiffres tant que la grille se résout jusqu’au bout avec des techniques seulement.
| Technique la plus difficile | Nombre de grilles |
|---|---|
| Singletons seulement | 243 grilles (environ 81 %) |
| Jusqu’aux candidats verrouillés et aux paires | 40 grilles (environ 13 %) |
| Techniques avancées nécessaires | 17 grilles (environ 6 %) |
Autrement dit, quand on fabrique des grilles normalement, on obtient rarement des grilles difficiles. Dans l’app, on recommence à fabriquer jusqu’à obtenir une grille qui demande des techniques avancées, afin de proposer des grilles ★4 et ★5 (Comment on fabrique un sudoku).
Pour s’attaquer aux grilles difficiles
- Commencez par ★3 et apprenez à bien utiliser les candidats verrouillés et les paires (Résoudre un sudoku avancé).
- Puis, en ★4 et ★5, entraînez-vous à repérer le X-Wing et le XY-Wing (Résoudre une grille difficile).
- Les grilles dites « les plus difficiles du monde » s’adressent à ceux qui maîtrisent toutes ces techniques et veulent aller plus loin. Si vous n’y arrivez pas, inutile d’être déçu.
