Le Sudoku utilise des chiffres, mais ce n'est pas un jeu de calcul.
Pour résoudre une grille classique, vous n'avez pas besoin d'additionner, multiplier ou appliquer des formules.
Les chiffres 1 à 9 fonctionnent principalement comme neuf symboles distincts.
L'intérêt mathématique vient de la structure qui organise ces symboles :
- combinatoire ;
- carrés latins ;
- satisfaction de contraintes ;
- Exact Cover ;
- relations de conflits ;
- symétrie ;
- recherche ;
- dénombrement.
Cette structure explique pourquoi le Sudoku est à la fois très simple à définir et doté d'un espace de solutions immense.
Sudoku comme carré latin contraint
Un carré latin d'ordre 9 est une disposition 9×9 de neuf symboles où chaque symbole apparaît exactement une fois dans chaque ligne et chaque colonne.
Une grille Sudoku classique complètement résolue respecte ces deux conditions plus les contraintes des blocs 3×3.
Donc :
Toute grille Sudoku classique complète est un carré latin avec des contraintes supplémentaires de blocs.
Mais :
Tout carré latin 9×9 n'est pas une grille Sudoku valide.
Cette relation est importante mathématiquement.
Elle ne justifie cependant pas l'affirmation historique simplifiée :
« Euler a inventé le Sudoku. »
Les carrés latins appartiennent à l'ascendance mathématique.
L'histoire directe du puzzle moderne est traitée séparément dans Histoire du Sudoku.
Satisfaction de contraintes
Le Sudoku est un exemple naturel de Constraint Satisfaction Problem.
Considérez chaque case comme une variable.
Une case non résolue peut commencer avec le domaine :
{1,2,3,4,5,6,7,8,9}
Les indices et les relations entre cases réduisent ces domaines.
Exemple :
r4c7 candidats
{2,5,8}Si une case liée reçoit 5, le candidat 5 peut être supprimé de cet ensemble.
Pour le joueur, c'est une mise à jour des candidats.
Dans un modèle CSP, c'est de la propagation de contraintes.
Sudoku comme Exact Cover
Le Sudoku classique peut aussi être formulé comme un problème d'Exact Cover.
Une solution complète doit satisfaire exactement plusieurs familles de contraintes :
- chaque case reçoit exactement un chiffre ;
- chaque ligne contient chaque chiffre une fois ;
- chaque colonne contient chaque chiffre une fois ;
- chaque bloc contient chaque chiffre une fois.
Chaque placement possible rNcM = d satisfait une combinaison de ces contraintes.
Une solution Sudoku correspond alors à un ensemble de placements qui couvre chaque contrainte exactement une fois.
Cette représentation est particulièrement utile pour les solveurs complets et le comptage de solutions.
Sudoku comme réseau de conflits
Le Sudoku peut également être vu comme un réseau où des états candidats sont reliés par des incompatibilités.
Une relation peut dire :
Ces deux états ne peuvent pas être vrais simultanément.
Cette idée réapparaît dans la résolution humaine sous forme de :
- cases liées ;
- Weak Links ;
- Strong Links ;
- Chains.
La représentation formelle change.
La structure de contraintes reste la même.
Recherche et backtracking
Un solveur complet peut utiliser une recherche récursive.
Flux simplifié :
- choisir une case non résolue ;
- tester un candidat ;
- propager les contraintes ;
- revenir en arrière en cas de contradiction ;
- continuer jusqu'à trouver les solutions.
Avec une bonne sélection des variables et une propagation précoce, ce processus peut être très efficace.
Ce type de solveur répond à :
- une solution existe-t-elle ?
- en existe-t-il plusieurs ?
- quelle grille complète correspond aux indices ?
C'est une autre tâche qu'un solveur human-style qui doit expliquer une succession de techniques nommées.
Combien existe-t-il de grilles Sudoku complètes ?
Pour le Sudoku classique 9×9, le nombre de grilles complètes valides est :
6 670 903 752 021 072 936 960
soit environ :
6,671 × 10²¹
Ce nombre compte d'abord comme distinctes des grilles pouvant être reliées par des symétries ou par permutation des chiffres.
Grilles essentiellement différentes
De nombreuses grilles complètes peuvent être transformées les unes dans les autres par des opérations qui préservent la validité, par exemple :
- renommer les chiffres ;
- permuter des lignes dans une même bande ;
- permuter des colonnes dans une même pile ;
- permuter les bandes ou les piles ;
- transposer la grille ;
- combiner ces symétries.
Lorsque l'on regroupe les grilles sous le groupe standard de symétries Sudoku, il reste :
5 472 730 538
grilles essentiellement différentes.
Cela représente encore plusieurs milliards.
Pourquoi ce nombre n'est pas le nombre de puzzles possibles
Une grille solution complète n'est qu'un point de départ.
À partir de la même solution, on peut choisir de très nombreux ensembles d'indices.
Certains :
- n'ont pas de solution unique ;
- sont minimaux ;
- contiennent des indices redondants ;
- produisent des difficultés et chemins de résolution différents.
Donc :
nombre de grilles complètes
n'est pas équivalent à :
nombre de Sudoku publiables possibles.
Symétrie dans la génération
Symétrie mathématique
Certaines transformations envoient une grille complète valide sur une autre grille complète valide.
Symétrie de disposition des indices
Un constructeur peut placer les indices avec une symétrie de rotation, par exemple à 180°.
Cette seconde forme est avant tout une décision esthétique ou éditoriale.
Ce n'est pas une règle du Sudoku classique.
Combinatoire et choix des indices
Un générateur doit sélectionner un ensemble d'indices parmi 81 positions.
Le nombre de sous-ensembles possibles est immense.
Mais seule une petite partie possède simultanément les propriétés souhaitées :
- cohérente ;
- unique ;
- résoluble avec le modèle human-style ciblé ;
- correctement calibrée ;
- éditorialement satisfaisante.
La génération est donc un problème de recherche et de validation.
Nombre minimal d'indices comme problème extrémal
La question :
Combien d'indices au minimum peuvent déterminer un Sudoku classique unique ?
est un problème mathématique extrémal.
La réponse prouvée est 17.
Cette limite ne dit rien sur l'élégance ou la difficulté d'un Sudoku particulier à 17 indices.
Difficulté comme problème de modélisation humaine
Un solveur complet peut résoudre très rapidement une grille que les humains trouvent difficile.
Le temps de calcul d'un simple backtracking n'est donc pas un bon indicateur de difficulté humaine.
Un meilleur modèle examine :
- les techniques humaines requises ;
- le nombre et l'ordre des étapes ;
- les dépendances ;
- l'effort de reconnaissance ;
- les données joueurs.
Pourquoi plusieurs solveurs ont plusieurs rôles
Solveur complet / compteur de solutions
Répond à :
- existe-t-il une solution ?
- est-elle unique ?
- quelles solutions complètes existent ?
Solveur human-style
Produit :
- des étapes nommées ;
- des éliminations expliquées ;
- un chemin de résolution lisible ;
- des données pour le rating.
Générateur
Combine :
- grille solution ;
- sélection d'indices ;
- vérification d'unicité ;
- analyse human-style ;
- évaluation de difficulté ;
- filtres qualité.
Un seul algorithme n'a pas besoin de remplir les trois fonctions.
FAQ
Le Sudoku repose-t-il sur l'arithmétique ?
Non. Les chiffres jouent principalement le rôle de symboles distincts.
Toute grille Sudoku est-elle un carré latin ?
Toute grille Sudoku classique complètement résolue est un carré latin avec des contraintes supplémentaires de blocs.
Tout carré latin est-il un Sudoku ?
Non.
Combien existe-t-il de grilles Sudoku classiques complètes ?
6 670 903 752 021 072 936 960.
Pourquoi seulement environ 5,47 milliards de grilles essentiellement différentes ?
Parce que de nombreuses grilles complètes sont équivalentes sous permutation des chiffres et symétries valides.
Un espace immense rend-il automatiquement une grille difficile ?
Non. La difficulté dépend du puzzle de départ et de son chemin de résolution humain.
Que lire ensuite ?
Lisez Comment les Sudoku sont générés pour la construction pratique et Comment la difficulté du Sudoku est évaluée pour les modèles human-style.