Pour un Sudoku classique 9×9 qui doit posséder exactement une solution, le nombre minimal prouvé d'indices de départ est :
17
Des Sudoku uniques à 17 indices existent.
Un Sudoku classique unique à 16 indices n'existe pas.
Cette seconde affirmation a été établie par Gary McGuire, Bastian Tugemann et Gilles Civario à l'aide d'une recherche exhaustive assistée par ordinateur.
Le résultat répond à une question mathématique très précise.
Il ne signifie pas que 17 indices produisent automatiquement les meilleurs puzzles, les plus difficiles ou les plus intéressants.
Qu'est-ce qu'un indice ?
Un indice est un chiffre déjà placé avant le premier mouvement du joueur.
Autres termes rencontrés :
- chiffre donné ;
- given ;
- clue.
Un Sudoku à 17 indices commence avec :
- 17 cases remplies ;
- 64 cases vides.
La solution complète contient toujours 81 chiffres.
Le nombre d'indices décrit l'état initial, pas la taille de la solution.
Pourquoi l'unicité fait partie de la question
Sans imposer une solution unique, on pourrait retirer beaucoup d'indices et obtenir un état de départ avec de nombreuses complétions possibles.
Ce n'est pas le problème du minimum d'indices.
La vraie question est :
Quel est le plus petit ensemble d'indices qui détermine exactement une grille Sudoku classique 9×9 complète ?
Deux conditions doivent donc être vraies en même temps :
- Les indices sont compatibles avec au moins une solution.
- Il n'existe pas de seconde solution.
Pourquoi 17 n'était pas évident
Les chercheurs et collectionneurs connaissaient depuis longtemps des Sudoku uniques à 17 indices.
Pendant des années, personne n'avait trouvé d'exemple à 16.
Mais :
« Personne n'en a trouvé »
n'est pas équivalent à :
« Il n'en existe aucun. »
Le défi était de prouver qu'aucun Sudoku à 16 indices ne se cachait dans l'immense espace de recherche.
La preuve contre 16 indices
McGuire, Tugemann et Civario ont transformé le problème en une recherche exhaustive utilisant notamment des unavoidable sets et des hitting sets.
À haut niveau :
- partir de grilles Sudoku solutions complètes ;
- identifier des structures qu'un ensemble d'indices doit obligatoirement toucher pour préserver l'unicité ;
- traiter les positions possibles des indices comme un problème de hitting set ;
- énumérer efficacement les petits hitting sets ;
- tester exhaustivement les cas à 16 indices ;
- ne trouver aucun Sudoku unique à 16 indices.
La borne est donc établie :
Tout Sudoku classique 9×9 unique nécessite au moins 17 indices.
La preuve est assistée par ordinateur.
Il ne s'agit pas d'une petite démonstration élémentaire obtenue simplement en comptant les cases.
Qu'est-ce qu'un unavoidable set ?
Pour une grille solution donnée, un unavoidable set est un ensemble de cases possédant cette propriété :
Un puzzle unique construit à partir de cette solution doit contenir au moins un indice dans cet ensemble.
Pourquoi ?
Si toutes ces cases restent sans indice, une complétion alternative peut rester possible.
Un ensemble d'indices valide doit donc « toucher » chaque unavoidable set pertinent.
C'est l'origine de la formulation en hitting sets.
Pour cette introduction publique, cette intuition suffit ; le travail de recherche contient les détails computationnels.
Minimum vs minimal
Cette distinction est essentielle.
Nombre minimum d'indices
La plus petite valeur globalement possible.
Pour un Sudoku classique 9×9 unique :
17 indices.
Sudoku minimal
Puzzle dans lequel chaque indice présent est nécessaire à l'unicité.
Si l'on retire n'importe lequel d'entre eux, le puzzle n'est plus unique.
Un Sudoku minimal peut posséder :
- 18 ;
- 24 ;
- ou davantage d'indices.
« Minimal » ne signifie pas « possède 17 indices ».
Tout Sudoku unique à 17 indices est-il minimal ?
Oui.
Si l'on pouvait retirer un indice tout en conservant l'unicité, on obtiendrait un Sudoku unique à 16 indices.
Le résultat précédent l'exclut.
La réciproque est fausse :
Un Sudoku minimal n'a pas nécessairement 17 indices.
Peut-on choisir n'importe quelles 17 cases ?
Non.
La plupart des ensembles arbitraires de 17 positions ne produisent pas un bon Sudoku unique.
Ils peuvent :
- autoriser plusieurs solutions ;
- ne produire aucune solution si les chiffres sont incohérents ;
- ne pas être résolubles avec le modèle human-style prévu ;
- donner une difficulté inadaptée.
La borne globale dit seulement que certains Sudoku uniques à 17 indices existent.
17 indices signifie-t-il Expert ?
Non.
Le nombre d'indices est un mauvais indicateur isolé de difficulté humaine.
La difficulté dépend aussi de :
- leur position ;
- la structure des candidats ;
- les techniques nécessaires ;
- le nombre d'étapes ;
- la profondeur des dépendances ;
- l'effort de reconnaissance.
Une grille très vide peut révéler une logique simple.
Une grille plus remplie peut cacher une Chain difficile.
C'est pourquoi nombre minimal d'indices et évaluation de difficulté restent deux pages Theory distinctes.
Un Sudoku à 16 indices peut-il avoir plusieurs solutions ?
Bien sûr.
Le théorème exclut seulement les Sudoku classiques uniques à 16 indices.
Un état à 16 indices peut :
- avoir plusieurs solutions ;
- n'en avoir aucune ;
- ou simplement ressembler à une grille partielle valide.
Il ne peut pas déterminer exactement une solution classique.
Pourquoi ce résultat compte pour un générateur
Il indique surtout ce qu'un générateur pratique ne devrait pas optimiser aveuglément.
Un bon objectif ressemble davantage à :
unique
+ résoluble de façon humaine
+ difficulté calibrée
+ varié
+ reproductiblequ'à :
le moins d'indices possibleLa réduction extrême des indices peut coûter beaucoup de calcul sans produire de meilleurs puzzles.
Le nombre d'indices reste une métadonnée utile.
Ce n'est pas un objectif de qualité en soi.
Recherche vs gameplay
Le résultat des 17 indices est fascinant parce qu'il décrit une limite dure de la structure combinatoire du Sudoku.
Pour le joueur, la question la plus importante reste :
Cette disposition précise d'indices produit-elle un chemin logique juste et intéressant ?
Ce sont deux critères différents.
FAQ
Combien d'indices au minimum pour un Sudoku classique unique ?
17.
Existe-t-il un Sudoku unique à 16 indices ?
Non.
Tout Sudoku à 17 indices est-il difficile ?
Non.
Tout Sudoku unique à 17 indices est-il minimal ?
Oui.
Tout Sudoku minimal possède-t-il 17 indices ?
Non.
Pourquoi le nombre d'indices ne détermine-t-il pas la difficulté ?
Parce que leur position et la structure des déductions comptent beaucoup plus que le simple total.
Que lire ensuite ?
Lisez Solutions uniques au Sudoku pour comprendre la propriété globale à une solution.
Lisez Comment les Sudoku sont générés pour voir comment un générateur choisit et valide les indices.