Sur cette page
Le Sudoku utilise des chiffres, mais sa structure mathématique ne repose pas sur l’arithmétique. On n’additionne ni ne multiplie les valeurs : on impose surtout des contraintes d’unicité à neuf symboles.
Cette simplicité apparente permet plusieurs lectures mathématiques complémentaires : carré latin contraint, problème de satisfaction de contraintes, Exact Cover, graphe de conflits, espace combinatoire et problème algorithmique généralisé.
Pourquoi les nombres du Sudoku sont en réalité des symboles
Dans le Sudoku classique, le « 7 » n’a pas besoin d’être sept fois plus grand qu’un « 1 ». Il sert seulement d’étiquette distincte.
On pourrait remplacer 1–9 par neuf lettres, couleurs ou icônes, tant que chaque symbole reste identifiable et que les mêmes contraintes de non-répétition s’appliquent.
C’est pourquoi le Sudoku est un puzzle combinatoire, pas un exercice de calcul.
Sudoku comme carré latin contraint
Un carré latin d’ordre 9 contient neuf symboles, chacun apparaissant une fois par ligne et une fois par colonne.
Une grille Sudoku complète possède cette propriété et ajoute neuf régions 3×3 qui doivent elles aussi contenir chaque symbole exactement une fois.
Ainsi : tout Sudoku complet classique est un carré latin, mais l’inverse est faux.
- lignes : 1–9 une fois chacun
- colonnes : 1–9 une fois chacun
- pas de règle des blocs
- lignes : 1–9 une fois chacun
- colonnes : 1–9 une fois chacun
- blocs : 1–9 une fois chacun
Sudoku comme problème de satisfaction de contraintes
On peut modéliser chaque case comme une variable dont le domaine initial est {1,…,9} ou une valeur fixe si la case est donnée.
Les contraintes imposent que certaines variables prennent des valeurs toutes différentes : chaque ligne, colonne et bloc doit être une permutation de 1–9.
Cette représentation CSP permet la propagation de contraintes : lorsqu’une valeur devient impossible dans une case, cette information réduit parfois les domaines ailleurs et peut déclencher de nouvelles déductions. Dans un modèle plus formel, les contraintes all-different sur chaque unité peuvent propager davantage qu’un simple contrôle de doublons, ce qui rapproche certains solveurs de contraintes des raisonnements de sous-ensembles utilisés par les humains.
Des contraintes locales créent une structure globale
Chaque règle semble locale, mais les unités se recouvrent. Une case appartient simultanément à une ligne, une colonne et un bloc.
Ce chevauchement relie la grille entière. Une décision dans le coin supérieur gauche peut, par une suite de contraintes, influencer des candidats très éloignés.
Les techniques avancées exploitent précisément cette structure globale : Fish relient plusieurs lignes et colonnes, Wings relient des cases bivalue/trivalue, et les chaînes propagent des implications à travers le réseau de candidats.
Sudoku comme problème d’Exact Cover
Une formulation standard représente chaque placement candidat (r,c,d) comme une ligne possible d’un problème d’Exact Cover.
Pour un Sudoku 9×9, on peut partir de 729 placements possibles : 81 cases × 9 chiffres.
Une solution doit satisfaire exactement une fois 324 contraintes :
- 81 contraintes de case ;
- 81 contraintes ligne-chiffre ;
- 81 contraintes colonne-chiffre ;
- 81 contraintes bloc-chiffre.
Algorithm X peut alors rechercher un ensemble de placements couvrant chacune de ces contraintes exactement une fois. Une ligne correspondant à r4c7=5, par exemple, couvre simultanément la case r4c7, la présence du 5 dans la ligne 4, la colonne 7 et le bloc concerné. Choisir cette ligne élimine automatiquement toutes les lignes incompatibles partageant l’une de ces contraintes.
Cette formulation est extrêmement élégante pour la résolution complète et le comptage de solutions, car elle transforme les règles classiques en une structure uniforme. Elle n’encode toutefois pas directement les noms pédagogiques des techniques humaines.
Sudoku comme problème de type graphe
On peut aussi représenter les placements candidats comme des nœuds. Deux nœuds incompatibles sont reliés par une relation de conflit : même case avec deux chiffres différents, ou même chiffre dans deux cases d’une même unité.
Cette vue aide à comprendre Coloring, Strong/Weak Links et AIC. Les techniques humaines ne sont pas nécessairement implémentées comme un graphe formel, mais la représentation explique pourquoi les implications peuvent se propager. Des candidats en conflit forment naturellement des arêtes d’exclusion, tandis que des relations fortes créent des implications conditionnelles. Une chaîne alterne alors des états qui peuvent être interprétés comme un parcours dans ce réseau.
Recherche et backtracking
Le backtracking choisit une possibilité, poursuit récursivement, puis revient au point de branchement si une contradiction est rencontrée.
Avec de bonnes heuristiques — choisir une case très contrainte, propager les candidats, arrêter dès une contradiction — cette méthode résout efficacement des Sudoku classiques et peut compter leurs solutions.
Ce n’est pas pour autant une technique human-style : son objectif est la complétude algorithmique, pas nécessairement une explication pédagogique.
Exact Cover et backtracking ne sont pas opposés
Algorithm X est lui-même un algorithme de recherche avec choix et retour arrière, appliqué à une structure Exact Cover.
Dire « Exact Cover au lieu de backtracking » oppose donc deux niveaux différents : Exact Cover décrit l’encodage du problème ; backtracking décrit une famille de mécanismes de recherche.
Dancing Links (DLX) est une structure de données/technique d’implémentation qui accélère les opérations de couverture et découverte dans Algorithm X. DLX n’est pas synonyme d’Algorithm X.
Complexité computationnelle du Sudoku généralisé
Le Sudoku 9×9 possède une taille fixe, donc on peut toujours le résoudre dans un espace fini. En théorie de la complexité, on étudie plutôt des versions généralisées où la taille de la grille augmente.
La résolution de Sudoku généralisé est NP-complete. Cela signifie, très grossièrement, qu’aucun algorithme polynomial n’est connu pour tous les cas et que le problème peut encoder une recherche combinatoire difficile.
Cette classification théorique ne dit pas qu’un Sudoku 9×9 quotidien est difficile à résoudre pour un ordinateur.
Combien existe-t-il de grilles Sudoku classiques complètes ?
Le nombre exact de grilles solutions 9×9 classiques est :
6 670 903 752 021 072 936 960.
Ce résultat a été établi par comptage computationnel et analyse des symétries. Il mesure des grilles complètes distinctes, pas des puzzles à indices.
plus de six sextillions de grilles classiques de Sudoku entièrement remplies
Grilles Sudoku essentiellement différentes
Beaucoup de grilles sont équivalentes sous des transformations qui conservent la structure du Sudoku : permutation des chiffres, échange de lignes dans une bande, échange de colonnes dans une pile, permutation de bandes/piles et certaines symétries géométriques.
Quand ces équivalences sont factorisées, on obtient environ 5 472 730 538 grilles solutions essentiellement différentes.
Ce nombre reste immense, mais il décrit des classes structurelles plutôt que chaque renommage possible des chiffres.
Pourquoi le nombre de grilles solutions n’est pas le nombre de puzzles Sudoku
Un puzzle est un ensemble partiel d’indices associé à une ou plusieurs grilles complètes compatibles.
Une même grille solution peut engendrer énormément de puzzles différents selon les indices conservés. Et certains ensembles d’indices peuvent être compatibles avec plusieurs grilles solutions.
Le comptage des solutions complètes et le comptage des puzzles publiables sont donc des problèmes combinatoires différents. En outre, la notion de « puzzle différent » dépend de ce que l’on considère équivalent : même masque avec des chiffres permutés, même solution sous transformation de lignes/bandes, ou expérience de résolution distincte. Il n’existe donc pas un unique nombre simple de « tous les Sudoku possibles » qui réponde à toutes les interprétations.
Symétrie dans les mathématiques du Sudoku
Le mot symétrie couvre au moins deux idées distinctes.
Équivalence des grilles solutions
Certaines transformations produisent une grille qui est essentiellement le même objet mathématique : renommer les chiffres ou réorganiser certaines lignes/colonnes de manière structurellement valide.
Symétrie de la disposition des indices
Un constructeur peut aussi placer les indices selon une symétrie visuelle, par exemple une rotation de 180°. Cette esthétique de clue layout n’est pas une règle obligatoire du Sudoku.
Confondre les deux niveaux mène à des conclusions erronées sur la difficulté ou l’unicité.
Les permutations aident à expliquer l’équivalence des Sudoku
Comme les chiffres sont des symboles, toute permutation globale de 1–9 conserve la structure. Si l’on remplace partout 1→7, 7→3, etc., le puzzle transformé possède le même réseau logique sous un autre étiquetage.
Les permutations autorisées de lignes, colonnes, bandes et piles créent d’autres équivalences. Elles sont essentielles dans les calculs de classes de grilles et dans certaines stratégies de réduction de recherche. Pour un générateur, elles permettent aussi de produire des variantes structurellement équivalentes d’une grille source, même si un catalogue de qualité cherchera généralement une diversité plus riche que de simples transformations.
Combinatoire du choix des indices
À partir d’une grille solution, choisir les cases visibles est un problème de sous-ensembles. Pour k indices, il existe théoriquement C(81,k) choix de positions avant même d’évaluer l’unicité.
La grande majorité de ces choix ne produisent pas forcément un puzzle unique ou intéressant. La génération doit donc filtrer par solution count, difficulté, esthétique et autres critères. Le problème devient encore plus riche si l’on exige une symétrie particulière, un nombre exact d’indices ou une technique cible : chacune de ces conditions réduit l’espace admissible d’une manière différente. Les générateurs pratiques doivent donc combiner combinatoire et heuristiques ; énumérer naïvement tous les sous-ensembles possibles serait inutilement coûteux.
Nombre minimal d’indices comme problème extrémal
La question « quel est le plus petit nombre d’indices possible pour une solution unique ? » est un problème extrémal : on cherche une configuration à la frontière d’une propriété globale.
Pour le Sudoku classique 9×9, cette frontière est 17. La preuve qu’aucun cas à 16 indices n’existe combine structure, symétries et recherche computationnelle.
Difficulté comme modèle de calcul humain
La difficulté d’un puzzle n’est pas une constante mathématique universelle attachée à sa grille comme le nombre de solutions.
Elle dépend d’un modèle de résolution : techniques reconnues, ordre de recherche, coûts attribués aux étapes et effort de reconnaissance. Une plateforme peut ensuite calibrer ce modèle avec des données humaines.
La difficulté est donc une mesure construite de l’effort de résolution, pas un simple invariant combinatoire.
Pourquoi différents solveurs Sudoku servent des tâches différentes
Solveur complet / compteur de solutions
Il doit trouver une solution si elle existe et déterminer éventuellement s’il en existe une seconde. Sa priorité est la complétude et la correction.
Solveur human-style
Il cherche des étapes nommables et explicables : Singles, Locked Candidates, Subsets, Fish, Wings, Chains, etc. Il sert à produire un chemin pédagogique. Deux solveurs human-style peuvent néanmoins donner des parcours différents s’ils n’emploient pas la même priorité de techniques, d’où l’importance de versionner leur politique.
Analyseur de difficulté
Il transforme le chemin human-style en métriques : technique maximale, nombre d’étapes, dépendances, options productives et coûts de reconnaissance. Il peut ensuite convertir ces features en score continu, labels ou recommandations adaptées au public ciblé.
Générateur
Il propose ou retire des indices, appelle un compteur de solutions, puis utilise éventuellement un solveur human-style et un analyseur pour accepter les puzzles correspondant à un objectif.
Ces représentations ne sont pas concurrentes. Une même plateforme peut utiliser Exact Cover pour vérifier rapidement l’unicité, un CSP pour certaines analyses, un graphe de candidats pour expliquer des chaînes et un solveur human-style pour produire des étapes lisibles. Choisir le bon modèle pour chaque question est souvent plus important que chercher un algorithme unique qui ferait tout.
FAQ
Le Sudoku repose-t-il sur l’arithmétique ?
Non. Les chiffres sont essentiellement neuf symboles distincts ; aucune addition ou multiplication n’est requise par les règles classiques.
Toute grille Sudoku complétée est-elle un carré latin ?
Oui. Elle respecte une occurrence de chaque symbole par ligne et colonne.
Tous les carrés latins 9×9 sont-ils des grilles Sudoku valides ?
Non. Ils peuvent violer les contraintes supplémentaires des blocs 3×3.
Combien existe-t-il de grilles Sudoku classiques complètes ?
6 670 903 752 021 072 936 960.
Combien existe-t-il de grilles Sudoku complètes essentiellement différentes ?
Environ 5 472 730 538 après factorisation des principales équivalences structurelles.
Pourquoi existe-t-il autant de grilles si les règles sont si simples ?
Parce que les contraintes limitent un espace combinatoire immense sans le réduire à une poignée de configurations. Les permutations et choix compatibles restent extrêmement nombreux.
Le Sudoku est-il NP-complete ?
Le Sudoku généralisé est NP-complete. Cette affirmation de complexité ne signifie pas que le format fixe 9×9 soit difficile pour un ordinateur moderne.
Algorithm X est-il une technique humaine de Sudoku ?
Non. C’est un algorithme général pour Exact Cover, très utile dans les solveurs complets.
L’immense nombre de grilles solutions détermine-t-il la difficulté d’un Sudoku ?
Non. La difficulté d’un puzzle particulier dépend surtout de son ensemble d’indices et de son chemin de résolution selon le modèle choisi.